الحوسبة (A * B) وزارة الدفاع C بسرعة ل C = 2 ^ n + -1

Question

في 32 بت عددا صحيح الرياضيات، يتم حساب عمليات الرياضيات الأساسية للإضافة والمضاعفة على وزارة الدفاع الضمنية 2 ^ 32، وهذا يعني أن نتائجك ستكون أدنى أجزاء ترتيب من إضافة أو مضاعفة.

إذا كنت ترغب في حساب النتيجة مع وحدة معامل مختلفة، فيمكنك بالتأكيد استخدام أي عدد من فئات Bigint بلغات مختلفة. وللقيم A، B، C <2 ^ 32، يمكنك حساب القيم الوسيطة في INTS طويل 64 بت واستخدم مشغلي٪ مضمن للحد من الإجابة الصحيحة

لكن قيل لي أن هناك حيل خاصة للحوسبة بكفاءة * B وزارة الدفاع C عندما تكون C من النموذج (2 ^ n) -1 أو (2 ^ n) +1، لا تستخدم 64 بت الرياضيات أو مكتبة Bigint وفعالة للغاية، أكثر من تقييم التعريف التعسفي، وكذلك حساب الحالات بشكل صحيح والتي من شأنها أن تتجاوز عادة ANT 32 بت إذا كنت بما في ذلك الضرب الوسيط.

لسوء الحظ، على الرغم من سماع أن هذه الحالات الخاصة لها طريقة تقييم سريعة، لم أجد بالفعل وصفا للطريقة. "أليس كذلك في الرنوث؟" "أليس كذلك في مكان ما على ويكيبيديا؟" هي الحبوبة التي سمعتها.

يبدو أنها تقنية شائعة في مولدات الأرقام العشوائية التي تقوم بتوزيض A * B Mod 2147483647، حيث 2147483647 هو رقم رئيسي يساوي 2 ^ 31 -1.

لذلك سأطلب الخبراء. ما هي طريقة مضاعفة الحالة الخاصة الذكية مع وزارة الدفاع التي لا يمكنني العثور عليها أي مناقشة؟

Answer 1

أعتقد أن الحيلة هي التالية (سأقوم بذلك في قاعدة 10، لأنه أسهل، لكن يجب أن يحتفظ المبدأ)

لنفترض أنك تتضاعف a*b mod 10000-1, ، و

a = 1234 = 12 * 100 + 34
b = 5432 = 54 * 100 + 32

حاليا a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 =  648 * 10000
34 * 54 * 100   = 1836 * 100
12 * 32 * 100   =  384 * 100
34 * 32         = 1088

حيث x * 10000 ≡ x (mod 10000-1) 1]، والشروط الأولى والأخيرة تصبح 648 + 1088. الشروط الثانية والثالثة هي المكان الذي تأتي فيه "خدعة". لاحظ أن:

1836 = 18 * 100 + 36
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1).

هذا هو أساسا تحول دائري. إعطاء نتائج 648 + 3618 + 8403 + 1088. وألاحظ أيضا أنه في جميع الحالات، فإن الأرقام الضخمة هي <10000 (نظرا لأن <100 و B <100)، لذلك هذا قابل للحساب إذا كنت تستطيع فقط عدة أرقام رقمين معا وأضفهم.

في ثنائي، ستنجح بالمثل.

ابدأ ب A و B، كلاهما 32 بت. افترض أنك تريد أن تضاعفها وزارة الدفاع 2 ^ 31 - 1، ولكن لديك فقط مضاعف 16 بت (إعطاء 32 بت). ستكون الخوارزمية شيئا مثل هذا:

 a = 0x12345678
 b = 0xfedbca98
 accumulator = 0
 for (x = 0; x < 32; x += 16)
     for (y = 0; y < 32; y += 16)
         // do the multiplication, 16-bit * 16-bit = 32-bit
         temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF)

         // add the bits to the accumulator, shifting over the right amount
         total_bits_shifted = x + y
         for (bits = 0; bits < total_bits_shifted + 32; bits += 31)
             accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF

         // do modulus if it overflows
         if (accumulator > 0x7FFFFFFFF)
             accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF);

في وقت متأخر، لذلك جزء تراكم من ذلك ربما لن يعمل. أعتقد أنه من حيث المبدأ فمن الصحيح رغم ذلك. شخص ما لا يشعر بحرية تحرير هذا لجعله صحيحا.

غير منضبطة، وهذا سريع جدا، وكذلك، ما هو استخدام PRNG، أنا أظن.

1]: x * 10000 ≡ x * (9999 + 1) ≡ 9999 * x + x ≡ x (mod 9999)

Answer 2

لنفترض أنه يمكنك حساب A * B p*2^N+q. وبعد يمكن أن يتطلب ذلك من حساب 64 بت، أو يمكنك تقسيم A و B إلى أجزاء 16 بت وحسب حسابي على 32 بت.

ثم a*b mod 2^N-1 = p+q mod 2^N-1 حيث 2^N mod 2^N-1 = 1.

و a*b mod 2^N+1 = -p+q mod 2^N+1 حيث 2^N mod 2^N+1 = -1.

في كلتا الحالتين، لا يوجد قسم 2^N-1 أو 2^N+1.

Answer 3

تحول البحث السريع هذا: http://home.pipeline.com/~hbaker1/ab-mod-n.pdf.. وبعد لسوء الحظ، فقد فات الأوان بالنسبة لي إحساسا كافيا بهذا ما يكتب في الصيغة المبسطة، ولكن ربما في تلك الورقة في مكان ما.

Answer 4

بدلا من القيام بالحد المعياري في كل خطوة، يمكنك استخدام الحد من مونتغمري (هناك المزيد أوصاف) للحد من تكلفة حساب الضرب المعياري. لا يزال هذا لا يستخدم خصائص N يجري زائد / ناقص قوة اثنين، رغم ذلك.

Answer 5

الهوية التي تبحث عنها هي x mod N = (x mod 2^q)- c*floor(x/2^q), ، بشرط N = 2^q + c و C هو أي عدد صحيح (ولكن عادة ± 1).

قد ترغب في القراءة القسم 9.2.3: "Moduli من النموذج الخاص" في "الأرقام الرئيسية: منظور حسابي" بواسطة ريتشارد كراندال و Carl Pomerance. إلى جانب النظرية، يحتوي على pseudocode لخوارزمية تنفذ العلاقة المذكورة أعلاه.

Answer 6

لقد وجدت صفحة مكثفة إلى حد ما في هذا الموضوع جدا، لا تناقش الخوارزمية فقط ولكن حتى المحددة التاريخ من المشكلة والحلول والطريقة التي استخدمها الناس الحل.