خوارزمية الضرب

يستخدم هذا المثال الضرب الطويل لضرب 23,958,233 (المضروب) في 5,830 (المضروب فيه) ويصل إلى 139,676,498,390 كنتيجة (ناتج).

 23958233 × 5830 ——————————————— 00000000 ( = 23,958,233 × 0) 71874699 ( = 23,958,233 × 30) 191665864 ( = 23,958,233 × 800) + 119791165 ( = 23,958,233 × 5,000) ——————————————— 139676498390 ( = 139,676,498,390)

23958233 · 5830 ——————————————— 119791165 191665864 71874699 00000000 ——————————————— 139676498390

اضرب ( أ [ 1..ص ] ، ب [ 1..ق ] ، الأساس ) // المعاملات التي تحتوي على الأرقام الموجودة في أقصى اليمين عند الفهرس 1product = [ 1 .. p + q ] // تخصيص مساحة للنتيجةfor b_i = 1 to q // for all digits in bالحمل = 0for a_i = 1 to p // for all digits in aproduct [ a_i + b_i - 1 ] += carry + a [ a_i ] * b [ b_i ]الحمل = حاصل ضرب [ أ_i + ب_i - 1 ] / الأساسحاصل ضرب [ a_i + b_i - 1 ] = حاصل ضرب [ a_i + b_i - 1 ] mod القاعدةحاصل ضرب [ b_i + p ] = حمل // الرقم الأخير يأتي من الحمل النهائيإرجاع المنتج

تُنفّذ بعض الرقاقات عملية الضرب الطويل، إما في مكوناتها المادية أو في شفرتها البرمجية ، لأحجام كلمات مختلفة للأعداد الصحيحة والأعداد العشرية. في العمليات الحسابية ذات الدقة العشوائية ، يشيع استخدام الضرب الطويل مع ضبط الأساس على 2^ ^w ، حيث w هو عدد البتات في الكلمة، لضرب أعداد صغيرة نسبيًا. لضرب عددين مكونين من n خانة باستخدام هذه الطريقة، نحتاج إلى حوالي n^ ² عملية. وبشكل أدق، يتطلب ضرب عددين مكونين من n خانة باستخدام الضرب الطويل Θ ( n^ ² ) عملية أحادية الخانة (جمع وضرب).

عند تطبيق خوارزميات الضرب الطويلة في البرمجيات، يجب التعامل مع تجاوز السعة أثناء عمليات الجمع، وهو ما قد يكون مكلفًا. يتمثل الحل النموذجي في تمثيل العدد بأساس صغير، b ، بحيث يكون، على سبيل المثال، 8b عددًا صحيحًا قابلًا للتمثيل آليًا. يمكن بعد ذلك إجراء عدة عمليات جمع قبل حدوث تجاوز السعة. عندما يصبح العدد كبيرًا جدًا، نضيف جزءًا منه إلى النتيجة، أو نحمل الجزء المتبقي ونعيده إلى عدد أقل من b . تُسمى هذه العملية بالتطبيع . استخدم ريتشارد برنت هذا النهج في حزمة فورتران الخاصة به، MP. ^{[ 2 ]}

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

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

(( x << 2 ) + x ) << 1 # هنا يتم حساب 10*x على النحو التالي: (x*2^2 + x)*2 ( x << 3 ) + ( x << 1 ) # هنا يتم حساب 10*x على النحو التالي: x*2^3 + x*2

في بعض الحالات، تتفوق هذه التسلسلات من عمليات الإزاحة والجمع أو الطرح على مضاعفات الأجهزة، وخاصةً وحدات القسمة. القسمة على عدد من الشكل${\displaystyle 2^{n}}$أو${\displaystyle 2^{n}\pm 1}$غالباً ما يمكن تحويلها إلى تسلسل قصير كهذا.

طريقة الشبكة ( أو طريقة المربعات) هي طريقة تمهيدية لضرب الأعداد متعددة الأرقام ، وغالبًا ما تُدرَّس للتلاميذ في المرحلة الابتدائية . وقد أصبحت جزءًا أساسيًا من منهج الرياضيات الوطني للمرحلة الابتدائية في إنجلترا وويلز منذ أواخر التسعينيات. ^{[ 3 ]}

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

على سبيل المثال، يمكن حساب العملية الحسابية 34 × 13 باستخدام الشبكة:

 300 40 90 + 12 ———— 442

