نعلم من السنوات المدرسة الأولى ان عملية الجمع اسهل من عملية الضرب. فاذا كان علينا ان نضرب عددين كلاهما من 8 خانات في بعضهما أو نجعمهما فان الجمع هى العملية الأيسر؟ مثلا اذا كان علينا ان نضرب 86406524 في 86452419 أو  نجمعهما فمن السهل ان ترى ان عملية الجمع هي الأسهل.وان شككت فى ذلك فعليك ان تقوم بهاتين العمليتين لتلمس الفارق بنفسك! لكن لماذا؟ لأننا ببساطة فى عملية الجمع علينا ان نجمع ثمانية أزواج من الأعداد المفردة لنصل الى النتيجة النهائية. لكن لانهاء عملية الضرب علينا ان نضرب كل رقم فى أحد العددين فى كل رقم من العدد الأخر. وعمليات الضرب وحدها عبارة عن 64 عملية. ثم تتبعها عمليات الجمع العديدة

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

وموضوع اليوم  يتناول هذا الأمر وكيف يتعامل علماء المعلومات Information scientests معه بل وكيف يصفونه رياضيا.  فى البداية دعونا نقرر الحقائق التالية:

1 نحن نعرف جدول الضرب. أذن عندما نحتاج لضرب عددين كلاهما من خانة واحدة علينا ان نقوم بخطوة واحدة فقط وهى ان نستدعى تلك النتيجة من الذاكرة. فلضرب 7 فى 5 علينا فقط ان نتذكر ان النتيجة هى 35 .
2 كما أن هناك جدولا للضرب فان هناك أيضا جدولا للجمع وان كنا لا نطلق عليه هذا الأسم. ولجمع عددين كلاهما من خانة واحدة علينا ان نسترجع تلك النتيجة من الذاكرة فمجموع 7 زائد 5 يساوي 12 . لكن علماء المعلومات يفترضون هنا شيئا مباغتا. فهم يقولون اننا فى خطوة واحدة نستطيع ان نجمع ثلاثة اعداد من خانة واحد وليس عددين فقط بشرط ان يكون احد تلك الأعداد هو الصفر أو الواحد!! لماذا اذن هذا الأفتراض العجيب. الأجابة ببساطة لأن الدوائر الالكترونية Adder للحاسوب تلبى هذه الخاصية ! لكن ما هي الحكمة من وراء ذلك؟ فى الحقيقة ان الامر يعتمد على السياق اللذى نجرى من خلاله عملية الجمع. مثلا اذا كان هدفنا ان نجمع 7 زائد 5 ولا شئ اكثر من ذلك. فيمكننا ان نتخيل اننا نجمع 7 زائد 5 زائد 0. فالنتيجة لن تتغير. لكنننا فى احوال كثيرة نجمع هذين العددين لاننا نبحث أصلا عن مجموع عددين ك 79 زائد 59 . فعندما نجمع ال 7 زائد 5 يكون ذلك بعد ان جمعنا ال 9 على 9 ونتيجتهما هى 18 , 8 تدخل فى النتيجة النهائية مباشرة اما 1 فهو عدد محمول  للخطوة الثانية ويطلق عليه ال carry وهذا العدد يدخل على مجموع ال 7 5 فتكون النتيجة 13 والنتيجة النهائية للعملية الحسابية هى 138
3 الأمر الثالث هناك ارقام خاصة مثل: 10 و 100 أو 1000 الى أخره بالنسبة لعملية الضرب. وهي كما نلاحظ اعداد ممكن التعبير عنها فى صورة أسية يكون الأساس فيها العدد 10 أما الأس فهو اى عدد طبيعي. ونتيجة الضرب نحصل عليها بمنتهى البساطة بان نضيف الأصفار الموجودة فى العدد المذكور انفا الى يمين العدد الاخر. مثلا نتيجة ضرب 27 فى 100 هي 2700 . أذن نحن نحصل على الأجابة فورا ولا نحتاج لتطبيق اى خوارزمية معقدة لعملية الضرب. اذن نحن نحصل على النتيجة النهائية فى خطوة واحدة. وهذا النقطة تحتاج منا الى بعض التعليق فبعض الحواسب تحتوى على مايطلق عليه مزيح باريل أو Barrel Shifter وهذا بامكانه ان يزيح اى عدد من الخانات ويملأ الخانات الجديدة بالاصفار فكأنه يضرب فى 10 او فى 100 او 1000 وذلك فى خطوة واحدة. لكن ليست كل الحواسب تستطيع ذلك. بعضها يستطيع ان يزيح العدد خانة واحدة فقط فى الخطوة الواحدة. وبعض الحواسيب يعمل بين هذا وذاك. لكن الأكيد  ان الضرب في هذه الأرقام الخاصة يتم على مستوى الدوائر الألكترونية بصورة اكثر كفاءة وفاعلية من الضرب فى باقى الأرقام الأخرى. وفى موضوعنا اليوم سنفترض كما سبق وذكرنا اننا نستطيع ان نزيح اى عدد من الخانات فى خطوة واحدة فقط.
4 النقطة الرابعة اننا لا نستطيع ان نجري عمليتين من العمليات الاساسية الثلاثة السابقة فى نفس الوقت. فليس بأمكاننا ان نضرب 7 فى 5 و نجمعهما فى نفس اللحظة. ربما يستطيع بعض العباقرة والموهوبون ذلك . لكننا هنا سنفترض ان ذلك غير ممكن. ولفعل ذلك نحتاج الى خطوتين متتاليتين.

