Teddy Dillard

2022-01-02

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?

### Answer & Explanation

Vivian Soares

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={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}$
We can guarantee that this is the minimum. Unfortunately, this was a simple example and we dont

encolatgehu

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 ${A}^{510}$,
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't know how to choose the optimal N.

karton

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

Do you have a similar question?

Recalculate according to your conditions!