Anonymous user
Addition-chain exponentiation: Difference between revisions
fixed error in 2↑15; Also: changed M, initial choice was a mistake, particularly as det M!=1, new M has det of 1
(fixed error in 2↑15; Also: changed M, initial choice was a mistake, particularly as det M!=1, new M has det of 1) |
|||
Line 8:
:<math>a^{15} = a \times (a \times [a \times a^2]^2)^2 \!</math> (binary, 6 multiplications)
:<math>a^{15} = a^3 \times ([a^3]^2)^2 \!</math> (shortest addition chain, 5 multiplications)
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]].
{|class=wikitable
|+Table demonstrating how to do ''Exponentiation'' using ''Addition Chains''
|-
!
|-
|0
|-
|1
|-
|2
|-
|2
|-
|3
|-
|3
|-
|4
|-
|3
|-
|4
|-
|4
|-
|5
|-
|4
|-
|5
|-
|5
|-
|5
|-
|4
|}
The number of multiplications required follows this sequence:
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5,
Line 56:
'''Task requirements:'''
Using the following values:
\sqrt{\frac{1}{2}} & 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 & 0 &\\
0 & 0 & 0 & 0 & 0 & 1 &\\
0 & 0 & 0 & 0 & 1 & 0 &\\
\end{bmatrix}</math> <math>m=31415</math> and <math>n=27182</math>
Repeat task [[Matrix-exponentiation operator]], except use '''addition-chain exponentiation''' to better calculate:
:<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<sup>31415</sup>
* 1.00002550055251<sup>27182</sup>
Also: Display a count of how many multiplications were done in each case.
| |||