القوة بالتربيع المتكرر: الأس الباقي والمراكم وحساب البواقي

الأس الباقي وهدف القوة

نريد حساب قوة قاعدة صحيحة لأس صحيح غير سالب، إما كعدد صحيح كامل وإما كباقٍ عند معيار موجب معلن. يشرح مرجع CP-Algorithms طريقة التربيع المتكرر التي تستفيد من التمثيل الثنائي للأس. سننفذ كودًا أصليًا يحفظ تتبع المراكم والقوة الحالية والأس المتبقي، ثم نقارن النتائج بضرب مباشر وبالدالة pow ضمن العقد الذي حددناه.

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

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

[1]

خمسة للأس أحد عشر ومجموع واحد واثنين وثمانية

نختار القاعدة 5 والأس 11. يكتب أحد عشر في النظام الثنائي 1011، ويعني ذلك مجموع 8 و2 و1. لذلك نستطيع تكوين القوة المطلوبة من قوى خمسة للأسس ثمانية واثنين وواحد. لا نختار قوة للأس أربعة في حاصل الضرب النهائي، لأن الخانة التي تمثل أربعة في كتابة أحد عشر الثنائية صفر.

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

والبتات في القراءة من الأقل أهمية إلى الأعلى هي واحد ثم واحد ثم صفر ثم واحد. هذا ترتيب قرارات الحلقة، لا ترتيب كتابة 1011 المعتاد من اليسار إلى اليمين. نراجع التمييز عندما نقول أول خطوة فردية وثالث خطوة زوجية، حتى لا يقرأ المراجع الصفر في موضع آخر ويظن أن التتبع خالف تحليل الأس.

قوى خمسة وخمسة وعشرين و625 و390625

نبدأ بالقوة الحالية 5 التي تمثل القاعدة للأس واحد. بتربيعها نحصل على 25، وهي القوة للأس اثنين. ثم نربع 25 فنحصل على 625، وهي القوة للأس أربعة. وبعد تربيع 625 نحصل على 390625، وهي القوة للأس ثمانية. تغير قيمة القوة الحالية جاء من مضاعفة الأس الذي تمثله، لا من إضافة واحد إلى ذلك الأس.

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

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

الأس الباقي أحد عشر ثم خمسة ثم اثنين ثم واحد

الحلقة تبدأ بالأس المتبقي 11، ثم تقسمه قسمة صحيحة على اثنين بعد معالجة بت الطرف. يصبح 5، ثم 2، ثم 1، ثم صفرًا فتقف. لذلك نفذنا أربع دورات، لا إحدى عشرة دورة، وراجعنا فردية العدد في كل منها كي نقرر هل تدخل القوة الحالية في المراكم.

عند 11 تكون الفردية صحيحة، وعند 5 صحيحة أيضًا، وعند 2 غير صحيحة، ثم عند 1 صحيحة. إذا اكتفينا بفحص فردية الأس الأصلي مرة واحدة ثم كررنا القرار، سنخطئ في البت الثالث. الأس الباقي حالة تتغير مع القراءة، لا نسخة اسمية من المدخل نتركها كما كانت طوال العمل.

ونستعمل أسًا غير سالب لكي يكون الانتقال بالقسمة الصحيحة إلى الصفر ذا معنى في هذا المرور. لا نعالج الأس السالب بالحلقة نفسها ولا نحول هدفه إلى عدد موجب ونزعم أن النتيجة لم تتغير. قوى سالبة أو عكس معياري تحتاج عقودًا وعمليات أخرى، بينما دالتنا ترفض هذا المدخل قبل الحساب.

المراكم خمسة ثم 125 ثم 125 ثم 48828125

المراكم يبدأ بواحد، لأنه عنصر محايد للضرب في النسخة العددية الكاملة. في الدورة الأولى الفردية نضربه في 5 فيصير خمسة. وفي الثانية نضربه في 25 فيصير 125. الدورة الثالثة تمر على القوة 625 لكن البت صفر، فيبقى 125. ثم تضربه الدورة الرابعة في 390625 فيصير 48828125.