ثم يتم الجمع للحصول على 442، إما في مجموع واحد (انظر إلى اليمين)، أو من خلال تكوين المجاميع صفًا تلو الآخر

(300 + 40) + (90 + 12) = 340 + 102 = 442.

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

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

تُعدّ عملية الضرب الشبكي، أو الغربالي، مكافئةً خوارزميًا لعملية الضرب المطوّل. تتطلب هذه العملية إعداد شبكة (مخطط مرسوم على الورق) تُوجّه الحساب وتفصل عمليات الضرب عن عمليات الجمع . وقد عُرفت هذه الطريقة في أوروبا عام ١٢٠٢ في كتاب فيبوناتشي " ليبر أباتشي" . وصف فيبوناتشي العملية بأنها ذهنية، حيث استخدم يديه اليمنى واليسرى لإجراء العمليات الحسابية الوسيطة. قدّم ماتراكجي ناسوح ستة أشكال مختلفة لهذه الطريقة في كتابه "عمدة الحساب" الذي يعود إلى القرن السادس عشر. وقد شاع استخدامها في مدارس إندرون في جميع أنحاء الإمبراطورية العثمانية. ^{[ ٤ ]} كما استخدمت عظام نابيير ، أو قضبان نابيير، هذه الطريقة أيضًا، كما نشرها نابيير عام ١٦١٧، وهو عام وفاته.

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

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

 2 3 9 5 8 2 3 3 +---+---+---+---+---+---+---+---+- |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /| | / | / | / | / | / | / | / | / | 5 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5| +---+---+---+---+---+---+---+---+- |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /| | / | / | / | / | / | / | / | / | 8 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4| +---+---+---+---+---+---+---+---+- |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 3 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9| +---+---+---+---+---+---+---+---+- |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /| | / | / | / | / | / | / | / | / | 0 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0| +---+---+---+---+---+---+---+---+- 26 15 13 18 17 13 09 00

01 002 0017 ٠٠٠٢٤ 000026 0000015 00000013 000000018 0000000017 00000000013 000000000009 0000000000000 ————————————— 139676498390 

= 139,676,498,390

تُعرف الطريقة الثنائية أيضًا باسم ضرب الفلاحين، نظرًا لاستخدامها الواسع بين عامة الناس الذين لم يحفظوا جداول الضرب اللازمة للضرب المطوّل. ^{[ 5 ]} وقد استُخدمت هذه الخوارزمية في مصر القديمة. ^{[ 6 ]} من أهم مزاياها سهولة تعلمها، وعدم حاجتها للحفظ، وإمكانية تطبيقها باستخدام رموز، مثل رقائق البوكر ، في حال عدم توفر الورق والقلم. أما عيبها، فهو أنها تتطلب خطوات أكثر من الضرب المطوّل، مما يجعلها غير عملية للأعداد الكبيرة.

عشري: ثنائي: 11 3 1011 11 5 6 101 110 2 12 10 1100 1 24 1 11000 —— —————— 33 100001

عشري: ثنائي: 5830 23958233 1011011000110 1011011011001001011011001 2915 47916466 101101100011 10110110110010010110110010 1457 95832932 10110110001 101101101100100101101100100 728 191665864 1011011000 1011011011001001011011001000 364 383331728 101101100 10110110110010010110110010000 182 766663456 10110110 101101101100100101101100100000 91 1533326912 1011011 1011011011001001011011001000000 45 3066653824 101101 10110110110010010110110010000000 22 6133307648 10110 101101101100100101101100100000000 11 12266615296 1011 1011011011001001011011001000000000 5 24533230592 101 10110110110010010110110010000000000 2 49066461184 10 101101101100100101101100100000000000 1 98132922368 1 1011011011001001011011001000000000000 ———————————— 1022143253354344244353353243222210110 (قبل الحمل) 139676498390 10000010000101010111100011100111010110

يمكن استخدام هذه الصيغة في بعض الحالات لتسهيل إكمال عمليات الضرب:

${\displaystyle {\frac {\left(x+y\right)^{2}}{4}}-{\frac {\left(xy\right)^{2}}{4}}=\left({\frac {x+y}{2}}\right)^{2}-\left({\frac {xy}{2}}\right)^{2}=xy}$

في الحالة التي${\displaystyle x}$و${\displaystyle y}$بما أن هي أعداد صحيحة، فإن

${\displaystyle (x+y)^{2}\equiv (xy)^{2}{\bmod {4}}}$

