21
$\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?

$\endgroup$
2
  • $\begingroup$ Isn't this a Project Euler problem? $\endgroup$ Jul 26, 2010 at 17:34
  • 7
    $\begingroup$ @John: Yes, finding the number of multiplications for n=1:200 is problem 122. $\endgroup$
    – Larry Wang
    Jul 26, 2010 at 18:13

6 Answers 6

19
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 26, 2010 at 15:23
  • $\begingroup$ 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; $\endgroup$
    – Larry Wang
    Jul 26, 2010 at 17:55
  • $\begingroup$ @Kaestur: This shows that algorithm is not optimal. $\endgroup$
    – kennytm
    Jul 26, 2010 at 18:02
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ My intuition tells my that this decomposition is not always useful, can someone who knows more chime in on that? $\endgroup$ Jul 26, 2010 at 21:38
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 6, 2010 at 13:15
  • $\begingroup$ Thanks for J. for clearing that up for me. $\endgroup$ Aug 6, 2010 at 18:36
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Can you explain the downvotes? $\endgroup$
    – Ganesh
    Oct 21, 2011 at 20:55
  • $\begingroup$ Probably the fact that you are relying on someone else's computed answers, rather than explaining how and why the algorithm works, and how to compute arbitrarily big numbers that were not in the published list. $\endgroup$
    – Nayuki
    Jul 13, 2016 at 19:00
  • $\begingroup$ The list of numbers up to 100000 is quite useful for weeding out incorrect algorithms though $\endgroup$
    – Nayuki
    Jul 13, 2016 at 19:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .