الحسابيات

10. الحسابيات

10.1 الخوارزمية الإقليدية (Euclid’s Algorithm)

أشهر جميع الخوارزميات هو بلا شك خوارزمية إقليدس (Euclid). وهي تحسب القاسم المشترك الأكبر لعددين صحيحين x و y، ويُكتب x ∧ y، ويُسمّى «قاسم x و y الأكبر». وإذا أُعطي عددان صحيحان غير سالبين x و y، فإن الخوارزمية الإقليدية تستبدل الزوج (x,y) بالزوج (y,x mod y)، وتستمر حتى تبلغ y الصفر. ثم تُعيد قيمة x، وهي القاسم المشترك الأكبر للقيمتين الابتدائيتين لـ x و y. ونكتب هذه الخوارزمية في صورة دالة عودية gcd:

  let rec gcd x y =
    if y = 0 then x else gcd y (x mod y)

تتبع صحة الخوارزمية من كون كل تكرار يحافظ على القاسم المشترك الأكبر لـ x و y. وعندما نبلغ y = 0، نُعيد x، أي x∧ 0، وهو إذن القاسم المشترك الأكبر للقيمتين الابتدائيتين لـ x و y. بعبارة أخرى، استعملنا الخاصيتين التاليتين للقاسم المشترك الأكبر:

يتبع توقف الخوارزمية من كون y يتناقص تناقصًا صارمًا في كل تكرار، مع بقائه غير سالب طوال ذلك. وبالفعل، لدينا الثابت (invariant) القائل إن x,y ≥ 0.

يُعطى تعقيد الخوارزمية الإقليدية بمبرهنة لاميه (Lamé’s theorem). وتنصّ على أنه إذا نفّذت الخوارزمية s تكرارًا مع x > y > 0، فإن x ≥ Fs+1 و y ≥ Fs، حيث (Fn) هو متتالية فيبوناتشي (Fibonacci sequence). ونستنتج من ذلك أن الخوارزمية الإقليدية لوغاريتمية، أي s = O(log x). وفي الحالة العامة، يكون التعقيد O(log(max(x,y)))؛ انظر التمرين 10.1. ويمكن إيجاد تحليل مفصّل في كتاب فن البرمجة الحاسوبية [14، القسم 4.5.3].

يعمّم التمرين 10.2 الدالة gcd على الأعداد الصحيحة x و y التي ليست بالضرورة غير سالبة.

الخوارزمية الإقليدية الموسّعة (Extended Euclidean Algorithm)

يمكننا بسهولة تعديل الخوارزمية الإقليدية لحساب معاملات بيزو (Bézout coefficients)، أي عددين صحيحين u و v يحققان المعادلة التالية:

يُعرف هذا بالخوارزمية الإقليدية الموسّعة. وننفّذه في صورة دالة extended_gcd تأخذ العددين الصحيحين x و y كسمتين وتُعيد الثلاثية (u,v,x ∧ y). ويُعطى الرمز في البرنامج 79.

من السهل ملاحظة أن المكوّن الثالث للثلاثية المُعادة هو القاسم المشترك الأكبر لـ x و y. وبالفعل، إذا ركّزنا على هذا المكوّن، نجد الحسابات نفسها التي تُجرى في الدالة gcd بالمتغيرين x و y، لأن x −⌊⌋y ليس سوى x mod y. وللتحقق من المعادلة 10.1، يكفي الاستدلال بالاستقراء على y. والحالة الأساسية y = 0 واضحة. وفي خطوة الاستقراء، تخبرنا فرضية الاستقراء بأن:

وهذا يكافئ:

وهو ما يوافق رمز الدالة extended_gcd.

تعقيد extended_gcd هو نفس تعقيد الدالة gcd. فرقم العمليات المُنفَّذة في كل تكرار أكبر بلا شك، لكنه يبقى محدودًا، وعدد التكرارات هو نفسه تمامًا. ولذلك يظل التعقيد O(log x).

