اكتشف علماء الرياضيات الطريقة المثلى لمضاعفة الأرقام

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

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

في 18 مارس 2019 ، وصف باحثان أسرع طريقة معروفة لمضاعفة رقمين كبيرين. يمثل العمل تتويجا لبحث طويل الأمد عن الإجراء الأكثر كفاءة لأداء إحدى العمليات الأساسية للرياضيات.

يقول يوريس فان دير هوفن ، عالم الرياضيات في المركز الوطني الفرنسي للبحوث العلمية ، أحد المشاركين في كتابة هذا العمل: "يعتقد الجميع أن طريقة الضرب التي يدرسونها في المدرسة هي الأفضل ، ولكن في الواقع ، يجري البحث النشط في هذا المجال".

إن تعقيد العديد من المشكلات الحسابية ، من عد الأرقام الجديدة من العدد إلى إيجاد أعداد كبيرة ، يخفف من معدل الضرب. يصف Van der Hoeven النتيجة بأنها تعيين نوع من الحد الأقصى للسرعة الرياضية لحل العديد من المشكلات الأخرى.

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

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

تتطلب طريقة المدرسة " نقل " خطوات n ² ، حيث n هو عدد الأرقام في كل من الأرقام المضروبة. تتطلب الحسابات التي تحتوي على أرقام مكونة من ثلاثة أرقام تسعة مضاعفات ، وبأرقام مكونة من رقم واحد ، 10،000.

تعمل طريقة النقل بشكل جيد مع الأرقام التي تتكون من عدة أرقام ، ومع ذلك ، فإنها تبدأ في الانزلاق عند ضرب الأرقام التي تتكون من ملايين أو مليارات الأرقام (وهذا ما تفعله أجهزة الكمبيوتر عند حسابها بدقة π أو عند البحث عن أعداد أولية كبيرة في جميع أنحاء العالم ). لمضاعفة رقمين بمليار رقم ، ستحتاج إلى إنتاج مضاعفات المربعة أو 10 ¹⁸ - وهذا سيستغرق حوالي 30 عامًا لجهاز كمبيوتر حديث.

لعدة آلاف من السنين ، كان يعتقد أنه لا يمكن مضاعفة الأرقام بشكل أسرع. ثم في عام 1960 ، حضر عالم الرياضيات السوفيتي والروسي أناتولي ألكسيفيتش كاراتسوبا ، 23 عامًا ، ندوة أجراها أندريه نيكولاييفيتش كولموغوروف ، عالم رياضيات سوفيتي ، أحد أعظم علماء الرياضيات في القرن العشرين. صرح Kolmogorov أنه لا توجد طريقة عامة للضرب تتطلب أقل من n ² عمليات. قرر كاراتسوبا أن هناك مثل هذه الطريقة - وبعد أسبوع من البحث اكتشفها.


اناتولي الكسيفيتش كاراتسوبا

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


تتطلب طريقة الضرب التقليدية 25x63 أربعة مضاعفات من رقم واحد والعديد من الإضافات


يتطلب الضرب في Karatsuba 25x63 ثلاثة مضاعفات برقم واحد والعديد من الإضافات والطرح.
أ) كسر الأرقام
ب) مضاعفة عشرات
ج) مضاعفة الوحدات
د) إضافة ما يصل الأرقام
ه) ضرب هذه المبالغ
و) النظر ه - ب - ج
ز) جمع إجمالي b و c و f

كلما زاد عدد الأحرف في الأرقام ، يمكن استخدام طريقة Karatsuba بشكل متكرر.


تتطلب الطريقة التقليدية لضرب 2531x1467 16 مضاعفة برقم واحد.


يتطلب الضرب في Karatsuba 2531x1467 9 مضاعفات.

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

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

وقال ديفيد هارفي ، عالم الرياضيات في جامعة نيو ساوث ويلز والمؤلف المشارك للعمل الجديد: "يمكن تحويل عدة مضاعفات إلى إضافات ، نظرًا لأن أجهزة الكمبيوتر ستكون قادرة على القيام بذلك بشكل أسرع".

أتاحت طريقة Karatsuba مضاعفة الأرقام باستخدام مضاعفات n ^1.58 فقط برقم واحد. بعد ذلك ، في عام 1971 ، نشر أرنولد شونهاجي وفولكر شتراسن طريقة لمضاعفة الأعداد الكبيرة عن طريق ضربات n × log n × log (log n). لمضاعفة رقمين من مليار حرف ، ستتطلب كل طريقة Karatsuba 165 تريليون خطوة.


يوريس فان دير هوفن ، عالم رياضيات في المركز الوطني الفرنسي للبحوث العلمية

يتم استخدام طريقة Schönhage-Strassen بواسطة أجهزة الكمبيوتر لمضاعفة أعداد كبيرة ، وقد أدى إلى اثنين من النتائج الهامة الأخرى. أولاً ، قدم تقنية من مجال معالجة الإشارات تسمى Fast Fourier Transform . منذ ذلك الحين ، كانت هذه التقنية هي أساس جميع خوارزميات الضرب السريع.

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

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

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

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

تثبت خوارزمية Harvey و van der Hooven أنه يمكن إجراء الضرب في خطوات n n log. ومع ذلك ، فهو لا يثبت عدم وجود طريقة أسرع. سيكون من الأصعب إثبات أن نهجهم يتم بأسرع وقت ممكن. في نهاية فبراير ، نشر فريق من علماء الكمبيوتر من جامعة آرهوس مقالاً يدعي أنه إذا تبين أن إحدى النظريات غير المؤكدة صحيحة ، فإن هذه الطريقة ستكون بالفعل أسرع طريقة للتكاثر.

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

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

تتغير المعدات بمرور الوقت ، ولكن أفضل خوارزميات من فئتها تستمر إلى الأبد. بغض النظر عن شكل أجهزة الكمبيوتر في المستقبل ، ستظل خوارزمية Harvey و van der Hooven الطريقة الأكثر فاعلية لمضاعفة الأرقام.