العدد 125 يمثل حاصل القوى المختارة سابقًا، ولا يصف قوة المرشح عند تلك اللحظة. إظهار الرقمين في حقل واحد سيخفي لماذا بقي المراكم ثابتًا بينما تغيرت القوة. سنسجل before وafter في التتبع كي يرى القارئ القرار وأثره، لا النتيجة التي كتبناها بعد انتهاء الحلقة فقط.

وبعد الدورة الأخيرة يربع هذا الكود القوة مرة أخرى ويحفظ القيمة التالية رغم أن الأس المتبقي صار صفرًا، فلا تستعمل في دورة جديدة. نذكر ذلك عند عد عمليات التنفيذ الفعلية؛ لا نحسب ترتيبًا مثاليًا آخر ثم ننسب عداده إلى السجل الذي رجع من الدالة. الشاهد يصف الخطوات التي نفذناها، بما فيها انتقال محفوظ انتهى العمل بعده.

الحالة الثابتة بين النتيجة والقوة والأس

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

في خطوة زوجية نحول القوة إلى مربعها وننصف الأس، فيبقى الحاصل نفسه دون تغيير المراكم. وفي خطوة فردية نأخذ عاملًا من القوة إلى المراكم ثم نعالج بقية الأس الزوجية بالطريقة نفسها. هذه العلاقة تفسر لماذا يمكن أن يتغير أكثر من متغير بينما يبقى السؤال العددي النهائي محفوظًا.

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

الخطوة الزوجية والفردية

في الدورة ذات الأس المتبقي 2، لا نضرب المراكم في 625. نربع القوة وننتقل إلى الأس 1، لأن القوة للأس اثنين تساوي مربع القوة نفسها للأس واحد. في الدورة الأخيرة الفردية نضيف ذلك العامل إلى المراكم قبل الانتهاء. الفرق بين الحالتين محدد من البت، وليس من كون قيمة القوة الحالية كبيرة أو صغيرة.

يمكننا تجربة أس زوجي صغير مثل اثنين لقاعدة خمسة؛ تمر القراءة على البت صفر ثم واحد وتنتج 25. وتجربة الأس واحد تختار القاعدة مباشرةً. هذه حالات تعزل قرار الاختيار عن بناء القوى، وتساعد على كشف تبديل ترتيب تحديث المراكم والقوة الذي قد يضرب بعامل جديد قبل استعمال العامل المقصود.

لذلك نحفظ before_power في كل صف ونستعمله عند تفسير الضربة الفردية. next_power هو مرشح الدورة القادمة بعد التربيع، لا العامل الذي اخترناه في الصف الحالي. إذا استعملنا الرقم التالي في شرح القرار الحالي، قد يبدو المراكم غير متوافق مع التتبع رغم أن الذي أخطأ هو قراءة الحقول لا الحساب نفسه.

البواقي بمعيار سبعة والنتيجة ثلاثة

إذا طلبنا باقي خمسة للأس أحد عشر عند المعيار 7، نراجع القيم بعد كل ضرب وتربيع ضمن هذا المعيار. تبدأ القوة بباقي 5، ثم يصبح باقي مربعها 4، ثم 2، ثم 4. قرارات البتات لم تتغير، لأن الأس ما زال أحد عشر؛ الذي تغير هو تمثيل القوى والمراكم الذي نحفظه بعد الحساب.

المراكم بعد الدورات الأربع يصبح 5 ثم 6 ثم 6 ثم 3. في الثانية نحسب باقي خمسة في أربعة، فيكون باقي عشرين ستة. الثالثة زوجية فلا تضيف عاملًا، ثم نحسب في الأخيرة باقي ستة في أربعة، فيكون باقي أربعة وعشرين ثلاثة. النتيجة توافق أخذ باقي العدد الكامل 48828125 عند 7.

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

عرض الرسم بالحجم الكامل

حالة الأس صفر والمعيار واحد

