what's new about powers ?

[Antti Karttunen]

Concerning
ID Number: A003313 (Formerly M0255)
Sequence:  0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4,5,5,6,5,6,6,6,5,6,6,6,6,7,6,
           7,5,6,6,7,6,7,7,7,6,7,7,7,7,7,7,8,6,7,7,7,7,8,7,8,7,8,8,8,7,
           8,8,8,6,7,7,8,7,8,8
Name:      Minimum multiplications to compute n-th power.
References D. E. Knuth, The Art of Computer Programming. Addison-Wesley,

              Reading, MA, Vol. 2, p. 446.
Keywords:  nonn
Offset:    1
Author(s): njas


Jud McCranie wrote:

> At 04:09 PM 11/1/2001 -0500, David W. Wilson wrote:
>
> >Does this sequence relate to addition chains?
>
> Yes it does.  Knuth (vol 2) has it on the same page.

Please people!

Type a paragraph or two, or in this case, the specific multiplication
algorithm from the book, to be included in the comments of A003313,
if you have such secret source of wisdom we others lack.
The current contents of A003313 doesn't tell too much.
(And I don't have money for foreseeable future to buy the bibles...)

Although in this case I guess what is meant here:
 n^4  can be computed by setting A = n*n, and the result is then A*A,
thus total of 2 multiplications needed.
For n^5, we can go A = n*n, B = A*A and the result is B*n, (where A, B,
...
are the free accumulators or stack locations in the abstract machine),
total of 3 multiplications. So it strongly resembles the binary
multiplication
algorithm, from which I guess the connection with the addition chains.
But I could be wrong, as long as there's no further information in
A003313.
(Specifically: does decomposing the exponent/multiplier always
binary-wise give
the minimum value?)

Yours,

Antti Karttunen

>
>
> +---------------------------------------------------------+
> |     Jud McCranie                                        |
> |                                                         |
> | Programming Achieved with Structure, Clarity, And Logic |
> +---------------------------------------------------------+