ضرب عدد صحيح سريع باستخدام الجداول

أريد أن أخبر القراء عن خدعة برمجة قابلتهم في نوع من كتاب الترجمة الذي يحتوي على مجموعة مختارة من هذه الحيل في تلك الأيام التي لم يخترع فيها البايت فقط ، ولكن من المخيف أن نقول المكدس ، وما زال Dijkstra العظيم لا يلعن المشغل غوتو (كذا ، بأحرف كبيرة).

أعجبتني الحيلة كثيراً ببساطتها ونعمتها ، حيث أنني كنت سعيدًا بالفعل في هذه الألفية بإخبار الطلاب عنها في شكل المهمة التالية.

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

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

لكن إلى هذه النقطة. أنت بحاجة ماسة إلى تطبيق الضرب برمجيًا حتى يعمل بسرعة في الوقت الفعلي ويناسب موردًا متاحًا.

من خلال الحساب المدرسي ، نذكر أنه يمكن ضرب الأرقام متعددة القيم بعمود ، ويمكن أخذ نتيجة ضرب الأرقام الفردية من جدول الضرب.

لكن فقط إذا تم اختيار الأرقام باختصار (على سبيل المثال ، 0 و 1) ، فسيكون جدول الضرب قصيرًا والأعمدة طويلة ، وسيستغرق حسابها الكثير من الوقت.

على العكس ، إذا أخذنا أرقامًا طويلة (على سبيل المثال ، من 0 إلى 65535) ، فحينئذٍ لحساب 16 بت
يتم أخذ النتيجة مباشرة من الجدول ، والأعمدة مفقودة. ومع ذلك ، فإن حجم طاولة فيثاغورس الكلاسيكية يتحول إلى حوالي 17 جيجابايت (4 * 65536 * 65536) ، إذا أخذنا في الاعتبار التماثل فيما يتعلق قطري ، ثم نصف حوالي 8.5 جيجابايت.

قد يكون قليلا جدا.

تشديد وتذكر الجبر.

$$$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$(1)

$$$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$(2)

طرح (2) من (1)

$$$(a + b) ^ 2 - (a - b) ^ 2 = 4ab$

و اكثر

$$$a b = ((a + b) ^ 2 - (a - b) ^ 2) / 4$

وبالتالي ، لدينا جدول المربعات في مجموعة sqr ، نحصل عليها

a * b = (sqr [a + b] - sqr [a - b]) / 4 (*)

حجم الجدول 8 * (65535 + 65535) حوالي 8.4 ميغابايت ، وهو ما قد يكون مقبولًا بالفعل.

يرجع حجم عنصر الجدول المكون من 8 بايتات إلى حقيقة أنه بالنسبة إلى الحد الأقصى a و b ، لا يصلح مربع مجموع البايتات الخاص بهما - 2 بت غير كافية.

بعد ذلك ، سوف أصف بعض التحسن الذي لم يكن في الكتاب. لقد توصلت إلى ذلك بنفسي عندما كنت أكتب هذه الملاحظة بالفعل.

لاحظ أن البتات الأقل دلالة في المربع الزوجي هي دائمًا 00 ، والمربع الغريب هو 01 دائمًا. ومن ناحية أخرى ، بالنسبة لأي زوج من الأرقام ، يكون مجموعهما وفرقهما متساويان.
لذلك ، في صيغتنا (*) ، لا يمكن أن تتضمن عملية الطرح بين الأقواس الواصلات ،
يرتبط مع اثنين من الأقل بت أهمية. لذلك ، فإن محتويات عناصر الجدول مربع
يمكنك التقدم بتين إلى اليمين ومن ثم حفظ نصف الذاكرة.

وأخيرا لدينا

a * b = sqr4 [a + b] - sqr4 [a - b] (**)

حيث sqr4 هو جدول المربعات المعدلة.

في مثالنا ، حجمها حوالي 4.2 ميغابايت.

أدناه لتوضيح هذا النهج ، يتم تضمين نص برنامج لوا.

function create_multiplier(N) -- N     local sqr4 = {} --   for i = 1, 2 * N - 1 do local temp = 0 for j = 1, i - 1 do --    temp = temp + i - 1 --    end -- ..  "" sqr4[i] = math.floor(temp / 4) --  2  end return --   () function (i, j) if i < j then i, j = j, i end return sqr4[1 + i + j] - sqr4[1 + i - j] end end N = 256 mpy = create_multiplier(N) for i = 0, N - 1 do for j = 0, N - 1 do if i * j ~= mpy(i,j) then print("", i, j, i * j, mpy(i,j)) end end end print(" .") 

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

سأكون ممتنًا لجميع قراء هذه المذكرة للتصحيحات والتعليقات.