user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Addition-chain exponentiation. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

In cases of special objects (such as with matrices) the operation of multiplication can be excessively expensive. In these cases the operation of multiplication should be avoided or reduced to a minimum.

In mathematics and computer science, optimal **addition-chain exponentiation** is a method of exponentiation by positive integer powers that requires a minimal number of multiplications. It works by creating a shortest addition chain that generates the desired exponent. Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally, *addition-chain exponentiation* may also refer to exponentiation by non-minimal addition chains constructed by a variety of algorithms (since a shortest addition chain is very difficult to find).

The shortest addition-chain algorithm requires no more multiplications than binary exponentiation and usually less. The first example of where it does better is for 

a

15
{\displaystyle {\displaystyle a^{15}}}
, where the binary method needs six multiplies but a shortest addition chain requires only five:

:   a

    15
    =
    a
    ×
    (
    a
    ×
    [
    a
    ×

    a

    2

    ]

    2

    )

    2

    {\displaystyle {\displaystyle a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}\!}}
     (binary, 6 multiplications)
:   a

    15
    =

    a

    3
    ×
    (
    [

    a

    3

    ]

    2

    )

    2

    {\displaystyle {\displaystyle a^{15}=a^{3}\times ([a^{3}]^{2})^{2}\!}}
     (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 NP-complete.

Table demonstrating how to do *Exponentiation* using *Addition Chains*

| Number of Multiplications | Actual Exponentiation | Specific implementation of *Addition Chains* to do Exponentiation |
| --- | --- | --- |
| 0 | a1 | a |
| 1 | a2 | a × a |
| 2 | a3 | a × a × a |
| 2 | a4 | (a × a→b) × b |
| 3 | a5 | (a × a→b) × b × a |
| 3 | a6 | (a × a→b) × b × b |
| 4 | a7 | (a × a→b) × b × b × a |
| 3 | a8 | ((a × a→b) × b→d) × d |
| 4 | a9 | (a × a × a→c) × c × c |
| 4 | a10 | ((a × a→b) × b→d) × d × b |
| 5 | a11 | ((a × a→b) × b→d) × d × b × a |
| 4 | a12 | ((a × a→b) × b→d) × d × d |
| 5 | a13 | ((a × a→b) × b→d) × d × d × a |
| 5 | a14 | ((a × a→b) × b→d) × d × d × b |
| 5 | a15 | ((a × a→b) × b × a→e) × e × e |
| 4 | a16 | (((a × a→b) × b→d) × d→h) × h |

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,
6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6,
7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7,
8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 7,
8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 8, 8, 8, 8...

This sequence can be found at: http://oeis.org/A003313

**Task requirements:**

Using the following values:

A
=


[

1
2

0

1
2

0

0

0

0

1
2

0

1
2

0

0

0

1
2

0

−

1
2

0

0

−

1
2

0

1
2

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

]
{\displaystyle {\displaystyle 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&\\\end{bmatrix}}}}
 

m
=
31415
{\displaystyle {\displaystyle m=31415}}
 and 

n
=
27182
{\displaystyle {\displaystyle n=27182}}

Repeat task Matrix-exponentiation operator, except use **addition-chain exponentiation** to better calculate:

:   A

    m
    {\displaystyle {\displaystyle A^{m}}}
    , 

    A

    n
    {\displaystyle {\displaystyle A^{n}}}
     and 

    A

    n
    ×
    m
    {\displaystyle {\displaystyle A^{n\times m}}}
    .

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

* 1.0000220644541631415
* 1.0000255005525127182

Also: Display a count of how many multiplications were done in each case.

Note: There are two ways to approach this task:

* Brute force - try every permutation possible and pick one with the least number of multiplications. If the brute force is a simpler algorithm, then present it as a subtask under the subtitle "Brute force", eg ===Brute Force===.
* Some clever algorithm - the wikipedia page has some hints, subtitle the code with the name of algorithm.

Note: Binary exponentiation does not usually produce the best solution. Provide only optimal solutions.

Kudos (κῦδος) for providing a routine that generate sequence A003313 in the output.