10.2 الرفع إلى الأس بالتربيع (Exponentiation by Squaring)

من أجل n ∈ ℕ، يُجري الحساب الساذج لـ xn عددًا من العمليات يساوي n− 1 عملية ضرب. وتقوم خوارزمية الرفع إلى الأس بالتربيع على حساب xn بإجراء O(log n) من عمليات الضرب فقط. وهي تستعمل المتطابقات التالية:

وترجمتها إلى OCaml، من أجل x من النوع int، سهلة. ويمكننا أن نكتب، على سبيل المثال، الرمز المُعطى في البرنامج 80. وهو يستعمل كون n/2 يُعيد ⌊n∕2⌋، بغضّ النظر عن كون n زوجيًا أم فرديًا.

توجد صِيغ متعددة. يمكننا، على سبيل المثال، معالجة n = 1 كحالة خاصة، لكن هذا ليس مفيدًا بشكل خاص. (انظر أيضًا التمرين 10.4.) وعلى أي حال، تبقى الفكرة المركزية كما يلي: إذا قسمنا الأس على اثنين على الأقل في كل خطوة، فإن العدد الإجمالي للنداءات العودية يتناسب مع log(n)، وكذلك عدد عمليات الضرب.

وبشكل أدقّ، يمكننا أن نُثبت بالاستقراء على k أنه إذا كان 2k−1 ≤ n < 2k، فإن الدالة exp تُجري k نداءً عوديًا بالضبط. وبما أن كل نداء عودي لـ exp يُجري عملية ضرب واحدة أو عمليتين، نستنتج أن العدد الإجمالي لعمليات الضرب محدود بـ 2log n.

وتطبيقات هذه الخوارزمية لا تُعَدّ ولا تُحصى، خاصة أن x ليس بالضرورة من النوع int. فبمجرد أن يكون لدينا عنصر محايد (unit) وعملية تجميعية (associative operation)، أي بنية مونويد (monoid) M، يمكننا تطبيق هذه الخوارزمية لحساب xn من أجل x ∈ M و n ∈ ℕ. ويقترح التمرين 10.6 أحد هذه التعميمات.

10.3 الحسابيات النمطية (Modular Arithmetic)

نفترض في هذا القسم أننا نرغب في إجراء حسابيات بقياس (modulo) m من أجل قيمة ثابتة لـ m. وهذا مثير للاهتمام لأسباب عدة. فقد نرغب، على سبيل المثال، في حساب قيمة ضخمة جدًا مع الاهتمام فقط بخاناتها k الأخيرة في الأساس 10. وفي هذه الحالة يكون لدينا m = 10k. ويمكننا أيضًا استعمال مبرهنة الباقي الصينية (Chinese Remainder Theorem) لحساب قيمة معطاة بقياس عدة أعداد صحيحة أولية فيما بينها، وتمثيل أعداد صحيحة يحتمل أن تكون أكبر من تلك التي توفّرها الآلة بهذه الطريقة. انظر التمرين 10.8.

وفي ما تبقّى من هذا القسم، نفترض أن m ثابت من النوع int بحيث m > 0. وسنكتب عددًا من الدوال التي تتعامل مع الأعداد الصحيحة بقياس m، أي الأعداد الصحيحة x التي تحقق:

ويقترح التمرين 10.7 جمع الدوال المختلفة في دالة وصفية (functor) مُعاملَة بـ m. نبدأ بدالة of_int تأخذ عددًا صحيحًا اعتباطيًا x وتُعيد باقيه بقياس m. ولا يمكننا ببساطة إجراء x mod m لأنه إذا كان x سالبًا، فإن xmodm يكون سالبًا أيضًا. وبشكل عام، يحمل amodb الإشارة نفسها لـ a. ولذلك

نكتب:

  let of_int x =
    let r = x mod m in if r < 0 then r + m else r

