خوارزمية كاراتسوبا

المبدأ الأساسي لخوارزمية كاراتسوبا هو فرق تسد ، باستخدام صيغة تسمح بحساب حاصل ضرب عددين كبيرين${\displaystyle x}$و${\displaystyle y}$باستخدام ثلاث عمليات ضرب لأعداد أصغر، كل منها يحتوي على نصف عدد الأرقام تقريبًا${\displaystyle x}$أو${\displaystyle y}$بالإضافة إلى بعض عمليات الجمع وإزاحة الأرقام. هذه الخطوة الأساسية هي في الواقع تعميم لخوارزمية ضرب الأعداد المركبة المماثلة ، حيث يتم استبدال الوحدة التخيلية i بقوة من قوى الأساس .

يترك${\displaystyle x}$و${\displaystyle y}$يتم تمثيله على النحو التالي:${\displaystyle n}$سلاسل مكونة من - أرقام في نظام أساسي ما${\displaystyle B}$لأي عدد صحيح موجب${\displaystyle m}$أقل من${\displaystyle n}$يمكن كتابة الرقمين المعطاينين ​​على النحو التالي:

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

أين${\displaystyle x_{0}}$و${\displaystyle y_{0}}$أقل من${\displaystyle B^{m}}$ثم يصبح المنتج

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

أين

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

تتطلب هذه الصيغ أربع عمليات ضرب، وكانت معروفة لتشارلز باباج . ^{[ 4 ]} لاحظ كاراتسوبا أن${\displaystyle xy}$يمكن حسابها بثلاث عمليات ضرب فقط، مع إضافة بضع عمليات جمع إضافية.${\displaystyle z_{0}}$و${\displaystyle z_{2}}$كما كان من قبل و${\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}$يلاحظ المرء أن

${\displaystyle {\begin{alignat}{2}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_{1}+x_{1}y_{1}+x_{0}y_{0}&&-x_{1}y_{ 1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{1}+y_{0})&&-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{alignat}}}$

وبالتالي، لا يلزم سوى ثلاث عمليات ضرب لإجراء الحساب${\displaystyle z_{0},z_{1}}$و${\displaystyle z_{2},}$وبالتالي${\displaystyle xy.}$

يستخدم شكل بديل${\displaystyle z_{4}=(x_{1}-x_{0})(y_{1}-y_{0})}$بدلاً من:

${\displaystyle {\begin{align}z_{1}&={\phantom {x_{1}y_{1}+x_{0}y_{0}-(x_{1}y_{1}-x_{0}y_{0}+{}}}x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{1}+x_{0}y_{0}-{\phantom {(}}x_{1}y_{1}-x_{0}y_{0}+x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{1}+x_{0}y_{0}-(x_{1}y_{1}+x_{0}y_{0}-x_{1}y_{ 0}-x_{0}y_{1})\\&=x_{1}y_{1}+x_{0}y_{0}-(x_{1}-x_{0})(y_{1}-y_{0})\\&=z_{2}+z_{0}-z_{4}.\\\end{محاذاة}}}$

لحساب حاصل ضرب 12345 و 6789، حيث B = 10، اختر m = 3. نستخدم m إزاحة لليمين لتحليل معاملات الإدخال باستخدام الأساس الناتج ( B ^m = 1000 )، كما يلي:

12345 = 12 × 1000 + 345

6789 = 6 × 1000 + 789

يتم استخدام ثلاث عمليات ضرب فقط، والتي تعمل على أعداد صحيحة أصغر، لحساب ثلاث نتائج جزئية:

z ₂ = 12 × 6 = 72

z ₀ = 345 × 789 = 272205

ض ₁ = ( 12 + 345 ) × ( 6 + 789 ) − ض ₂ − ض ₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

نحصل على النتيجة بمجرد جمع هذه النتائج الجزئية الثلاث، مع إزاحتها وفقًا لذلك (ثم نأخذ عمليات الحمل في الاعتبار عن طريق تحليل هذه المدخلات الثلاثة في الأساس 1000 كما هو الحال بالنسبة لمعاملات الإدخال):

النتيجة = z² · ( Bm ^{) ²} + z¹ _· ( Bm ^{) ¹} + z⁰ _· ( Bm ^{) ⁰} ، أي_​

النتيجة = 72 × 1000 ² + 11538 × 1000 + 272205 = 83810205 .

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

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

في حاسوب مزود بمضاعف كامل 32 بت × 32 بت ، على سبيل المثال، يمكن اختيار B = 2^ ³¹ وتخزين كل رقم ككلمة ثنائية منفصلة مكونة من 32 بت. عندئذٍ، لن تحتاج عمليتا الجمع x1 + x0 و y1 + _y0 إلى كلمة ثنائية إضافية _{لتخزين رقم} الترحيل (كما هو الحال في _جامع حفظ الترحيل )، ويمكن تطبيق تكرار كاراتسوبا حتى يصبح طول الأرقام المراد ضربها رقمًا واحدًا فقط.

تُجدي الخطوة الأساسية في خوارزمية كاراتسوبا مع أي أساس B وأي قيمة لـ m ، لكن الخوارزمية التكرارية تكون أكثر كفاءة عندما تكون m مساوية لـ n /2، مُقرّبةً لأعلى. على وجه الخصوص، إذا كانت n تساوي ^2k ، حيث k عدد صحيح ، ويتوقف التكرار فقط عندما تكون n تساوي 1، فإن عدد عمليات الضرب في خانة واحدة هو 3k ^، وهو nc حيث c = ^log₂ ₃ .

بما أنه يمكن تمديد أي مدخلات ذات أرقام صفرية حتى يصبح طولها قوة من قوى العدد اثنين، فإنه يترتب على ذلك أن عدد عمليات الضرب الأولية، لأي قيمة لـ n ، يكون على الأكثر${\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}$.

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

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

لبعض الثوابت c و d . بالنسبة لعلاقة التكرار هذه ، تعطي النظرية الرئيسية لتكرارات فرق تسد الحد التقاربي${\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}$.

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