الأسس المتسلسلة

في الرياضيات وعلوم الحاسوب ، يُعدّ الرفع الأسي الأمثل باستخدام سلسلة الجمع طريقةً لرفع عددٍ ما إلى أسٍّ صحيحٍ موجبٍ بأقل عددٍ ممكنٍ من عمليات الضرب. باستخدام صيغة أقصر سلسلة جمع ، مع استبدال الجمع بالضرب، يتم حساب الأس المطلوب (بدلاً من مضاعف) للأساس . (يتوافق هذا مع متتالية OEIS A003313 (طول أقصر سلسلة جمع لـ n) ). يمكن تقييم كل عملية رفع أسّي في السلسلة بضرب نتيجتين من نتائج عمليات الرفع الأسّي السابقة. وبشكلٍ أعم، قد يشير الرفع الأسي باستخدام سلسلة الجمع أيضًا إلى الرفع الأسّي باستخدام سلاسل جمع غير دنيا يتم إنشاؤها بواسطة خوارزمياتٍ متنوعة (نظرًا لصعوبة إيجاد أقصر سلسلة جمع).

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

${\displaystyle a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}}$(ثنائي، 6 عمليات ضرب)

${\displaystyle a^{15}=([a^{2}]^{2}\times a)^{3}}$(أقصر سلسلة جمع، 5 عمليات ضرب).

${\displaystyle a^{15}=a^{3}\times ([a^{3}]^{2})^{2}}$(وأيضًا أقصر سلسلة جمع، 5 عمليات ضرب).

من جهة أخرى، يُعدّ تحديد أقصر سلسلة جمع أمرًا صعبًا: فلا توجد حاليًا طرق مثلى فعّالة معروفة للأسس العشوائية، وقد ثبت أن المشكلة ذات الصلة المتمثلة في إيجاد أقصر سلسلة جمع لمجموعة معينة من الأسس هي مسألة NP-كاملة . ^{[ 1 ]} حتى مع وجود أقصر سلسلة، تتطلب عملية الأسس باستخدام سلسلة الجمع ذاكرة أكبر من الطريقة الثنائية، لأنها قد تحتاج إلى تخزين العديد من الأسس السابقة من السلسلة. لذا، عمليًا، تُستخدم عملية الأسس باستخدام أقصر سلسلة جمع بشكل أساسي للأسس الثابتة الصغيرة التي يمكن حساب أقصر سلسلة لها مسبقًا والتي لا تكون كبيرة جدًا.

توجد أيضًا عدة طرق لتقريب أقصر سلسلة جمع، والتي غالبًا ما تتطلب عمليات ضرب أقل من عملية الرفع إلى الأس الثنائي؛ إذ أن الرفع إلى الأس الثنائي نفسه خوارزمية غير مثالية لسلسلة الجمع. يعتمد اختيار الخوارزمية المثلى على السياق (مثل التكلفة النسبية لعملية الضرب وعدد مرات إعادة استخدام أس معين). ^{[ 2 ]}

لا يمكن حل مشكلة إيجاد أقصر سلسلة جمع باستخدام البرمجة الديناميكية ، لأنها لا تحقق فرضية البنية الفرعية المثلى . أي أنه لا يكفي تقسيم القوة إلى قوى أصغر، بحيث تُحسب كل منها بأقل عدد ممكن من العمليات الحسابية، لأن سلاسل الجمع للقوى الأصغر قد تكون مترابطة (لتقاسم العمليات الحسابية). على سبيل المثال، في أقصر سلسلة جمع للعدد 15 ^{المذكور} أعلاه، يجب حساب المسألة الفرعية للعدد 6 ^{على النحو التالي : (a³} ) ² ^، لأن a³ يُعاد استخدامه (على عكس، مثلاً، ^{a⁶ =} a² ( a² ) ^{² ،} والذي يتطلب أيضاً ثلاث عمليات ضرب) .  

إذا سُمح بكل من الضرب والقسمة، فيمكن استخدام سلسلة جمع-طرح  للحصول على عدد أقل من عمليات الضرب والقسمة الإجمالية (حيث يقابل الطرح القسمة). مع ذلك، فإن بطء القسمة مقارنةً بالضرب يجعل هذه الطريقة غير مُجدية عمومًا. أما بالنسبة للأسس السالبة ، فبما أن عملية قسمة واحدة مطلوبة على أي حال، فإن سلسلة الجمع-الطرح غالبًا ما تكون مفيدة. أحد الأمثلة على ذلك هو العدد ^-31 ، حيث يتطلب حساب 1/ a ⁻³¹ باستخدام أقصر سلسلة جمع للعدد 31 ^سبع عمليات ضرب وقسمة واحدة، بينما تتطلب أقصر سلسلة جمع-طرح خمس عمليات ضرب وقسمة واحدة.

${\displaystyle a^{-31}=a/((((a^{2})^{2})^{2})^{2})^{2}}$(سلسلة جمع وطرح، 5 عمليات ضرب + 1 عملية قسمة).

في عملية الأسس على المنحنيات الإهليلجية ، يكون معكوس النقطة ( x , y ) متاحًا بدون تكلفة، لأنه ببساطة ( x , −y )، وبالتالي فإن سلاسل الجمع والطرح هي الأمثل في هذا السياق حتى بالنسبة للأسس الصحيحة الموجبة. ^{[ 3 ]}  

• دونالد إي. كنوث ، فن برمجة الحاسوب، المجلد 2: الخوارزميات شبه العددية ، الطبعة الثالثة، §4.6.3 (أديسون-ويسلي: سان فرانسيسكو، 1998).
• دانيال ج. بيرنشتاين، " خوارزمية بيبنجر "، سيتم دمجها في كتاب المؤلف عن التشفير عالي السرعة . (2002)