ويُكتب الجمع بقياس m بسهولة إذا افترضنا أن المعاملات هي بالفعل أعداد صحيحة بقياس m. ولضمان الخاصية (10.2)، يكفي طرح m إذا كانت قيمة x+y أكبر من أو تساوي m.

  let add x y =
    let r = x + y in if r >= m then r - m else r

ولأن العددين الصحيحين x و y غير سالبين، فالإشارة ليست مشكلة هنا. ومع ذلك، ولكي يكون الجمع صحيحًا، يجب ألا تفيض العملية x+y، أي يجب أن يكون لدينا x+y ≤ max_int. وهناك طريقة سهلة لضمان ذلك، وهي فرض قيمة قصوى على m، أي m ≤ max_int∕2 + 1. ويمكننا فعل ذلك بوضع التوكيد (assertion) التالي في بداية الرمز:

  let () = assert (0 < m && m <= max_int/2 + 1)

ويُكتب الطرح بسهولة مماثلة، إذا حرصنا على إعادة قيمة غير سالبة، كما فعلنا أعلاه في الدالة of_int.

  let sub x y =
    let r = x - y in if r < 0 then r + m else r

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

الضرب

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

  let mul x y =
    (x * y) mod m

ومع ذلك، إذا لم نرغب في تقييد مجال المعاملات، واكتفينا بالقيد المفروض أصلًا، أي m ≤ max_int∕2 + 1، فلا يمكننا استعمال الضرب العادي لأنه قد يُسبّب فيضًا. لكن يمكننا التغلب على هذه الصعوبة بإجراء الضرب كما يُجرى يدويًا. لنفترض أن x مكتوب في الأساس 2 على الصورة:

حيث xk هو الرقم الأكثر دلالة (most significant digit) و x0 الرقم الأقل دلالة (least significant digit). وسنكتب بعد ذلك حلقة (loop) تحسب (xk…xi)2 ×y (mod m)، من أجل i متغيّر من k + 1 إلى 0. ونكتبها على شكل حلقة for، مع تجميع النتيجة في مرجع (reference) r. وبالنظر إلى الافتراض على m وإلى كون النوع int في OCaml ممثلًا بـ Sys.word_size-1 بتة إشارية (signed bits) (انظر الفصل 3)، يمكننا البدء بـ i = Sys.word_size-4.

  let mul x y =
    let r = ref 0 in
    for i = Sys.word_size - 4 downto 0 do

في كل تكرار من الحلقة، نبدأ بضرب r في 2، بقياس m، وهو ما نفعله بالدالة add.

      r := add !r !r;

ويكون لدينا بعد ذلك !r ≡ (xk…xi)2 × 2 ×y (mod m). ثم نختبر البتة xi وإذا كانت تساوي 1، نضيف y إلى r لإعادة إرساء ثابت الحلقة.

      if x land (1 lsl i) <> 0 then r := add !r y

وبعد الخروج من الحلقة، يكون لدينا !r ≡ xkxk−1…x1x0 ×y (mod m)، أي !r ≡ x×y (mod m)، وهو النتيجة المطلوبة. ويُعطى الرمز في البرنامج 82.

القسمة

تفترض قسمة x على y بقياس m أن y و m أوليان فيما بينهما، وتُعيد نتيجة q بحيث q×y = x (mod m). ونستعمل الخوارزمية الإقليدية الموسّعة (البرنامج 79). وبالفعل، إذا كان y و m عددين صحيحين أوليين فيما بينهما، فإن الخوارزمية الإقليدية الموسّعة تعطينا عددين صحيحين، u و v، بحيث:

ويتبع هذا من المعادلة 10.1. وبضرب هذه المساواة في x، نحصل على:

ونتتيجة القسمة إذن هي x×u. ويُعطى الرمز في البرنامج 82. وهو يستعمل of_intu لأن u قد يكون سالبًا، لكن يمكن جعله أكثر كفاءة بما أن الخوارزمية الإقليدية تضمن أن |u| < m، بحيث يصبح استعمال of_int معقدًا بلا ضرورة.