لأن${\displaystyle x+y}$و${\displaystyle xy}$إما أن يكون كلاهما زوجيًا أو كلاهما فرديًا. هذا يعني أن

${\displaystyle {\begin{aligned}xy&={\frac {1}{4}}(x+y)^{2}-{\frac {1}{4}}(xy)^{2}\\&=\left((x+y)^{2}{\text{ div }}4\right)-\left((xy)^{2}{\text{ div }}4\right)\end{aligned}}}$

ويكفي (مسبقًا) حساب الجزء الصحيح من المربعات المقسومة على 4 كما في المثال التالي.

عملية الضرب في كاراتسوبا هي خوارزمية فرق تسد من النوع O( n ^{log ₂ 3} ) ≈ O( n ^1.585 )، والتي تستخدم التكرار لدمج العمليات الحسابية الفرعية.

بإعادة كتابة الصيغة، يصبح من الممكن إجراء حسابات فرعية/استدعاء ذاتي. وباستخدام الاستدعاء الذاتي، يمكن حل هذه المسألة بسرعة.

يترك${\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}.}$

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

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

بسبب تكلفة الاستدعاء الذاتي، فإن عملية الضرب في كاراتسوبا أبطأ من عملية الضرب الطويلة للقيم الصغيرة لـ n ؛ لذلك تتحول التطبيقات النموذجية إلى عملية الضرب الطويلة للقيم الصغيرة لـ n .

تُعرف طريقة أخرى للضرب باسم "توم-كوك" أو "توم-3". تقوم هذه الطريقة بتقسيم كل عدد مُراد ضربه إلى عدة أجزاء. وتُعدّ "توم-كوك" إحدى تعميمات طريقة "كاراتسوبا". يُمكن لـ"توم-كوك" الثلاثية إجراء عملية ضرب بحجم 3N بتكلفة خمس عمليات ضرب بحجم N. يُسرّع هذا العملية بمقدار 9/5، بينما تُسرّعها طريقة "كاراتسوبا" بمقدار 4/3.

على الرغم من أن استخدام المزيد من الأجزاء قد يقلل الوقت المستغرق في عمليات الضرب المتكررة، إلا أن العبء الإضافي الناتج عن عمليات الجمع وإدارة الأرقام يزداد أيضًا. لهذا السبب، تُعدّ طريقة تحويل فورييه أسرع عادةً للأعداد التي تتكون من عدة آلاف من الأرقام، وتزداد سرعتها تدريجيًا مع ازدياد حجم الأعداد.

يمكن كتابة كل عدد في النظام العددي (الأساس B) على شكل متعدد الحدود:

