حساب مربع سريع bignum

تهدف هذه المقالة إلى تحديد أسرع طريقة للحساب y = x^2 لـ bigints معبراً عنها كصفوف ديناميكية من dwords غير الموقعة. dwords:

dword x [n 1] = {lsw ، ...... ، msw} ؛

حيث:

DWORD x[n 1] = { LSW, ......, MSW };

ابحث عن قيمة y = x^2 في أسرع وقت ممكن دون فقدان الدقة. (o (n^2) الضرب)

• ينطوي النهج الساذج على ضرب x بمفرده ، والذي يستغرق وقتًا في (n^2). يمكن التعبير عن ذلك على النحو التالي:
• y = x * x y = (x0 x1 x2 ... xn)*(x0 x1 x2 ... xn)

y1 = x1*x0 x0*x1 y2 = x2*x0 x1*x1 x0*x2 y3 = x3*x0 x2*x1 x1*x2 ... y (2n-3) = xn (n-2)*x (n) x (n-1)*x (n-1) x (n)*x (n-2) y (2n-2) = xn (n-1)*x (n) x (n)*x (n-1) y (2n-1) = xn (n)*x (n)

karatsuba الضرب

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