10.4 حساب المصفوفات (Matrix Calculus)

ننفّذ في هذا القسم بعض العمليات الأساسية على المصفوفات. وتبسيطًا، نفترض أن المصفوفات ذات معاملات صحيحة. ويقترح التمرين 10.9 تعميمًا على مصفوفات ذات معاملات اعتباطية.

وكما شرحنا في القسم 2.5 غربال إراتوستينس (Sieve of Eratosthenes)، فإن المصفوفة ليست سوى مصفوفة من المصفوفات (array of arrays)، أي:

  type matrix = int array array

ونُذكّر بأنه يجب ألا نكتب Array.make3(Array.make4v) لإنشاء مصفوفة 3 × 4، بل بالأحرى Array.make_matrix34v، أو بالمثل Array.init3(fun_->Array.make4v).

وبخلاف Array.make_matrix، لا توفّر المكتبة المعيارية لـ OCaml عمليات على المصفوفات. فلنبدأ إذن بكتابة دالة init_matrix، نظيرة Array.init بالنسبة للمصفوفات. تأخذ الدالة كسمتين بُعدي المصفوفة n و m، ودالة f لتهيئة كل عنصر.

  let init_matrix n m f =
    Array.init n (fun i -> Array.init m (fun j -> f i j))

بعبارة أخرى، نُعيد المصفوفة M ذات الحجم n×m بحيث Mi,j = f i j. ونستخلص من ذلك دالة id لبناء مصفوفة الوحدة (identity matrix) ذات الحجم n×n.

  let id n =
    init_matrix n n (fun i j -> if i = j then 1 else 0)

بعد ذلك، لنكتب دالة size تُعيد أبعاد مصفوفة، أي عدد الأسطر والأعمدة، في شكل زوج. وبافتراض أن المصفوفة تحتوي دائمًا على سطر واحد على الأقل، يمكننا كتابة:

  let size a =
    (Array.length a, Array.length a.(0))

ولننظر الآن في جمع مصفوفتين A و B. نبدأ بالتحقق من أن لهما الحجم نفسه.

  let add a b =
    let (n, m) as s = size a in
    if size b <> s then invalid_arg "add";

ثم يكفي استعمال init_matrix لبناء المصفوفة التي حدّها العام هو Ai,j + Bi,j.

    init_matrix n m (fun i j -> a.(i).(j) + b.(i).(j))

وجداء مصفوفة A ذات الحجم n × p ومصفوفة B ذات الحجم p × m هو مصفوفة C ذات الحجم n × m يُعطى حدّها العام بـ:

نبدأ بتحديد أبعاد المصفوفتين وبالتحقق من أن عدد أعمدة A يساوي فعلًا عدد أسطر B.

  let mul a b =
    let n, p = size a in
    let q, m = size b in
    if q <> p then invalid_arg "mul";

ثم نكتب دالة محلية product تحسب المعامل Ci,j وفق المعادلة (10.3).

    let product i j =
      let s = ref 0 in
      for k = 0 to p - 1 do s := !s + a.(i).(k) * b.(k).(j) done;
      !s

ولا يبقى سوى إنشاء مصفوفة ذات الحجم n × m بالدالة init_matrix بتمرير الدالة product إليها كسمة.

    in
    init_matrix n m product

ويُعطى الرمز الكامل أعلاه في البرنامج 83. وليست مصفوفة من المصفوفات الاحتمال الوحيد لتمثيل مصفوفة. فهناك تمثيلات أخرى أكثر اقتصادًا من حيث الذاكرة عندما يكون عدد كبير من العناصر متساويًا. ونتكلم حينئذ عن المصفوفات المتفرّقة (sparse matrices). ويقترح التمرين 10.13 أحد هذه التمثيلات.

 module Modulo(M: sig val m: int end): sig ... end = struct ... end

  type matrix = { cols: int; rows: M.t array }