what's new about powers ? A003313

[Antti Karttunen]

Jud McCranie wrote:

> At 01:55 AM 11/2/2001 +0200, Antti Karttunen wrote:
>
> >Type a paragraph or two, or in this case, the specific multiplication
> >algorithm from the book, to be included in the comments of A003313,
>
> The algorithm varies depending on n.  The book discusses the factor method,
> the power tree method, and the binary method.  For n < 100000 the power
> tree method is optimal but for a few cases the factor method is best.

Thanks.

Does this "optimality" refer to finding the optimal (i.e. in this case,
the minimal) value of n, or finding what's that minimum value,
in the optimal amount of time?

If what is meant is the former sentence, then could we have sequence
for those n, for which the factor method is the best (or better than
the power tree method)?


Here's again the sequence, if somebody forgot from which sequence we are
talking about:

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


Terveisin,

Antti


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