$${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$$

علاوة على ذلك، يمكن اعتبار عملية ضرب عددين بمثابة حاصل ضرب كثيرتي حدود:

$${\displaystyle XY=(\sum _{i=0}^{N}{x_{i}B^{i}})\,(\sum _{j=0}^{N}{y_{i}B^{j}})}$$

بما أن معامل ⁠${\displaystyle B^{k}}$المنتج​$${\displaystyle z_{k}=\sum _{(i,j):i+j=k}{x_{i}y_{j}}=\sum _{i=0}^{k}{x_{i}y_{k-i}},}$$ أحدهما يحتوي على عملية التفاف، والآخر يمكنه استخدام تحويل فورييه السريع (FFT): $${\displaystyle {\hat {f}}(XY)={\hat {f}}(\sum _{i=0}^{k}{x_{i}y_{k-i}})={\hat {f}}(X)\cdot {\hat {f}}(Y).}$$

وبالتالي، يتم اختزال عملية الضرب إلى تحويل فورييه السريع (FFT) .${\displaystyle N}$عمليات الضرب، وعكس تحويل فورييه السريع. ينتج عن ذلك تعقيد زمني قدره O ( n  log( n )  log(log n )) .

في عام 2007، قام عالم الرياضيات السويسري مارتن فورر من جامعة ولاية بنسلفانيا بتحسين التعقيد التقاربي لعملية ضرب الأعداد الصحيحة إلى${\textstyle O(n\log n\cdot {2}^{\Theta (\log ^{*}(n))})}$باستخدام تحويلات فورييه على الأعداد المركبة ، ^{[ 18 ]} حيث يرمز log ^{* إلى} اللوغاريتم المتكرر . قدّم أنينديا دي، وتشاندان ساها، وبيوش كورور، ورامبراساد سابثارشي خوارزمية مشابهة باستخدام الحساب النمطي في عام 2008، محققين نفس زمن التشغيل. ^{[ 19 ]} في سياق ما سبق، ما حققه هؤلاء المؤلفون هو إيجاد N أقل بكثير من 2 ^ ^{(3k +} 1)، بحيث يكون لـ Z / NZ جذر من الرتبة (2^ m ) للوحدة. هذا يُسرّع الحساب ويقلل من التعقيد الزمني. مع ذلك، فإن هذه الخوارزميات الأخيرة أسرع من خوارزمية شونهاج-ستراسن فقط للمدخلات الكبيرة جدًا وغير العملية.

في عام 2014، قدم هارفي وجوريس فان دير هوفن وليسيرف ^{[ 20 ]} خوارزمية جديدة تحقق زمن تشغيل قدره${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$، مما يوضح الثابت الضمني في${\displaystyle O(\log ^{*}n)}$كما اقترحوا نسخة معدلة من خوارزميتهم تحقق${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$لكن صحتها تعتمد على تخمينات قياسية حول توزيع أعداد ميرسين الأولية . في عام 2016، اقترح كوفانوف وتومي خوارزمية لضرب الأعداد الصحيحة تعتمد على تعميم لأعداد فيرما الأولية ، والتي تحقق، على ما يبدو، حدًا أقصى للتعقيد قدره${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$يتطابق هذا مع النتيجة الشرطية التي توصل إليها هارفي وفان دير هوفن وليسيرف عام 2015، ولكنه يستخدم خوارزمية مختلفة ويعتمد على تخمين مختلف. ^{[ 21 ]} في عام 2018، استخدم هارفي وفان دير هوفن نهجًا قائمًا على وجود متجهات شبكية قصيرة مضمونة بنظرية مينكوفسكي لإثبات حد تعقيد غير مشروط قدره${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$[ ^{22 ]​}

في مارس 2019، أعلن ديفيد هارفي وجوريس فان دير هوفن عن اكتشافهما لخوارزمية ضرب من رتبة O ( n log n ) . ^{[ 23 ]} نُشرت هذه الخوارزمية في مجلة حوليات الرياضيات عام 2021. ^{[ 14 ]} ولأن شونهاج وستراسن توقعا أن n  log( n ) هي "أفضل نتيجة ممكنة"، قال هارفي: "...  من المتوقع أن يكون عملنا بمثابة نهاية المطاف لحل هذه المشكلة، على الرغم من أننا لا نعرف حتى الآن كيفية إثبات ذلك بدقة." ^{[ 24 ]} ومع ذلك، فإن الخوارزمية الجديدة غير عملية إلى حد كبير: فهي أسرع من خوارزمية شونهاج-ستراسن فقط إذا تجاوز عدد الأرقام n log n. ^{[ 14 ]}

${\displaystyle {\begin{aligned}2^{{1729}^{12}}&=2^{713\,739\,807\,325\,663\,489\,766\,475\,852\,620\,783\,120\,641}\\&\approx 4.145331\times 10^{214\,857\,091\,104\,455\,254\,035\,802\,532\,723\,729\,912\,717}\\&\approx 10^{2.148571\times 10^{38}}.\end{aligned}}}$

يوجد حد أدنى بسيط لـ Ω ( n ) لضرب عددين من n بت على معالج واحد؛ ولا توجد خوارزمية مطابقة معروفة (على الأجهزة التقليدية، أي على أجهزة تورينج المكافئة) ولا أي حد أدنى أدق. وتفترض فرضية هارتمانيس-ستيرنز أن${\displaystyle O(n)}$لا يمكن تحقيق ذلك. تقع عملية الضرب خارج نطاق AC ⁰ [ p ] لأي عدد أولي p ، مما يعني عدم وجود مجموعة من الدوائر ذات العمق الثابت، والحجم متعدد الحدود (أو حتى شبه الأسي) باستخدام بوابات AND وOR وNOT وMOD _{p التي يمكنها حساب ناتج الضرب. وينتج هذا عن اختزال MOD q} إلى عملية ضرب ذات عمق ثابت . ^{[ 25 ]} كما تُعرف حدود دنيا لعملية الضرب لبعض فئات برامج التفرع . ^{[ 26 ]}

• طرق الحساب المتعددة في الرياضيات اليومية في برنامج UCSMP
• عرض تقديمي باستخدام برنامج باوربوينت حول الرياضيات القديمة
• فيديو تعليمي لضرب الشبكة

• خوارزميات الضرب المستخدمة في GMP