20
$\begingroup$

Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $A^n$ in a structure where multiplication is associative?

For example, suppose $A$ is a square matrix. Matrix multiplication is associative, and I can compute $A^9$ with $4$ multiplications:

$A^2 = A \cdot A$

$A^3 = A^2 \cdot A$

$ A^6 = A^3 \cdot A^3 $ $ A^9 = A^6 \cdot A^3 $

One method which works is to compute $A^{2^i}$ and use the binary representation of $n$, but this is not always optimal, e.g. with $n=23$, we can do it in $6$ multiplications:

$ A^2 = A \cdot A $

$ A^3 = A^2 \cdot A $

$ A^5 = A^3 \cdot A^2 $

$ A^{10} = A^5 \cdot A^5 $

$ A^{20} = A^{10} \cdot A^{10} $

$ A^{23} = A^{20} \cdot A^3 $

rather than $7$:

$ A^2 = A\cdot A $ $ A^4 = A^2 \cdot A^2 $ $ A^8 = A^4 \cdot A^4 $ $ A^{16} = A^8 \cdot A^8 $ $ A^{20} = A^{16} \cdot A^4 $ $ A^{22} = A^{20} \cdot A^2 $ $ A^{23} = A^{22} \cdot A $

Is there an algorithm which gives the quickest way?

  • 6
    @John: Yes, finding the number of multiplications for n=1:200 is [problem 122](http://projecteuler.net/index.php?section=problems&id=122).2010-07-26

6 Answers 6

18

There seems to be no efficient algorithm for this. Quoting Wikipedia on Addition-chain exponentiation:

… 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. Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

On the same page, however, it does link to a reference* of some methods better than binary exponentiation.

One simple example is to use base-N number instead of base-2. e.g. for A510,

with binary:   2 = 1 + 1                3 = 2 + 1                6 = 3 + 3                7 = 6 + 1               14 = 7 + 7               15 = 14 + 1               30 = 15 + 15               31 = 30 + 1               62 = 31 + 31               63 = 62 + 1              126 = 63 + 63              127 = 126 + 1              254 = 127 + 127              255 = 254 + 1              510 = 255 + 255   (15 multiplications)  with base-8:   2 = 1 + 1                3 = 2 + 1                4 = 3 + 1                5 = 4 + 1                6 = 5 + 1                7 = 6 + 1               14 = 7 + 7               28 = 14 + 14               56 = 28 + 28               63 = 56 + 7              126 = 63 + 63              252 = 126 + 126              504 = 252 + 252              510 = 504 + 6      (14 multiplications)  with base-4:   2 = 1 + 1                3 = 2 + 1                4 = 2 + 2                7 = 4 + 3               14 = 7 + 7               28 = 14 + 14               31 = 28 + 3               62 = 31 + 31              124 = 62 + 62              127 = 124 + 3              254 = 127 + 127              508 = 254 + 254              510 = 508 + 2      (13 multiplications) 

(I don't know how to choose the optimal N.)

*: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), pp 129–146

  • 0
    @Kaestur: This shows that algorithm is not optimal.2010-07-26
2

Another option would be to use eigendecomposition . It allows you to raise the eigenvalues in the diagonal of the decomposition A = VDV^-1 to a power. It changes the problem from matrix multiplication to the multiplication of the eigenvalues.

Once in eigendecomposition form you could perform the same addition-chain exponentiation technique but it would be with scalars, not matrices. Much more efficient, because each matrix multiplication has n^3 multiplies, but with ed you would only have n.

More is explained here:

http://en.wikipedia.org/wiki/Matrix_decomposition#Eigendecomposition

  • 0
    Thanks for J. for clearing that up for me.2010-08-06
2

I admit, I'm here doing research on that Project Euler problem. So far, all I can come up with are minimum and maximum values and I'm stuck doing it by eye.

I can verify the 510 example can be done in 11 multiplications.

  1. x*x=x^2
  2. x^2*x=x^3
  3. x^3*x^3=x^6
  4. x^6*x^6=x^12
  5. x^12*x^3=x^15
  6. x^15*x^15=x^30
  7. x^30*x^30=x^60
  8. x^60*x^60=x^120
  9. x^120*x^120=x^240
  10. x^240*x^15=x^255
  11. x^255*x^255=x^510

I can guarantee that's the minimum. Unfortunately, this was an easy example and I'm not sure how to generalize it into a program. At this rate, I may be doing half of the problem by hand...

I'm not sure how much I want to add due to it being a Project Euler problem, but if you express those exponents in binary, I think you may see my strategy, why I thought 510 was an easy example, and why I was so sure it couldn't be reduced to fewer multiplications. And maybe be able to determine some cases where you can't do better than the binary method.

1

This problem looks much like that of finding a ruler of optimal composition of the competing properties to have minimal length and to need only least number of marks. This is then known as the Golomb-ruler -problem. It is not solved but if I recall right there is the method of B. Wichmann, whose solution is always near the optimal. In a german newsgroup we had a discussinon of this and Peter Luschny has set up a page collecting and furtherly developing the discussion and partial solutions ("perfect rulers"). Maybe he has also links to the source-articles of the Wichmann-solution.

Just to show my own fiddling I think there is a good start for developing a strategy. I made a small table of compositions. Though no decisive algorithm pops up it gives at least an impression for a general direction how to construct one. Perhaps helpful....

1

There is a good discussion of this problem, though no final solution, in Volume 2 of Knuth's The Art of Computer Programming.

-2

[Edited:This is about solving the Project Euler problem, and not directly about your question. ] Admittedly, I'm quite late but remember having worked out this problem myself. The quickest cut to the solution is to use this OEIS page .

Add up the right hand entries for the first 200 rows, and you're done.As a general hint to Project Euler problems, when all this much theory is required, avoid writing your own programs and look it up somewhere.

  • 0
    The list of numbers up to 100000 is quite useful for weeding out incorrect algorithms though2016-07-13