Addition-chain exponentiation: Difference between revisions

On the other hand, the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven [[wp:NP-complete|NP-complete]].

!Number of<br>Multiplications || Actual<br>Exponentiation || Specific implementation of<br>''Addition Chains'' to do Exponentiation

|0|| a¹ || a

|1|| a² || a × a

|2|| a³ || a × a × a

|2|| a⁴ || (a × a→b) × b

|3|| a⁵ || (a × a→b) × b × a

|3|| a⁶ || (a × a→b) × b × b

|4|| a⁷ || (a × a→b) × b × b × a

|3|| a⁸ || ((a × a→b) × b→d) × d

|4|| a⁹ || (a × a × a→c) × c × c

|4|| a¹⁰ || ((a × a→b) × b→d) × d × b

|5|| a¹¹ || ((a × a→b) × b→d) × d × b × a

|4|| a¹² || ((a × a→b) × b→d) × d × d

|5|| a¹³ || ((a × a→b) × b→d) × d × d × a

|5|| a¹⁴ || ((a × a→b) × b→d) × d × d × b

|5|| a¹⁵ || ((a × a→b) × b × a→e) × e × e

|4|| a¹⁶ || (((a × a→b) × b→d) × d→h) × h

<math>A=\begin{bmatrix}

\sqrt{\frac{1}{2}} & 0 &\sqrt{\frac{1}{2}} & 0 & 0 & 0 &\\

0 &\sqrt{\frac{1}{2}} & 0 &\sqrt{\frac{1}{2}} & 0 & 0 &\\

0 &\sqrt{\frac{1}{2}} & 0 &-\sqrt{\frac{1}{2}} & 0 & 0 &\\

-\sqrt{\frac{1}{2}} & 0 &\sqrt{\frac{1}{2}} & 0 & 0 & 0 &\\

0 & 0 & 0 & 0 & 0 & 1 &\\

0 & 0 & 0 & 0 & 1 & 0 &\\

:<math> A ^ {m}</math>, <math>A ^ {n}</math> and <math>A ^ {n \times m}</math>.

As an easier alternative to doing the matrix manipulation above, generate the ''addition-chains'' for 31415 and 27182 and use ''addition-chain exponentiation'' to calculate these two equations:

* 1.00002206445416³¹⁴¹⁵

* 1.00002550055251²⁷¹⁸²