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?

Vivian Soares

Beginner2022-01-03Added 36 answers

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\times x={x}^{2}$

2)$x}^{2}\times x={x}^{3$

3)$x}^{3}\times {x}^{3}={x}^{6$

4)$x}^{6}\times {x}^{6}={x}^{12$

5)$x}^{12}\times {x}^{3}={x}^{15$

6)$x}^{15}\times {x}^{15}={x}^{30$

7)$x}^{30}\times {x}^{30}={x}^{60$

8)$x}^{60}\times {x}^{60}={x}^{120$

9)$x}^{120}\times {x}^{120}={x}^{240$

10)$x}^{240}\times {x}^{15}={x}^{255$

11)$x}^{255}\times {x}^{255}={x}^{510$

We can guarantee that this is the minimum. Unfortunately, this was a simple example and we dont

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)

2)

3)

4)

5)

6)

7)

8)

9)

10)

11)

We can guarantee that this is the minimum. Unfortunately, this was a simple example and we dont

encolatgehu

Beginner2022-01-04Added 27 answers

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

with binary:

with base-8:

With base-4:

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

karton

Expert2022-01-09Added 613 answers

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

How to find out the mirror image of a point?

Generators of a free group

If G is a free group generated by n elements, is it possible to find an isomorphism of G with a free group generated by n-1 (or any fewer number) of elements?How many 3/4 Are in 1

Convert 10 meters to feet. Round your answer to the nearest tenth

6. Reduce the following matrix to reduced row echelon form:

Let v be a vector over a field F with zero vector 0 and let s,T be a substance of V .then which of the following statements are false

Describe Aut(Zp), the automorphism group of the cyclic group Zp where p is prime. In particular find the order of this group. (Hint: A generator must map to another generator)