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

Question

Vivian Soares · Accepted Answer

Step 1  All you can think of are minimum and maximum values, and you can get stuck doing this by eye. You can check that example 510 can be done in 11 multiplications.  1) x×x=x2  2) x2×x=x3  3) x3×x3=x6  4) x6×x6=x12  5) x12×x3=x15  6) x15×x15=x30  7) x30×x30=x60  8) x60×x60=x120  9) x120×x120=x240  10) x240×x15=x255  11) x255×x255=x510  We can guarantee that this is the minimum. Unfortunately, this was a simple example and we dont

encolatgehu · Accepted Answer

There seems to be no efficient algorithm for this. 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 I don&#039;t know how to choose the optimal N.

karton · Accepted Answer

This is about solving the Project Euler problem, and not directly about your question. Admittedly, Im

Is there an algorithm for working out the best way

Answered question

Answer & Explanation

New Questions in Abstract algebra