حين يكون الأس صفرًا، لا تدخل الحلقة أي دورة وترجع الدالة قيمة المراكم المهيأة. في النسخة الكاملة هي واحد وفق تعريف البرنامج لحالة الضرب الخالية، وفي النسخة المعيارية هي باقي واحد عند المعيار. نكتب هذه الحالة ضمن العقد، ولا ندعي أن تنفيذها يحسم كل اصطلاح رياضي قد يناقش الأس الصفري في سياق آخر.

عند معيار واحد يكون باقي كل عدد صحيح صفرًا، فتبدأ النسخة المعيارية بمراكم صفر، وتكون النتيجة صفرًا حتى في حالة الأس صفر. لهذا لا نترك البداية واحدة دون أخذ باقيها ثم نرجعها كما هي عندما لا توجد دورات. هذه حالة صغيرة تفصل التهيئة العددية من التهيئة الموافقة لعقد الباقي.

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

الكود الأصلي وحدود المدخل

الدالة التالية تقبل قاعدة int وأُسًا int غير سالب، ومعيارًا اختياريًا int موجبًا. ترفض bool والعشريات والنصوص في تلك الحقول بدل تحويلها ضمنيًا. نخرج قيمة وتتبّعًا من صفوف تحفظ الحالات قبل التحديث وبعده، مع علم odd والأس التالي والقوة التالية، حتى يمكن إعادة فهم كل قرار في المثال.

لا تستعمل الدالة pow داخل تنفيذها؛ نستعمل تلك الأداة في الفحوص بوصفها مرجعًا آخر. توثق Python أن صورتها ذات الوسيطين تعطي القوة، وأن الصورة ذات معيار تعطي القوة المعيارية، ولها عقود أخرى أوسع من بعض حدودنا. لذلك لا ننسب رفض الأس السالب في كودنا إلى كل استخدام ممكن لـpow في Python.

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

[2]

def power_trace(base, exponent, modulus=None):
    if type(base) is not int or type(exponent) is not int:
        raise TypeError("integer base and exponent required")
    if exponent < 0:
        raise ValueError("nonnegative exponent required")
    if modulus is not None:
        if type(modulus) is not int:
            raise TypeError("integer modulus required")
        if modulus <= 0:
            raise ValueError("positive modulus required")
    result = 1 if modulus is None else 1 % modulus
    power = base if modulus is None else base % modulus
    remaining = exponent
    trace = []
    while remaining:
        before_result, before_power = result, power
        odd = bool(remaining & 1)
        if odd:
            result *= power
            if modulus is not None:
                result %= modulus
        power *= power
        if modulus is not None:
            power %= modulus
        next_remaining = remaining >> 1
        trace.append({"remaining": remaining, "result_before": before_result,
                      "power_before": before_power, "odd": odd,
                      "result_after": result, "next_power": power,
                      "next_remaining": next_remaining})
        remaining = next_remaining
    return {"value": result, "trace": tuple(trace)}

القاعدة السالبة وإشارة النتيجة

نسمح بقاعدة صحيحة سالبة مع أس غير سالب. مثلًا سالب 2 للأس ثلاثة يعطي سالب 8، وللأس أربعة يعطي 16. في القيم الكاملة يظهر اختلاف الإشارة من عدد العوامل السالبة، ولا نزيل الإشارة قبل الحلقة كي نسهل الحساب ثم ندعي أننا حسبنا السؤال الأصلي نفسه.

وفي النسخة المعيارية مع معيار موجب نعرض ممثل الباقي الذي تستعمله عمليات Python في هذا العقد. سالب 8 عند معيار 7 يعطي 6، وهو يوافق كتابة سالب 8 بوصفه مضاعفًا صحيحًا للسبعة زائد ستة. هذا الرقم ليس مقدارًا موجبًا للقوة الكاملة، بل تمثيل لها بحسب المعيار الذي طلبناه.

كما أن القاعدة صفر مع أس موجب حالة عددية مختلفة من معيار صفر المرفوض. لا نخلط اسم الحقلين بسبب ظهور الرقم نفسه. نراجع القاعدة والأس والمعيار كلًا وفق معناه ونوعه، ثم نقرأ result في العقد الكامل أو عقد البواقي الذي اخترناه عند الاستدعاء، لا بحسب الإشارة الظاهرة وحدها.

