في عام 1971، تكهن عالمان رياضيان ألمانيان بأنه سيكون من الممكن ضرب أعداد كبيرة باستخدام طريقة سريعة مذهلة، تعرف باسم خوارزمية شونهاجي_شتراسن. ومع ذلك، ظلت هذه الفكرة المشرقة افتراضية لعدة عقود – حتى الآن.
قام الأستاذ المساعد ديفيد هارفي، وهو عالم رياضيات من جامعة نيو ساوث ويلز (UNSW) في أستراليا، بحل لغز الضرب الذي استمر 48 عامًا والذي اقترحه لأول مرة أرنولد شونهاجي وفولكر شتراسن، وهو إنجاز سيسمح لأجهزة الكمبيوتر بمضاعفة أعداد كبيرة بكفاءة أكبر مع السرعة.
لفهم كيفية عمل هذه الطريقة، عُد بعقلك إلى الطريقة التي تعلمتها بضرب الأرقام في المدرسة الابتدائية. إذا كنت ترغب في ضرب شيء مثل 159 × 314، على سبيل المثال، يمكنك كتابة الرقمين فوق بعضهما البعض، واضرب كل رقم واحد من الرقم مع كل رقم من الرقم الآخر، ثم قم بإضافة الأرقام الجديدة. تتطلب هذه الطريقة حساب 9 عمليات مضاعفة منفصلة.
نظرًا لأن كل من الأرقام في هذا الضرب تحتوي على 3 أرقام (n = 3)، يجب ضرب كل رقم n من الرقم الأول بكل رقم n من الرقم الثاني، وهو ما يعادل n2. في عام 1971، اعتقد كل من شونهاجي وشتراسن أنه من الممكن نظريًا القيام بهذا الضرب بعمليات أقل بكثير، باستخدام عمليات n * log فقط، لكنهما لم يكونا قادرين على إثبات ذلك في ذلك الوقت. يظهر العمل الجديد أن هناك بالفعل خوارزمية تقوم بهذا فقط.
يمكنك قراءة ورقة البحث التي كتبها هارفي ومعاونه يوريس فان دير هوفن من كلية الفنون التطبيقية في فرنسا على أرشيف الوصول المفتوح HAL. تم توضيح ذلك أيضًا بشكل جيد بواسطة هارفي نفسه في الفيديو
وقال هارفي في بيان “لقد توقعوا وجود خوارزمية تضرب الأرقام المكونة من رقم ن باستخدام العمليات الأساسية بشكل أساسي n * log . تقدم ورقتنا أول مثال معروف لخوارزمية تحقق ذلك.”
إذا كان الكمبيوتر يستخدم “طريقة المدرسة الابتدائية” القديمة لمضاعفة رقمين بمليارات من الأرقام لكل منهما، فسيستغرق الأمر شهورًا. ومع ذلك، سوف يستغرق الأمر أقل من 30 ثانية باستخدام خوارزمية شونهاجي_شتراسن.
اقترح شونهاجي وشتراسن أيضًا أن n * log هي “أفضل نتيجة ممكنة”. في الواقع، ستكون هذه أسرع خوارزمية ممكنة للضرب. على الرغم من أن الأمر سيستغرق الكثير من العمل لإثبات ذلك، إلا أنها بالتأكيد فكرة محيرة.
لذلك، كل هذا يبدو مؤثرًا جدًا، لكن ما هو الاستخدام الحقيقي لكل هذا؟ من خلال السماح بضرب أسرع، يمكن للباحثين استخدامه لحساب أرقام pi بشكل أكثر كفاءة من ذي قبل وحل المشكلات التي تنطوي على أعداد أولية ضخمة.
لقد كان الناس يبحثون عن مثل هذه الخوارزمية منذ ما يقرب من 50 عامًا. لم يكن امرا مفروغًا منه بأن احدهم سيكون ناجحا في النهاية”، لخص هارفي. “ربما اتضح أن شونهاجي وشتراسن كانا مخطئين، وأنه لا توجد مثل هذه الخوارزمية الممكنة. ولكننا الآن نعرف ذلك بشكل أفضل.”
رد مع اقتباس
المشاركة الأصلية كتبت بواسطة انثى مخمليةة