وهنا ادخل علماء المعلومات تعريف مصطلح التعقيد Complexity بالنسبة لمشكلة معينة ما او خورازمية معينة. فلحل مشكلة معينة يتخيل المعلوماتيون جهاز كمبيوتر تخيلى يقوم بحل تلك المشكلة ويعمل وفق المبادئ السابقة. وطريقة عمل هذا الجهاز يشبه الى حد ما طريقة عملنا. فنحن لا نستطيع ان نضرب 7 فى 9 و نجمعهما فى نفس اللحظة. ولكنها عملية تلو الأخري. وهكذا فجهاز الكمبيوتر التخيلى يستطيع ان يجرى كل عملية اساسية فى خطوة واحدة. فلكل جهاز كمبيوتر سرعة معينة واذا شئنا الدقة انه أيقاع معين. وأذا قلنا ان سرعة حاسوب هى 2 ميجاهيرتز فمعنى ذلك انه يستطيع ان يجري 2 مليون عملية اساسية فى الثانية الواحدة.

ويرمز الرياضيون لمصطلح “التعقيد” بالرمز O واليوم سنحسب تعقيد عملية ضرب عددين لهم نفس عدد الخانات. لكن بداية علينا ان نلاحظ شيئا هاما. فعدد الخطوات ليست رقما ثابتا. مثلا اذا نظرنا فى عدد الخطوات اللازمة لضرب عددين من خانتين فقد يكون هذان العددان هما  10 فى 10وطبعا النتيجة هي 100.  والنتيجة نحصل عليها فى خطوة واحدة وذلك بتطبيق الملاحظة الاساسية الثالثة. لكن ماذا اذا كان علينا ان نضرب 89 فى 68؟ طبعا سنحتاج لأكثر من خطوة للحصول على النتيجة. ولذلك فعلماء المعلومات هنا عندما يتحدثون عن تعقيد مشكلة -مالم يذكروا شيئا اخر- فانهم يبحثون عن عدد الخطوات اللازمة لحل المشكلة بفرض حلول أسوأ الاختيارات.

دعونا نبدأ رحلتنا ولنحسب اولا ما هي عدد الخطوات اللازمة لجمع عددين لهم نفس عدد الخانات. مثلا ماهى عدد الخطوات اللازمة لجمع 66 زائد 32 . الاجابة واضحة اننا نحتاج الى خطوتين فقط . خطوة لجمع 6 زائد 2 وخطوة لجمع 6 زائد ثلاثة. ونقول ان تعقيد عملية الجمع هو تعقيد خطى
O(n)=n

واذا كان البعض يتشكك فى هذه النتيجة لاننا اخترنا ارقام سهلة. نوضح ذلك الامر بالمثال التالى ما هي عدد الخطوات  اللازمة لجمع 89 زائد 89 . مرة اخرة انها خطوتان. الخطوة الاولى نجمع 9 زائد 9 . النتيجة هى طبعا 18 . ثمانية تدخل فى النتيجة مباشرة. الخطوة الثانية اننا نجمع 8 زائد 8 زائد 1 . وهذه عملية تحتاج لخطوة واحد كما فى النقطة الثانية وتكون النتيجة النهائية هى 178 . واذا اردنا جمع عددين كلاهما من 8 ارقام فاننا نحتاج الى 8 خطوات. واذا أفترضنا اننا نحتاج الى ثانية واحدة لأتمام كل خطوة فاننا نحتاج الى 8 ثوان لاتمام العملية المذكورة.

دعونا نخطو خطوة اخرى ونرى ما هو عدد الخطوات اللازمة لضرب عدد مكون من عدد من الخانات فى عدد ثان مكون من رقم واحد فقط. مثلا ما هى عدد الخطوات اللازمة لضرب 89 فى 9؟  او عموما لضرب عدد مكون من n من الخانات فى عدد من رقم  واحد؟ نعلم ان علينا ان نضرب ذللك العدد الوحيد فى كل رقم في العدد الأول. ثم علينا ان نجمع الرقم الاول من النتيجة مع الرقم الثانى المحمول من المرحلة السابقة. فنحتاج فى النهاية الى 2n من العمليات الاساسية أو
O(n)=2n
فلضرب 89 في 9 نحتاج الى 4 خطوات. الخطوة الاولى ان نضرب 9 فى 9 والنتيجة هى 81 الرقم الأول 1 يدخل فى النتيجة النهائية مباشرة لانه لا يوجد رقم محمول من خطوة سابقة بينما 8 هي عدد محمول ينتقل الى المرحلة التالية. الخطوة الثانية ان نضرب 9 فى 8 النتيجة هى 72 . الخطوة الثالثة ان نجمع 2 زائد 8 المحمولة من الخطوة السابقة تكون النتيجة 10 . الصفر يدخل فى النتيجة مباشرة بينما ال 1 هو عدد محمول ينتقل الى الخطوة التالية. الخطوة الرابعة ان نجمع 1 زائد 7 لنحصل على 8 . والنتيجة النهائية هى 801