Also, see the Rosetta Code task:   [http://rosettacode.org/wiki/Knuth%27s\_power\_tree
Knuth's power tree].
assistant
**Translation of**: Python

```
# 20230327 Raku programming solution

use Math::Matrix;

class AdditionChains { has ( $.idx, $.pos, @.chains, @.lvl, %.pat ) is rw; 

   method add_chain { 
      # method 1: add chains depth then breadth first until done 
      return gather given self { 
         take my $newchain = .chains[.idx].clone.append: 
            .chains[.idx][*-1] + .chains[.idx][.pos];
	     .chains.append: $newchain;
         .pos == +.chains[.idx]-1 ?? ( .idx += 1 && .pos = 0 ) !! .pos += 1;
      }
   }

   method find_chain(\nexp where nexp > 0) {
   # method 1 interface: search for chain ending with n, adding more as needed
      return ([1],) if nexp == 1;
      my @chn = self.chains.grep: *.[*-1] == nexp // [];
      unless @chn.Bool { 
         repeat { @chn = self.add_chain } until @chn[*-1][*-1] == nexp 
      }
      return @chn
   }

   method knuth_path(\ngoal) {
      # method 2: knuth method, uses memoization to search for a shorter chain
      return [] if ngoal < 1; 
      until self.pat{ngoal}:exists {
         self.lvl[0] = [ gather for self.lvl[0].Array -> \i {
            for self.knuth_path(i).Array -> \j {
               unless self.pat{i + j}:exists {
                  self.pat{i + j} = i and take i + j
               }
            }
         } ] 
      }
      return self.knuth_path(self.pat{ngoal}).append: ngoal
   }

   multi method cpow(\xbase, \chain) {
#  raise xbase by an addition exponentiation chain for what becomes x**chain[-1]
      my ($pows, %products) = 0, 1 => xbase;

      %products{0} = xbase ~~ Math::Matrix 
         ?? Math::Matrix.new([ [ 1 xx xbase.size[1] ] xx xbase.size[0] ]) !! 1;

      for chain.Array -> \i {
         %products{i} = %products{$pows} * %products{i - $pows};
         $pows = i
      }
      return %products{ chain[*-1] }
   }
}

my $chn =  AdditionChains.new( idx    =>      0, pos =>      0, 
                               chains => ([1],), lvl => ([1],), pat => {1=>0} );

say 'First one hundred addition chain lengths:';
.Str.say for ( (1..100).map: { +$chn.find_chain($_)[0] - 1 } ).rotor: 10;

my %chns = (31415, 27182).map: { $_ => $chn.knuth_path: $_ };

say "\nKnuth chains for addition chains of 31415 and 27182:";
say "Exponent: $_\n  Addition Chain: %chns{$_}[0..*-2]" for %chns.keys;
say '1.00002206445416^31415 = ', $chn.cpow(1.00002206445416, %chns{31415});
say '1.00002550055251^27182 = ', $chn.cpow(1.00002550055251, %chns{27182});
say '(1.000025 + 0.000058i)^27182 = ', $chn.cpow: 1.000025+0.000058i, %chns{27182};
say '(1.000022 + 0.000050i)^31415 = ', $chn.cpow: 1.000022+0.000050i, %chns{31415};

my \sq05 = 0.5.sqrt;
my \mat  = Math::Matrix.new( [[sq05,    0, sq05,     0, 0, 0], 
                             [    0, sq05,    0,  sq05, 0, 0], 
                             [    0, sq05,    0, -sq05, 0, 0],
                             [-sq05,    0, sq05,     0, 0, 0], 
                             [    0,    0,    0,     0, 0, 1], 
                             [    0,    0,    0,     0, 1, 0]] );

say 'matrix A ^ 27182 =';
say my $res27182 = $chn.cpow(mat, %chns{27182});
say 'matrix A ^ 31415 =';
say $chn.cpow(mat, %chns{31415});
say '(matrix A ** 27182) ** 31415 =';
say $chn.cpow($res27182, %chns{31415});

```

Output:

```
First one hundred addition chain lengths:
0 1 2 2 3 3 4 3 4 4
5 4 5 5 5 4 5 5 6 5
6 6 6 5 6 6 6 6 7 6
7 5 6 6 7 6 7 7 7 6
7 7 7 7 7 7 8 6 7 7
7 7 8 7 8 7 8 8 8 7
8 8 8 6 7 7 8 7 8 8
9 7 8 8 8 8 8 8 9 7
8 8 8 8 8 8 9 8 9 8
9 8 9 9 9 7 8 8 8 8

Knuth chains for addition chains of 31415 and 27182:
Exponent: 27182
  Addition Chain: 1 2 3 5 7 14 21 35 70 140 143 283 566 849 1698 3396 6792 6799 13591
Exponent: 31415
  Addition Chain: 1 2 3 5 7 14 28 56 61 122 244 488 976 1952 3904 7808 15616 15677 31293
1.00002206445416^31415 = 1.9999999998924638
1.00002550055251^27182 = 1.999999999974053
(1.000025 + 0.000058i)^27182 = -0.01128636963542673+1.9730308496660347i
(1.000022 + 0.000050i)^31415 = 0.00016144681325535107+1.9960329014194498i
matrix A ^ 27182 =
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  1
  0  0  0  0  1  0
matrix A ^ 31415 =
   0  0  0   0  0  0
   0  0  0   0  0  0
   0  0  0  -0  0  0
  -0  0  0   0  0  0
   0  0  0   0  0  1
   0  0  0   0  1  0
(matrix A ** 27182) ** 31415 =
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  1
  0  0  0  0  1  0
```