عدد الضربات يختلف من زمن حساب الأعداد الكبيرة

في تتبع خمسة للأس أحد عشر توجد أربع دورات، وثلاث ضربات للمراكم لأن ثلاثة بتات مختارة، وأربعة تربيعات في هذا الكود. المجموع سبع عمليات ضرب في الحلقة، مع احتساب التربيع الأخير الذي لا نستخدم قوته التالية في دورة جديدة. لا ننقل عددًا من صياغة محسنة أخرى إلى التنفيذ الذي حفظنا صفوفه فعلًا.

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

هذا عد على مستوى العمليات، وليس قياس ثوانٍ أو ذاكرة. القيم الكاملة تكبر، وقد تختلف كلفة ضرب أعداد ذات خانات كثيرة من كلفة أعداد صغيرة. وكذلك سجل التتبع الذي اخترنا حفظه يضيف بيانات مع كل دورة. لم نقس أداءً على أجهزة أو مدخلات كبيرة، فلا نحول قلة الدورات إلى وعد بزمن ثابت لكل قوة أو معيار.

مرجع الضرب المتكرر وpow

للتأكد من القيمة الكاملة، نبدأ في المرجع المستقل بواحد ثم نضرب القاعدة مرة لكل وحدة من الأس. يقارن الاختبار هذه النتيجة بقيمة دالتنا وبـpow، دون قراءة حالات التربيع التي أنتجتها. وللنسخة المعيارية نقارن الباقي بالقيمة المرجعية وبالصورة المعيارية للأداة، ضمن المعايير الموجبة التي أعلنّاها.

نفذنا ذلك على قواعد من سالب ثلاثة إلى ثلاثة، وأسُس من صفر إلى اثني عشر، ومعايير من واحد إلى سبعة. كما راجعنا علاقة الحالة الثابتة في كل صف من التتبع، بصورة كاملة أو معيارية. توافق الجواب النهائي وحده قد يفوت خطأ في حقول شرح الخطوة، ولهذا نحفظ فحص القيم والحالات معًا.

ونضيف المثال الأصلي خمسة للأس أحد عشر، وحالة معيار سبعة، وأُس الصفر والمعيار واحد والمدخلات المرفوضة. هذه فحوص محدودة منفذة، وليست برهانًا لكل نوع عددي أو خاصية إضافية أو مقارنة أداء. نحتاج عقدًا ومرجعًا مناسبين حين نغير النوع أو العملية أو مجال الأس بدل إلحاق امتداد لم نحسبه بالنتائج السابقة.

بطاقة النتيجة والسجل والنسخة

يمكن كتابة بطاقة للقيمة الكاملة: القاعدة خمسة، والأس أحد عشر، ولا معيار، والنتيجة 48828125، والأس الباقي في الدورات 11 و5 و2 و1. نضيف القوى قبل القرار 5 و25 و625 و390625، والمراكم بعده 5 و125 و125 و48828125. هذه الحقول تتيح مراجعة موضع البت الذي لم يدخل في حاصل الضرب.

وللنسخة المعيارية نكتب معيار سبعة ونتيجة ثلاثة، مع القوى 5 و4 و2 و4 والمراكم 5 و6 و6 و3. لا نخلط السجلين أو نعرض بواقي صغيرة كأنها القوى الكاملة التي حصلنا عليها. اختلاف حجم الرقم ليس اختلافًا في سؤال الأس، بل في نوع المخرج الذي طلبناه وأسلوب تمثيله.

قبل استعمال الناتج، راجع أنواع المدخل والأس المسموح والمعيار وحقول before وnext. ثم أعد حساب خطوة صغيرة وتأكد من علاقتها بالحالة الثابتة. ستعرف بذلك ما أنجزه التربيع: قيمة صحيحة أو باقٍ وفق عقد معلن وتتبّع قابل للفحص، دون ادعاء تقريب أو دعم لكل مجال أو زمن تشغيل لم نقسه.