الان نصل الى هدفنا وهو حساب عدد الخطوات اللازمة لضرب عددين لهما نفس عدد الخانات. مثلا ما هى عدد الخطوات اللازمة لضرب 89 فى 99 .  كما نعلم من سنوات المدرسة الاولي علينا أن نضرب  أولا كل رقم من العدد  الثاني في العدد الأول . وكما رأينا لتونا فضرب 9 فى 89 يحتاج الى 4 خطوات. وضرب التسعة الثانية فى ال 89 يحتاج مرة اخرى الى 4 خطوات فنحتاج حتى الان الى 8 خطوات. او عموما  نحتاج الى 2n^2  عندما يكون عدد الخانات فى كل عدد هو n. حيث انهاء ضرب كل خانة من العدد الثاني  يحتاج الى 2n من الخطوات.

الأن وكما نعلم علينا ان نكتب تلك الأرقام فى سطور تحت بعضها . لكن علينا ان نزيح بعض السطور. اول سطر نكتبه كما هو. لكننا نزيح السطر الثانى خطوة واحدة باتجاه اليسار والسطر الثالث ان وجد نزيحه خانتين والسطر الرابع  نزيحه ثلاثة خطوات وهكذا. وكما نعلم من النقطة الثلاثة من المبادئ الأساسية اننا نستطيع ان نزيح اى عدد من الخانات فى خطوة واحدة. اى اننا ل n  من السطور نزيح فقط n-1 منها وبالتالى نحتاج الى n-1 من الخطوات. وفى المثال السابق فان ال 801 الاولى تبقى تابتة بينما تتحول 801 الثانية الى 8010 .

الان الخطوة النهائية هي ان نجمع السطور السابقة مع بعضها. لكن كيف لنا ان نجمع n من السطور مع بعضها؟ علينا ان نجمع اولا السطر الأول مع السطر الثاني ثم نجمع النتيجة على السطر الثالث . ثم نجمع النتيجة على السطر الرابع وهكذا. اذن اننا نحتاج الى n-1 من عمليات الجمع. لكن ماهي الخطوات اللتى نحتاجها فى عملية الجمع الواحدة؟

هنا نلجأ الى حيلة. نعلم اننا نبحث عن أسوأ الاحتمالات الممكنة. ولضرب عددين كلاهما يحتوي علي n من الخانات فان النتيجة النهائية ستحتوي فى أسوأ الحالات على 2n من الخانات. لماذا؟ مثلا لضرب عددين من 3 خانات فى بعضهما. اكبر عددين ممكن فرضهما هما 999 فى 999 . وبالتالي النتيجة لا بد ان تكون أصغر من ضرب 1000 فى 1000 . وضرب الف فى الف يعطى مليون هو عدد يتكون من 7 ارقام . وأي عدد اصغر منه يحتوى على 6 ارقام. اذن الخلاصة النهائية ان اى من عمليات الجمع ستحتاج فى حد اقصى الى 2n من الخطوات . وبذلك تكون تعقيد عملية الضرب من كل ما سبق هى كالتالي:
O(n)=2n^2 + (n-1)+(n-1)*2n=4n^2-n-1

اذن لضرب عددين من خانتين نحتاج الى 13 خطوة او كما سبق وافترضنا 13 ثانية بينما جمعهما يحتاج الى ثانيتين فقط. بالمثل فجمع عددين من 8 أرقام سوف يحتاج الى 8 ثوان بينما ضربهم يحتاج الى 247  ثانية أو اكثر من 4 دقائق. ماذا اذن عن جمع عددين من 100 رقم و ضربهما. للجمع سنحتاج الى 100 ثانية بينما الضرب يحتاج الى أكثر من 11 ساعة.

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

الأن نصل الى السؤال المهم هل هناك طريقة نزيد بها من كفاءة اجراء عملية الضرب؟ من الجلي ان هناك سبيلان لتحقيق هذا الهدف. السبيل الاول هو عن طريق بناء كمبيوترات اسرع  تسطيع  ان تجري ملايين ومليارات من العمليات الأساسية في الثانية الواحدة. والتقدم التكنولوجي يصنع هذا الامر بصورة تلقائية. فلا يوم يمر الا و نسمع عن انتاج اجهزة حاسوب ذات سرعات اعلى وأعلى. اما السبيل الثانى هو ما يهمنا أكثر. فهل هناك خوارزميات اكثر ذكاء من تلك اللتى تعلمناها فى المدرسة تمكننا من اتمام عملية الضرب بصورة اسرع؟

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

المصادر:
https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/Barrel_shifter
http://stackoverflow.com/questions/9083743/is-bit-shifting-o1-or-on