خوارزمية ليمر للقاسم المشترك الأكبر

خوارزمية ليمر للقاسم المشترك الأكبر ، نسبةً إلى د. هـ. ليمر ، هي خوارزمية سريعة لحساب القاسم المشترك الأكبر في العمليات الحسابية متعددة الدقة ، وهي تُحسّن خوارزمية إقليدس الأبسط من خلال إجراء معظم العمليات باستخدام الأرقام الأولى فقط من القيم. وكلمة "رقم" هنا لا تعني بالضرورة رقمًا عشريًا؛ إذ تُستخدم الخوارزمية غالبًا مع الأعداد الصحيحة المُمثلة باستخدام أساس β، مثل β = 1000 أو β = ^2³² .

لاحظ ليمر أن معظم نواتج القسمة في كل خطوة من خطوات القسمة في الخوارزمية القياسية صغيرة. (على سبيل المثال، لاحظ كنوت أن نواتج القسمة 1 و2 و3 تشكل 67.7% من جميع نواتج القسمة. ^{[ 1 ]} ) ويمكن تحديد هذه النواتج الصغيرة من خلال بضعة أرقام أولية فقط. لذا، تبدأ الخوارزمية بفصل هذه الأرقام الأولية وحساب سلسلة نواتج القسمة طالما أنها صحيحة.

لنفترض أننا نريد الحصول على القاسم المشترك الأكبر للعددين الصحيحين a و b . ليكن a ≥ b .

• إذا كان b يحتوي على رقم واحد فقط (في الأساس المختار ، على سبيل المثال β = 1000 أو β = 2 ³² )، فاستخدم طريقة أخرى، مثل خوارزمية إقليدس ، للحصول على النتيجة.
• إذا اختلف a و b في طول الأرقام، فقم باختزال a بتردد b ثم بدّلهما كما في خوارزمية إقليدس القياسية. كرر ذلك حتى يصبح طولهما متساوياً m .
• الحلقة الخارجية: كرر العملية حتى يصبح أحد a أو b يساوي صفرًا:
  • قلل قيمة m بمقدار واحد. ليكن x هو الرقم الرئيسي (الأكثر أهمية) في a ، x = a div β ^m و y هو الرقم الرئيسي في b ، y = b div β ^m .
  • قم بتهيئة مصفوفة 2 × 3

  ${\displaystyle \textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}}$إلى مصفوفة هوية موسعة${\displaystyle \textstyle {\begin{bmatrix}1&0&x\\0&1&y\end{bmatrix}},}$

  ثم قم بتطبيق خوارزمية إقليدس في آنٍ واحد على الزوجين ( x + A , y + C ) و( x + B , y + D )، حتى يختلف ناتج القسمة. أي، كرر العملية كحلقة داخلية .

  • احسب ناتج القسمة w₁ للقسمة المطولة لـ ( x + A ) على ( y + C ) _، و w₂ _للقسمة المطولة لـ ( x + B ) على ( y + D ). إذا تساوى هذان الناتجان، فإنهما يساويان أيضًا w ، وهو ناتج القسمة (غير المحسوب) من الخطوة المقابلة في خوارزمية إقليدس العادية.

  • • إذا كانت w ₁ ≠ w ₂ ، فاخرج من التكرار الداخلي. وإلا، فعيّن w إلى w ₁ (أو w ₂ ).
    • استبدل المصفوفة الحالية

    ${\displaystyle \textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}}$

    باستخدام ضرب المصفوفة

    ${\displaystyle \textstyle {\begin{bmatrix}0&1\\1&-w\end{bmatrix}}\cdot {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}={\begin{bmatrix}C&D&y\\A-wC&B-wD&x-wy\end{bmatrix}}}$

    وفقًا لصياغة المصفوفة لخوارزمية إقليدس الموسعة.

    • إذا كانت قيمة B ≠ 0، فانتقل إلى بداية الحلقة الداخلية.
  • إذا كانت B = 0، فقد وصلنا إلى طريق مسدود ؛ قم بتنفيذ خطوة عادية من خوارزمية إقليدس مع a و b ، وأعد تشغيل الحلقة الخارجية.
  • اجعل قيمة a تساوي aA + bB وقيمة b تساوي Ca + Db (في نفس الوقت). هذا يُطبّق خطوات خوارزمية إقليدس، التي نُفّذت على الأرقام الأولى في شكلها المُضغوط، على العددين الصحيحين الطويلين a و b . إذا كانت b ≠ 0، فانتقل إلى بداية الحلقة الخارجية.

• كابيل بارانجاب ، خوارزمية ليمر