أسرع عرض وحدات في جافا سكريبت

StackOverflow https://stackoverflow.com/questions/1450608

سؤال

مشكلتي هي حساب (g^x) mod p بسرعة في جافا سكريبت، حيث ^ هو للأسف، mod هي عملية modulo. جميع المدخلات هي أعداد صحيحة غير طبيعية، x لديه حوالي 256 بت، و p هو عدد رئيسي 2048 بت، و g قد يكون ما يصل إلى 2048 بت.

يبدو أن معظم البرامج التي وجدتها أنها تستطيع القيام بذلك في جافا سكريبت تستخدم مكتبة JavaScript Bigint (http://www.lemon.com/crypto/bigint.html.). القيام برضيعة واحدة من هذا الحجم مع هذه المكتبة يستغرق حوالي 9 ثوان على متصفحي البطيء (Firefox 3.0 مع Spidermonkey). أبحث عن حل أسرع على الأقل 10 مرات. الفكرة الواضحة عن استخدام المربع والضرب (للأسود عن طريق التربيع، http://en.wikipedia.org/wiki/exponentiation_by_squaring.) بطيئ جدا لعدد 2048 بت: يحتاج إلى ما يصل إلى 4096 مضاعفة.

ترقية المتصفح ليس خيارا. باستخدام لغة برمجة أخرى ليست خيارا. إرسال الأرقام إلى خدمة ويب ليست خيارا.

هل هناك بديل بديل أسرع؟

تحديث: عن طريق القيام ببعض الاستعدادات الإضافية (أي مسبقة بضع مئات من القوى) على النحو الموصى به من قبل المقال http://www.ccrwest.org/gordon/fast.pdf. المذكورة في إجابة Outis أدناه، فمن الممكن القيام بالأسف المعياري 2048 بت باستخدام فقط على الأكثر 354 مضاعفة وحدات. (الطريقة التقليدية المربعة والضرب أبطأ بكثير: يستخدم الحد الأقصى 4096 مضربا وحدات.) القيام بذلك تسرع للأسود المعياري بعامل 6 في فايرفوكس 3.0، وعامل 4 في جوجل كروم. السبب في أننا لا نحصل على تسريع كامل من 4096/354 هو أن خوارزمية التصنيف المعيارية في Bigint أسرع بالفعل من المربع والضرب، لأنه يستخدم تخفيض مونتغمري (http://en.wikipedia.org/wiki/montgomery_reduction.).

تحديث: بدءا من رمز Bigint، يبدو من المفيد القيام بمستوتين من الضرب Karatsuba الأمثل (والمضمون) (http://en.wikipedia.org/wiki/karatsuba_algorithm.)، ثم يعود فقط إلى الضرب BASE-32768 O (N ^ 2) المنفذ في Bigint. هذا يسرع الصدد من خلال عامل 2.25 للأعداد الصحيحة 2048 بت. لسوء الحظ، لا تصبح عملية modulo أسرع.

تحديث: باستخدام تخفيض باريت المعدل المحدد في http://www.lirmm.fr/arith18/papers/hasenplaugh-fastalreduction.pdf. و Karatsuba الضرب والقوى الدماغية (كما هو محدد في http://www.ccrwest.org/gordon/fast.pdf.)، يمكنني الحصول على الوقت اللازم لضرب واحد من 73 ثانية إلى 12.3 ثانية في فايرفوكس 3.0. يبدو أن هذا هو أفضل ما يمكنني فعله، لكنه لا يزال بطيئا للغاية.

التحديث: مترجم ActionScript 2 (AS2) في Flash Player لا يستحق الاستخدام، لأنه يبدو أنه أبطأ من مترجم JavaScript في Firefox 3.0: للحصول على Flash Player 9، يبدو أنه بطيء 4.2 مرات، ولاعب Flash Player 10، يبدو أن 2.35 مرة أبطأ. هل يعرف أي شخص فرق السرعة بين Actioncript2 و ActionScript3 (AS3) لعدد الكرشينج؟

تحديث: مترجم ActionScript 3 (AS3) في Flash Player 9 لا يستحق الاستخدام لأنه يحتوي على نفس السرعة تقريبا مثل JavaScript Int Firefox 3.0.

تحديث: يمكن أن يصل مترجم ActionScript 3 (AS3) في Flash Player 10 إلى 6.5 مرات بشكل أسرع من مترجم JavaScript في Firefox 3.0 إذا int يستخدم بدلا من Number, ، و Vector.<int> يستخدم بدلا من Array. وبعد على الأقل كان 2.41 مرة أسرع لضرب عدد صحيح 2048 بت. لذلك قد يستحق القيام بالأسعار المعيارية في AS3، تنفيذها في Flash Player 10 إذا كان ذلك متاحا. يرجى ملاحظة أن هذا لا يزال أبطأ من V8، وهو مترجم JavaScript من Google Chrome. يرى http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html. لسرعة مقارنة بين مختلف لغة البرمجة وتطبيقات جافا سكريبت.

تحديث: هناك حل جافا سريع للغاية، يمكن استدعاؤه من جافا سكريبت المتصفح إذا تم تثبيت البرنامج المساعد Java. الحل التالي هو حوالي 310 مرة أسرع من تنفيذ الجافا سكريبت النقي باستخدام bigint.

<body>hi0
<script type="text/javascript">
document.body.innerHTML += '<br>hi1';
if ('object'==typeof java) {
  var x = new java.math.BigInteger("123456789123456789", 10);
  var p = new java.math.BigInteger("234567891234567891", 10);
  var g = new java.math.BigInteger("3", 10);
  var v = x.modPow(x, p);
  document.body.innerHTML += '<br>' + v.toString();
  document.body.innerHTML += '<br>' + v.toString(16);
} else {
  document.body.innerHTML += '<br>java plugin not installed';
}
</script></body>

هل يمكن لأي شخص ترجمة هذا الرمز إلى Silverlight (C #)؟

هل كانت مفيدة؟

المحلول

هل ستكون بعض تقنية جانب العميل الأخرى التي يمكن الاتصال بها من JS، مثل تطبيق Java Applet أو فيلم فلاش، مقبولا؟ bigint's نهج هو بالفعل بسرعة إلى حد ما. يمكنك قرص bigint، أو يمكنك تجربة خوارزمية مختلفة, ، ولكن ربما لن تحصل على ترتيب تحسن الحجم.

نصائح أخرى

يمكنني استخدام "٪" للحيوانات (وزارة الدفاع) و "/" لقسم عدد صحيح. دع وظيفة f (p، g، x، r) احسب (r * g ^ x)٪ p على حال ص

bigint_t f(p,g,x,r) {
  bigint_t i, z = g, y;
  for (i = 1; i < x; ++i) {
    y = z; z *= g;
    if (z > p) break;
  }
  if (i >= x - 1) return r*z%p; // g^x*r%p = g^x*r
  else return f(p,y,x/i,g^(x%i)*r%p); // reduce to (r*g^(x%i)%p)*(g^i)^(x/i)%p
}

ينطوي هذا الروتين على حساب أكثر قليلا، ولكن كل عدد صحيح أقل من 4096 بت عادة أصغر بكثير من g ^ x. أعتقد أن هذا قد يكون أكثر كفاءة من الحساب المباشر. لاحظ أيضا أن g ^ (x٪ i) يمكن حسابها بطريقة أسرع لأننا نحسب g ^ (i + 1).

تحرير: انظر. هذا المشنور. وبعد محراد يعطي الحل الأيمن (والأفضل).

لماذا لا تفعل جانب خادم تكنولوجيا المعلومات في نوع من خدمة الويب باستخدام لغة أكثر ملاءمة مثل ج؟ ستكون الأوقات بعد ذلك وقتا لفترة إجتماعية واحدة (أقل من 9 ثوان)، بالإضافة إلى وقت الخادم لحساب النتيجة باستخدام بعض مكتبة Bigint في الرمز الأصلي. من المحتمل أن يكون هذا أسرع بكثير.

جرب هذا التخفيض المعياري مونتغمري http://code.google.com/p/bi2php/ على جافا سكريبت.

أحب أن أرى التعليمات البرمجية المصدر إلى مكتبة الطبق المعدلة الخاصة بك - هل هو متاح في أي مكان؟

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top