رأينا المرة الماضية لماذا أن أجراء عملية الضرب اصعب من أجراء عملية الجمع. وحسبنا تعقيد العمليتين ورأينا ان تعقيد عملية الجمع هو تعقيد خطى وتحديدا فان
O(n)=n
بينما تعقيد عملية الضرب هو تعقيد تربيعى وتحديدا فأن
O(n)=4n^2-n-1
لذا فاجراء عملية جمع عددين كلاهما من مائة خانة يحتاج الى 100 خطوة تماما بينما اجراء عملية ضربهما يحتاج الى عشرات الاف الخطوات! ولذا يبدو طرح السؤال التالي حتميا: هل توجد خوارزميات أخرى لاجراء عملية الضرب اكثر كفاءة بخلاف تلك اللتى تعلمناها فى المدرسة. بل ربما نسأل: هل هناك أساسا طرق بديلة لاجراء عملية الضرب غير تلك اللتى تعلمناها فى المدرسة؟ ام أنها هى الطريقة الوحيدة وليس فى الأمكان أبدع مما كان. والاجابة طبعا كما تتوقعون هي نعم والا لما احتجنا الى كتابة هذا الموضوع! لكن ما هى ياترى تلك الطرق الأخري؟
طريقة اليوم قد عرضناها منذ فترة طويلة فى أطار موضوع أخر وسيتعجب البعض عندما يعلم انها الطريقة اللتى كان يستخدمها قدماء المصريين لأجراء عملية الضرب!. وقبل ان نرى مثال تفصيلى لتلك الطريقة نوجز خطواتها الثلاثة فى الفقرات التالية
1 لضرب عددين فى بعضهما نضاعف العدد الأول باستمرار بينما ننصف العدد الثانى مع تقريب النتيجة الى الأسفل لنحصل دائما على رقم صحيح. ونكتب هذه الاعداد بداخل عمودي جدول فى مقابلة بعضهما وننتهى عندما نصل فى العمود الثانى الى العدد 1
2 نستبعد صفوف الجدول اللتى تكون فيها اعداد العمود الثانى زوجية
3 نجمع أعداد العمود الأول المتبقية مع بعضها لنحصل على النتيجة النهائية
دعونا نرى ذلك بالتفصيل فى المثال التالى. دعونا نحسب ما هى نتيجة ضرب 28 فى 13؟ النتيجة كما تعطيها الألة الحاسبة هى 364. دعونا نرى كيف نحصل على تلك القيمة كما كان يفعل قدماء المصريين بان نضاعف ال 28 وننصف ال 13 باستمرار
28 13 العمود الثانى يحتوى على عدد فردي
56 6 العمود الثانى يحتوى على رقم زوجى فسيتم استبعاده لاحقا من عمليات الجمع
112 3 العمود الثانى يحتوى على عدد فردي
224 1 العمود الثانى يحتوى على عدد فردي وهو نفس الوقت العدد 1 مما يعنى نهاية الخطوة الأولي
الأن نستبعد الصف الثانى ثم نجمع 28 زائد 112 زائد 224 والنتيجة هى 364
وهذه الطريقة تنجح دائما فى جميع الأحوال. لكن ما هو التفسير الرياضى لذاك الأمر السحري. كيف اننا عندما نضاعف العمود الاول ووننصف العمود الثاني ونجمع بعض الأرقام على بعضها نحصل على النتيجة الصحيحة؟ الاجابة سنرها واضحة ظاهرة عندما نعبر عن الأعداد فى ضوء النظام الثنائي وليس فى ضوء النظام العشري كما نحن معتادين أن نفعل. لكن ماهو النظام الثنائي أساسا؟!
نعلم جيدا نظام أعدادنا العشري. فهو يتكون أولا عن أخر من عشرة ارقام يصنعون هذا النظام بالكامل. وهذه الأرقام العشرة هى الأرقام من 0 حتى 9 . وكل خانة من عدد فى صورة عشرية تحتوى على أحد الارقام العشرة السابقة. ونطلق على الخانة فى أقصى اليمين خانة الأحاد تليها خانة العشرات فالمئات فالألوف الى اخره. وعدد الخانات الممكنة لاحدود لها. مثلا العدد 321 هو عدد يتكون من 3 خانات. تحتوي خانة الأحاد على الرقم 1 وخانة العشرات على الرقم 2 وخانة المئات على الرقم 3 ونستطيع ان نحلل ونفكك العدد السابق الى الصورة التالية
321=3.100+2.10+1.1
بيد أن نظامنا العشري ليس حقيقة مطلقة فى حد ذاتها. لاشك انه نظام جميل وناجح والا لما كان عاش واستمر عبر هذه القرون الطوال. ولكنه مرة اخرى ليس حقيقة مطلقة. ربما أستمد هذا النظام شيئا من رونقه من أن لنا اصابع عشر فجعل عملية العد والحساب أسهل خاصة بالنسبة للمبتدئين. لكن البابليون عرفوا ايضا نظاما قويا للأعداد لكنه لم يكن نظاما عشريا ولكنه نظام ستينى يصنع فيه 60 رقما نظام أعدادهم. ومن البابليين ورثنا تقسيم الساعة الى 60 دقيقة والدقيقة الى 60 ثانية. كما ان من يعلم اللغة الفرنسية ويعرف كيفية نطق الأعداد بها من السهل عليه ان يتخيل ان الشعوب الفرنسية القديمة عرفت نظاما للأعداد عشرينيا.
اذن وعلى وزن الكلام السابق يتكون النظام الثائي للأعداد أولا عن أخر من رقمين فقط: هما الصفر والواحد. وخانات أي عدد فى ذلك النظام تحتوى على احد هذين الرقمين السابقين. ونطلق على الخانة فى أقصى اليمين خانة الأحاد تليها خانة الأثنينات ثم الأربعات ثم الثمانيات الى اخره. وعدد الخانات الممكنة لاحدود لها. وعلى عكس المثال السابق فان كتابة عدد فى صورة 321 لا معنى لها لأن الصور 2 و 3 غير معرفة بداخل النظام الثنائي. بينما العدد 101 مثلا هى صورة مقبولة لكن قيمة هذا العدد ليست مائة وواحد ولكن خمسة! لأن هذا العدد يتكون من 1 فى خانة الأحاد و0 فى خانة الاثنينات و 1 فى خانة الأربعات فتكون القيمة الكلية خمسة .
ومن مميزات النظام الثنائى ان الرقمين اللذين يتكون منهما هما رقمان خاصان جدا فى العمليات الحسابية. فضرب اى عدد من عديد الخانات فى 0 يعطى النتيجة 0. بينما ضربه فى العدد 1 يعطى العدد نفسه مرة اخري. كذلك بالنسبة لعملية الجمع. فجمع أى عدد مع 0 يعطى العدد نفسه مرة أخري. بينما جمعه زائد 1 هى العملية الوحيدة اللتى فيها بعض المشقة حيت تكون النتيجة هى عدد جديد وهو العدد الصحيح التالى للعدد الأول.
والميزة الأهم بالنسبة للنظام الثنائى انه نظام بسيط وغير معقد كالنظام عشرى فمن السهل أن نصنع الة محدودة الذكاء كجهاز الكمبيوتر -فى حقيقة الأمر لا ذكاء لها على الاطلاق- تستطيع ان تميز بشكل دقيق ويقينى بين حالتين فقط هما الصفر والواحد وبالتالى تستطيع ان تقوم بعمليات حسابية وتبدو وكأنها تتخذ قرارات كما يفعل الانسان. لكن محاولة بناء جهاز كمبيوتر يستوعب 10 حالات مختلفة تمثل الارقام المختلفة مع استيعاب جميع العمليات الخاصة بها هى عملية اكثر تعقيدا بكثير مما نتصور. ولذلك فالنظام الحسابى الوحيد اللذى يستطيع جهاز الكمبيوتر أن يحاكيه من ناحية الدوائر الكهربائية هو النظام الثنائي.
لكن كيف نحول عددا من النظام العشرى الى النظام الثنائي؟ الأجابة بسيطة وتعتمد على فكرة بسيطة. الرقم العشري له احد أحتمالان أما أن يكون عددا فرديا أو زوجيا. فأذا كان عددا فرديا فأن خانة أحاده لابد أن تحتوي على العدد 1 فى الصورة الثنائية والا فأنها تحتوي على 0. وهكذا قد حددنا بسهولة اول خانة جهة اليمين. ماذا عن الخانة الثانية؟ انه نفس المبدأ. نقسم العدد على 2 ونقربه الى الأسفل . فاذا كان العدد جديد فرديا ستكون قيمة الخانة الثانية 1 والأ فهى 0!
دعونا نرى ذلك فى المثال السابق. حيت اننا نريد أن نصل الى حاصل ضرب 28 فى 13. فدعونا نحول العدد 13 الى النظام الثنائي:
العدد 13 هو عدد فردي فبالتالى أول خانة من جهة اليمين هى 1
نقسم العدد 13 على 2 ونقرب النتيجة الى أسفل فنحصل على العدد 6 وهو عدد زوجى اذن العدد الثانى هو 0.
نقسم 6 على 2 نحصل على 3 وهو عدد فردي اذن الخانة الثالثة هى 1
نقسم 3 على 2 مع التقريب نحصل على 1 فتكون الخانة الرايعة هى 1 وهى الخطوة الأخيرة
اذن فالعدد 13 له الصورة 1101 فى النظام الثنائي. ولاحظوا ان 1 فى خانة الثمانيات و 1 فى خانة الأربعات و 1 فى خانة الأحاد تعطى القيمة الأجمالية ثلاثة عشر!
اذن لحساب ضرب 28 فى 13 سأكتفى بتحليل العدد الثانى بدلالة قيم خانات النظام الثنائى كما رأينا لتونا لنري التالي 28×13 تساوي
28x(1×8+1×4+0×2+1×1)=28×8+28×4+28×1
وهذا تماما مافعلته الطريقة المصرية القديمة . حيث انها ضربت العدد 28 فى 2 ثم 4 ثم 8 . وقامت باستبعاد القيمة المضروبة فى 2 وجمعت القيم الأخري على بعضها. وهذه هى تحديدا القيمة الصحيحة!
الأن دعونا نحسب تعقيد Complexity هذه الطريقة. ومبدئيا تبدوا هذه الطريقة اكثر اجهادا من الطريقة المدرسية اللتى نعرفها. فعلينا اجراء العديد من عمليات التنصيف والمضاعفة قبل أن نصل الى الحل النهائي. لكن بداية احب ان اضيف الى علمكم ان هذه الطريقة القديمة ظلت مستخدمة لفترة طويلة جدا. فظلت هى الطريقة المتبعة فى الضرب فى المانيا حتى العصور الوسطى وظلت هى الطريقة المتبعة في روسيا حتى الزمن الحديث. ولذلك يطلق على هذه الطريقة ايضا أسم الطريقة الروسية وأن ثبت بما لا يدع مجالا للشك ان المصريين القدماء كانوا يتبعون هذه الطريقة ويظهر ذلك فى بردية ريند الرياضية
وقبل ان نحسب تعقيد الطريقة رياضيا دعونا نتذكر الأفتراضات اللتى قررناها فى الموضوع الماضي:
1 ضرب عددين كلاهما من خانة واحدة يحتاج الى خطوة واحدة
2 جمع عددين كلامهما من خانة واحدة يحتاج الى خطوة واحدة
3 ضرب أى عدد فى الاعداد الخاصة: 10 أو 100 أو 1000 الى أخره يحتاج الى خطوة واحدة
4 لا يمكننا ان نجري اي عمليتين من العمليات السابقة فى نفس الوقت. ولأجراء عمليتين منهما نحتاج الى خطوتين متتاليتين.
وجميع النقط السابقة ستبقى معنا اليوم بدون تغيير. فقط النقطة الثالثة لابد ان نزيدها بشئ من التعليق. صحيح انها ستبقى بصورتها لكننا سوف نلقى عليها الضوء من زاوية جديدة مفاجئة لحد ما. فالأعداد 1 و 10 و100 و 1000 الي أخره هى أعداد خاصة فى صورتها ورسمها بغض النظر عن نظام الأعداد اللتى هي موسومة فيه! الاعداد 1 و 10 و 100 و1000 الى اخرها نعرفها جيدا في ضوء النظام العشري. لكن دعونا نرى النظام الثنائي فكيف نعبر فيها عن القيم: واحد وأثنين و اربعة وثمانية الى اخره. أنها تأخذ الصور التالية 1 و 10 و 100 و 1000 الى أخره.اذن فهذه الصور تعبر عن قيم الخانات فى النظام الثنائى أو في أى نظام اخر للأعداد يمكننا تخيله. فحتى لو كان عندنا نظام أعداد خماسى أو ثمانى أو أى شئ اخر ستبقى هذه الصور 1 و 10 و 100 و 1000 الى أخره صورا خاصة تعبر عن القيم المقابلة لخانات ذلك النظام العددي.
اذن دعونا نتخيل أى قيمة ولتكن العدد ثلاثة ونكتبه فى النظام الثنائى كالتالي 11 فاذا ضربناه فى العدد اثنين وصورته هكذا 10 فيجب علينا ان نضيف صفرا الى يمين العدد الاول فنحصل عىل 110 وهذه فعلا قيمة العدد ستة. اذا النقطة الثالثة فى الأفتراضات الاولية ستبقى كما هى فى نظام الأعداد الثنائى وفى أى نظام أعداد اخر. فهذه الصور كأنها تخبئ خلفها شيئا سحريا.
اذن القلق اللتى شعرنا به باتجاه تلك الطريقة وخصوصا ما يتعلق بعمليات التنصيف وحساب الضعف سيفتر الأن كثيرا اذا اجرينا تلك العمليات فى ضوء نظام الاعداد الثنائى حيث ان تلك العمليات لا تحتاج الا خطوة واحدة. فلمضاعفة عدد ما علينا فقط ان نزيحه باتجاه اليسار خانة واحدة وملء الخانة على اليمين بصفر. ولتنصيف عدد علينا فقط ازاحته خانة باتجاه اليمين وهذا كل ما فى الأمر. اذن دعونا نحسب تعقيد عملية الضرب بالطريقة المصرية القديمة اذا أجرينها فى نظام الاعداد الثنائي.
اولا دعونا نحسب ما هى عدد الصفوف اللتى يحتويها الجدول اللذى ذكرناه سابقا في الخطوة الأولي. نستطيع بسهولة ان نرى أن عدد الصفوف هو n عندما تكون خانات العدد الثاني n. فالصف الأخير يحتوى على خانة واحدة تحتوي على القيمة 1 . والصف اللى يعلوه هو مضاعف هذا الرقم فيحتوى على خانتين والصف اللذى يعلوه يزيد بخانة وذلك حتى نصل الى الصف الأول اللذي يحتوى على n من الخانات. أذن فنحن لدينا n من الصفوف.
كما أن الصف الأول يحتوي على العددين الاول والثانى بدون أى تغيير. والصفوف اللتى تحتوى على تغيير هى فقط n-1 حيث أننا في كل صف نقوم بعمليتين: هى مضاعفة الرقم الأول وتنصيف العدد الثاني . أذن عدد الخطوات الكلية من الخطوة الأولي هى 2(n-1) ;
نصل الي الخطوة الثانية وهى استبعاد بعض الصفوف اللتى تكون فيها الأعداد فى العمود الثانى زوجية. دعونا نكون متشائمين ونفرض اننا لن نستبعد أى صف وجميع الصفوف سوف نستخدمها فى الخطوة الثالثة
اذن نصل الى الخطوة الثالثة وهى جمع n من الصفوف. كما سبق وذكرنا فى الموضوع الماضى ان ذلك يعنى n-1 عملية جمع. وحيث أن ضرب عددين لهما n من الخانات فى بعضهما سيكون للنتيجة النهائية فى حد أقصى 2n من الخانات اذن نتيجة عملية الجمع النهائية وأى من عمليات الجمع السابقة لها ستحتاج فى حد اقصى 2n من الخانات. والأن بامكاننا أن نحسب التعقيد الكلى على الصورة التالية
O(n)=2x(n-1)+(n-1)x2n=2n^2-2
وهذه النتيجة جد مفاجئة فهى أفضل من الحساب بالطريقة المدرسية اللتى تعرفنا عليها فى المرة الماضية. فلو كنا أجهزة كمبيوتر تدرك الأعداد فى صورة النظام الثنائي فقط لكان الحساب بالطريقة المصرية القديمة افضل كثيرا من الحساب بالطريقة اللتى نعرفها . وذلك طبعا بعد تحقق شرط ان عمليات التنصيف والمضاعفة نستطيع أن نجريها فى خطوة واحدة.
لكننا بشر ونعرف بخلاف النظام الثنائى النظام العشري. فالسؤال الأن لماذا لانحول الأرقام من النظام العشري الى النظام الثنائي ثم نجري عملية الضرب من خلال ذلك النظام؟ الأن سنصل الى عيوب النظام الثنائى. فقد تعاملنا معه من قبل كما لو أنه كان مثاليا خاليا من العيوب. العيب الرئيس فى النظام الثنائى ساطلق عليه التضخم! فهو يشبه التضخم فى عالم الاموال حيث تزداد القيمة الأسمية للنقود بينما تتناقص القوة الشرائية لها. مثلا العدد 9 فى النظام العشري نحتاج الى خانة واحدة للتعبير عنه. لكن العدد 9 فى النظام الثنائى يأخذ هذه الصورة 1001 أي اننا احتجنا الى 4 خانات للتعبير عن قيمة نستطيع ان نعبر عنها بخانة واحدة فى النظام العشرى. اذن عندما نحول الأعداد من النظام العشري الى النظام الثنائى فان عدد الخانات سوف يزيد وبالتالى عدد خطوات الحساب الكلية!
مثلا دعونا نرى عملية ضرب 99 فى 99 . فى ضوء النظام العشري وبالطريقة المدرسية هذه عملية ضرب عددين من خانتين فى بعضهمها ونحصل على عدد الخطوات القصوى بالمعادلة السابقة
O(n)=4n^2-n-1
وحيث ان لدينا خانتين فتكون عدد الخطوات الكلية ثلاث عشر. ماذا اذا حولنا العدد تسعة وتسعون الى النظام الثنائى ؟ اذن سنحصل على الصورة التالية 1100011 اذن نحصل على سبعة خانات وعدد الخطوات القصوى حسب المعادلة اللتى حصلنا عليها
O(n)=2n^2-2
يفيدنا بأننا قد نحتاج الى 96 خطوة. واذا حسبنا بدق أكبر حيث اننا نرى ان العدد يحتوي فى الصورة الثنائية على ثلاثة اصفار. اى أننا لن نحتاج الى جمع ثلاثة صفوف من الجدول نصل الى ان عدد الخطوات الكلية هو 45 خطوة وهو مازال عددا اكبر بكثير من ثلاث عشر.
اذن فلو كنا أجهزة كمبيوتر فان حساب الجمع بالطريقة المصرية القديمة يبدو وكأنه افضل لنا. لكن تعقيد هذه الطريقة مازال تربييعا فالفارق بينه وبين الطريقة المدرسية هو فارق كمى وليس نوعي. فهل هناك من خوارزمية تستطيع ان تصنع اختراقة نوعية ويكون تعقيد عملية الضرب فيها اقل من التربيعي؟ هذا ما سوف نراه فى المرة القادمة باذن الله.
