Addition-chain exponentiation とは

数学とコンピュータサイエンスでは、最適な加算連鎖累乗は、最小の乗算回数を必要とする正の整数のべき乗によるべき乗の方法です。これは、Integer SequenceのOnline EncyclopediaのA003313の配列に相当します。これは、所望の指数を生成する最短の加算チェーンを作成することによって機能します。チェーン内の各累乗は、前の累乗結果のうちの2つを掛けることによって評価することができます。より一般的には、加算連鎖のべき乗は、(最短の加算連鎖を見つけることが非常に困難であるため)様々なアルゴリズムによって構築された非最小の加算連鎖によるべき乗を指す場合もある。
最短加算連鎖アルゴリズムは、2進累乗より多くの乗算を必要とせず、通常はそれ以下である。バイナリメソッドが6回の乗算を必要とするが、最短加算チェーンが5回だけ必要なa15の場合の最初の例は、
a 15 = a × ( a × [ a × a 2 ] 2 ) 2 {\displaystyle a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}\!} (バイナリ、6回の乗算) a 15 = a 3 × ( [ a 3 ] 2 ) 2 {\displaystyle a^{15}=a^{3}\times ([a^{3}]^{2})^{2}\!} (最短加算チェーン、5回の乗算)
一方、最短加算チェーンの決定は困難である:任意の指数に対して効率的な最適方法は現在知られておらず、与えられた指数セットに対して最短加算チェーンを見つけるという関連問題はNP完全であることが証明されている。加算チェーンの累乗は最短チェーンであっても、バイナリメソッドより多くのメモリを必要とします。これは、チェーンから多くの以前の指数を潜在的に格納する必要があるためです。従って、実際には、最短の加算連鎖累乗は、最短の連鎖があらかじめ計算され、あまり大きくない小さな固定指数に主に使用されます。
最短加算チェーンを近似するためのいくつかの方法もあり、2進法の累乗よりも少ない乗算が必要なことがよくあります。バイナリ累乗自体は準最適な加算チェーンアルゴリズムです。最適なアルゴリズムの選択は、コンテキスト(乗算の相対コストと与えられた指数の再利用回数など)に依存します。
最適な基礎構造を仮定していないため、最短の加算チェーンを見つける問題は動的計画法では解決できません。つまり、より小さなパワーの加算チェーンが(計算を共有するために)関連する可能性があるため、パワーをより小さなパワーに分解するだけでは、それぞれが最小限に計算されるだけでは不十分です。例えば、上記のa15の最短加算チェーンでは、a3が再使用されるので(a6 = a2(a2)2とは対照的に)a6のサブ問題は(a3)2として計算されなければならず、 )。