Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Isn't this a Project Euler problem? –  John Gietzen Jul 26 '10 at 17:34
5  
@John: Yes, finding the number of multiplications for n=1:200 is problem 122. –  Larry Wang Jul 26 '10 at 18:13

6 Answers 6

up vote 16 down vote accepted

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

share|improve this answer
    
I'm doing something wrong checking the calculation myself, but David Speyer told me once told me that to find the best b you want to minimize some function whose real minimum occurs at e, and so the best base is either 2 or 3. He asked whether you could find a more clever algorithm which improves the run-time to the one you would get if you used "base e" even though that doesn't make sense. –  Noah Snyder Jul 26 '10 at 15:23
    
I think Noah is right. Also, I can do your example in 12: 1+1=2; +1=3; +3=6; +6=12; +12=24; +24=48; +48=96; +96=192; +192=384; +96=480; +24=504; +6=510; –  Larry Wang Jul 26 '10 at 17:55
    
@Kaestur: This shows that algorithm is not optimal. –  KennyTM Jul 26 '10 at 18:02

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.

share|improve this answer

[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.

share|improve this answer
    
Can you explain the downvotes? –  Ganesh Oct 21 '11 at 20:55

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....

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
My intuition tells my that this decomposition is not always useful, can someone who knows more chime in on that? –  Jonathan Fischoff Jul 26 '10 at 21:38
1  
Yes, eigendecomposition is not always useful, most especially if your matrix is "defective" (does not have a complete set of eigenvectors/similar to a "Jordan block" or a matrix with a Jordan block on the diagonal). The Schur decomposition (a similarity transformation of your original matrix to a (quasi)triangular matrix) is what is usually used numerically when evaluating a function of a matrix. On the other hand, for integer exponentiation, I would suppose the research on evaluating matrix polynomials might apply here as well. You might want to look at the Patterson-Stockmayer paper. –  J. M. Aug 6 '10 at 13:15
    
Thanks for J. for clearing that up for me. –  Jonathan Fischoff Aug 6 '10 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.