Calculating X raised to the 62nd power
J04...@lmsc5.is.lmsc.lockheed.com
Does anyone know how you can compute X raised to the 62nd power using only
eight multiplications ? This is a problem posed in my DATA STRUCTURES
class and I'm getting nowhere.
Thanks in advance.
Michael Jones
Sorry, I only know how to do it using seven. (I guess you could always do
an extra multiply by 1 if it just has to be eight. ;-) I think there's a
how-to table for multipliers up to 100 on page 446 of some book.
--
Be seeing you, m...@sgi.com 415.390.1455 M/S 7L-590
Michael Jones Silicon Graphics, Advanced Graphics Division
2011 N. Shoreline Blvd., Mtn. View, CA 94039-7311
Jeff James
J04...@LMSC5.IS.LMSC.LOCKHEED.COM writes:
Decompose your power into a sum of powers of 2. Produce x^(2^i) by
repetetive squaring and multiply those necessary to add up the power. This
takes 2(n-1) multiplies for any power up to 2^n, which is nine in your
case. Hack: compute x^2 and x^64 in five multiplies, then divide.
Jeff
Nancy McGough
This was a nice problem. How's this:
1] X * X = X^2
2] X^2 * X^2 = X^4
3] X^4 * X^4 = X^8
4] X^2 * X^8 = X^10
5] X^10 * X^10 = X^20
6] X^20 * X^20 = X^40
7] X^40 * X^20 = X^60
8] X^60 * X^2 = X^62
Nancy
Nancy McGough
This was a nice problem. How's this:
Bruce Bowen
Normally, I don't do homework, but this problem looks too trivial to pass up.
62
X = ((((X^2)^2)^2)^2 * ((X^2)^2)^2 * ((X^2)^2) * X^2 * X)^2
Well, maybe it's not too trivial. The above involves *9* multiplications.
Perhaps you can't do it in 8; but you can do it in 6 multiplies and one divide,
ie. (X^32 / X )^2.
-Bruce
Erick Bryce Wong
> Well, maybe it's not too trivial. The above involves *9* multiplications.
>Perhaps you can't do it in 8; but you can do it in 6 multiplies and one divide,
>ie. (X^32 / X )^2.
It can certainly be done in 8, as another poster pointed out...The solution I
found was only slightly different from hers, I had:
1) X^2 = X * X
2) X^3 = X^2 * X
3) X^6 = X^3 * X^3
4) X^12 = X^6 * X^6
5) X^24 = X^12 * X^12
6) X^48 = X^24 * X^24
7) X^60 = X^48 * X^12
8) X^62 = X^60 * X^2
Both solutions involved straying away from powers of two, as 62 has 5 one bits
in binary, so the routine way isn't good enough. This raises the question,
is it possible to do it in less than 8, and if not, can we prove why not?
(It can't be done in 5, because, X^32 is (I think) the largest possible power
attainable in 5 multiplications, and probably not 6 for a similar reason).
--
-- Erick, the smallest number expressible as the sum of two distinct triangle
numbers in two distinct ways.
David Bradley
>This raises the question, is it possible to do it in less than 8
>[multiplications] , and if not, can we prove why not?
>(It can't be done in 5, because, X^32 is (I think) the largest possible power
>attainable in 5 multiplications, and probably not 6 for a similar reason).
This leads me to ask: What is known about M(k), the least number of
multiplications needed to produce x^k starting with x? (No divisions
allowed.)
I'd guess there probably is no formula or simple criterion for
determining M(k) except when k has various special forms, eg. a power of
2, etc. Perhaps someone can confirm or deny this.
-D.M.Bradley
Mark
>This leads me to ask: What is known about M(k), the least number of
>multiplications needed to produce x^k starting with x? (No divisions
>allowed.)
This is but a special case of the more general problem:
What is the minimum number of additions, starting with 1, needed to get
a given finite subset S = {a1, a2, ..., aN } (1 <= a1 <= a2 <= ... <= aN)?
Call it f(S).
This is easily answered:
f(0) = 0
f(S) = f(S - {1})
f(S) = min 1 <= i <= m - 1: f(S - {m} + {i, m - i})
where m = max(S) (i.e., aN).
Then your N(k) is just f({k}).
This is the simplest possible problem with an easy inductive definition
that includes the N(k) problem as a special case.
Robert D. Silverman
:
:>This raises the question, is it possible to do it in less than 8
:>[multiplications] , and if not, can we prove why not?
It can be done in 6 plus a single divison. (x^64/x^4; or (x^32/x)^2)
:>(It can't be done in 5, because, X^32 is (I think) the largest possible power
:>attainable in 5 multiplications, and probably not 6 for a similar reason).
:
:This leads me to ask: What is known about M(k), the least number of
:multiplications needed to produce x^k starting with x? (No divisions
:allowed.)
:
:I'd guess there probably is no formula or simple criterion for
:determining M(k) except when k has various special forms, eg. a power of
:2, etc. Perhaps someone can confirm or deny this.
See Knuth Vol 2. ; the section on addition chains
One can come very close to an optimal addition chain by a method I
don't believe Knuth mentions; Look at the convergents of the continued
fraction expansion for (1+sqrt(5))/2. [Think Fibonacci/Lucas numbers]
There is no known simple method [so far as I known] for finding an optimal
addition chain.
One can compute x^N on O(log N) multiplications. The binary method
achieves 1.5 log N worst case; it can be improved in a fairly simple
way by the binary/trinary method to 1.33 log N worst case. One can't
ever do better than log N.
--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"
Bruce Karsh
Normally, I wouldn't give away the answer to a class problem. But some
correct answers have already been posted.
I ran an exhaustive search and found 233 solutions. Is there a better
way than running a huge search?
Here are the solutions I found, in case anyone's interested.
1 2 3 4 7 14 17 31 62
1 2 3 4 7 14 28 31 62
1 2 3 5 7 12 19 31 62
1 2 3 5 7 12 24 31 62
1 2 3 5 7 14 17 31 62
1 2 3 5 7 14 28 31 62
1 2 3 5 8 13 18 31 62
1 2 3 5 8 13 26 31 62
1 2 3 5 10 11 20 31 62
1 2 3 5 10 11 21 31 62
1 2 3 5 10 13 18 31 62
1 2 3 5 10 13 26 31 62
1 2 3 5 10 13 26 36 62
1 2 3 5 10 13 26 52 62
1 2 3 5 10 15 16 31 62
1 2 3 5 10 15 30 31 62
1 2 3 5 10 15 30 32 62
1 2 3 5 10 15 30 60 62
1 2 3 5 10 20 21 31 62
1 2 3 5 10 20 21 41 62
1 2 3 5 10 20 21 42 62
1 2 3 5 10 20 22 40 62
1 2 3 5 10 20 22 42 62
1 2 3 5 10 20 30 31 62
1 2 3 5 10 20 30 32 62
1 2 3 5 10 20 30 60 62
1 2 3 5 10 20 40 42 62
1 2 3 5 10 20 40 60 62
1 2 3 6 7 12 19 31 62
1 2 3 6 7 12 24 31 62
1 2 3 6 7 14 17 31 62
1 2 3 6 7 14 28 31 62
1 2 3 6 7 14 28 34 62
1 2 3 6 7 14 28 56 62
1 2 3 6 8 14 17 31 62
1 2 3 6 8 14 28 31 62
1 2 3 6 8 14 28 34 62
1 2 3 6 8 14 28 56 62
1 2 3 6 9 11 20 31 62
1 2 3 6 9 11 22 31 62
1 2 3 6 9 15 16 31 62
1 2 3 6 9 15 30 31 62
1 2 3 6 9 15 30 32 62
1 2 3 6 9 15 30 60 62
1 2 3 6 12 13 18 31 62
1 2 3 6 12 13 19 31 62
1 2 3 6 12 13 25 31 62
1 2 3 6 12 13 25 37 62
1 2 3 6 12 13 25 50 62
1 2 3 6 12 14 17 31 62
1 2 3 6 12 14 24 38 62
1 2 3 6 12 14 24 48 62
1 2 3 6 12 14 28 31 62
1 2 3 6 12 14 28 34 62
1 2 3 6 12 14 28 56 62
1 2 3 6 12 15 16 31 62
1 2 3 6 12 15 30 31 62
1 2 3 6 12 15 30 32 62
1 2 3 6 12 15 30 60 62
1 2 3 6 12 18 19 31 62
1 2 3 6 12 18 30 31 62
1 2 3 6 12 18 30 32 62
1 2 3 6 12 18 30 60 62
1 2 3 6 12 24 25 31 62
1 2 3 6 12 24 25 37 62
1 2 3 6 12 24 25 50 62
1 2 3 6 12 24 26 36 62
1 2 3 6 12 24 26 38 62
1 2 3 6 12 24 26 50 62
1 2 3 6 12 24 30 31 62
1 2 3 6 12 24 30 32 62
1 2 3 6 12 24 30 60 62
1 2 3 6 12 24 36 38 62
1 2 3 6 12 24 36 60 62
1 2 3 6 12 24 48 50 62
1 2 3 6 12 24 48 60 62
1 2 4 5 7 12 19 31 62
1 2 4 5 7 12 24 31 62
1 2 4 5 8 13 18 31 62
1 2 4 5 8 13 26 31 62
1 2 4 5 9 11 20 31 62
1 2 4 5 9 11 22 31 62
1 2 4 5 9 13 18 31 62
1 2 4 5 9 13 22 31 62
1 2 4 5 9 13 26 31 62
1 2 4 5 9 18 22 31 62
1 2 4 5 9 18 22 40 62
1 2 4 5 9 18 22 44 62
1 2 4 5 9 18 27 31 62
1 2 4 5 10 11 20 31 62
1 2 4 5 10 11 21 31 62
1 2 4 5 10 14 24 38 62
1 2 4 5 10 14 24 48 62
1 2 4 5 10 15 16 31 62
1 2 4 5 10 15 30 31 62
1 2 4 5 10 15 30 32 62
1 2 4 5 10 15 30 60 62
1 2 4 5 10 20 21 31 62
1 2 4 5 10 20 21 41 62
1 2 4 5 10 20 21 42 62
1 2 4 5 10 20 22 40 62
1 2 4 5 10 20 22 42 62
1 2 4 5 10 20 30 31 62
1 2 4 5 10 20 30 32 62
1 2 4 5 10 20 30 60 62
1 2 4 5 10 20 40 42 62
1 2 4 5 10 20 40 60 62
1 2 4 6 7 12 19 31 62
1 2 4 6 7 12 24 31 62
1 2 4 6 7 14 28 34 62
1 2 4 6 7 14 28 56 62
1 2 4 6 8 14 28 34 62
1 2 4 6 8 14 28 56 62
1 2 4 6 10 11 20 31 62
1 2 4 6 10 11 21 31 62
1 2 4 6 10 14 24 38 62
1 2 4 6 10 14 24 48 62
1 2 4 6 10 14 28 34 62
1 2 4 6 10 14 28 56 62
1 2 4 6 10 16 26 36 62
1 2 4 6 10 16 26 52 62
1 2 4 6 10 20 21 31 62
1 2 4 6 10 20 21 41 62
1 2 4 6 10 20 21 42 62
1 2 4 6 10 20 22 40 62
1 2 4 6 10 20 22 42 62
1 2 4 6 10 20 26 36 62
1 2 4 6 10 20 26 52 62
1 2 4 6 10 20 30 31 62
1 2 4 6 10 20 30 32 62
1 2 4 6 10 20 30 60 62
1 2 4 6 10 20 40 42 62
1 2 4 6 10 20 40 60 62
1 2 4 6 12 13 18 31 62
1 2 4 6 12 13 19 31 62
1 2 4 6 12 13 25 31 62
1 2 4 6 12 13 25 37 62
1 2 4 6 12 13 25 50 62
1 2 4 6 12 14 24 38 62
1 2 4 6 12 14 24 48 62
1 2 4 6 12 14 28 34 62
1 2 4 6 12 14 28 56 62
1 2 4 6 12 16 28 34 62
1 2 4 6 12 16 28 56 62
1 2 4 6 12 18 19 31 62
1 2 4 6 12 18 22 40 62
1 2 4 6 12 18 22 44 62
1 2 4 6 12 18 30 31 62
1 2 4 6 12 18 30 32 62
1 2 4 6 12 18 30 60 62
1 2 4 6 12 24 25 31 62
1 2 4 6 12 24 25 37 62
1 2 4 6 12 24 25 50 62
1 2 4 6 12 24 26 36 62
1 2 4 6 12 24 26 38 62
1 2 4 6 12 24 26 50 62
1 2 4 6 12 24 28 34 62
1 2 4 6 12 24 28 56 62
1 2 4 6 12 24 30 31 62
1 2 4 6 12 24 30 32 62
1 2 4 6 12 24 30 60 62
1 2 4 6 12 24 36 38 62
1 2 4 6 12 24 36 60 62
1 2 4 6 12 24 48 50 62
1 2 4 6 12 24 48 60 62
1 2 4 8 9 11 20 31 62
1 2 4 8 9 11 22 31 62
1 2 4 8 9 13 18 31 62
1 2 4 8 9 13 22 31 62
1 2 4 8 9 18 22 31 62
1 2 4 8 9 18 22 40 62
1 2 4 8 9 18 22 44 62
1 2 4 8 9 18 26 36 62
1 2 4 8 9 18 26 44 62
1 2 4 8 9 18 27 31 62
1 2 4 8 9 18 27 35 62
1 2 4 8 9 18 27 54 62
1 2 4 8 9 18 36 44 62
1 2 4 8 9 18 36 54 62
1 2 4 8 10 11 20 31 62
1 2 4 8 10 11 21 31 62
1 2 4 8 10 14 24 38 62
1 2 4 8 10 14 24 48 62
1 2 4 8 10 16 26 36 62
1 2 4 8 10 16 26 52 62
1 2 4 8 10 18 22 40 62
1 2 4 8 10 18 22 44 62
1 2 4 8 10 18 26 36 62
1 2 4 8 10 18 26 44 62
1 2 4 8 10 18 26 52 62
1 2 4 8 10 18 36 44 62
1 2 4 8 10 18 36 54 62
1 2 4 8 10 20 21 31 62
1 2 4 8 10 20 21 41 62
1 2 4 8 10 20 21 42 62
1 2 4 8 10 20 22 40 62
1 2 4 8 10 20 22 42 62
1 2 4 8 10 20 30 31 62
1 2 4 8 10 20 30 32 62
1 2 4 8 10 20 30 60 62
1 2 4 8 10 20 40 42 62
1 2 4 8 10 20 40 60 62
1 2 4 8 12 13 25 37 62
1 2 4 8 12 13 25 50 62
1 2 4 8 12 14 24 38 62
1 2 4 8 12 14 24 48 62
1 2 4 8 12 20 21 41 62
1 2 4 8 12 20 21 42 62
1 2 4 8 12 20 22 40 62
1 2 4 8 12 20 22 42 62
1 2 4 8 12 20 40 42 62
1 2 4 8 12 20 40 60 62
1 2 4 8 12 24 25 37 62
1 2 4 8 12 24 25 50 62
1 2 4 8 12 24 26 36 62
1 2 4 8 12 24 26 38 62
1 2 4 8 12 24 26 50 62
1 2 4 8 12 24 36 38 62
1 2 4 8 12 24 36 60 62
1 2 4 8 12 24 48 50 62
1 2 4 8 12 24 48 60 62
1 2 4 8 16 18 22 40 62
1 2 4 8 16 18 22 44 62
1 2 4 8 16 18 26 36 62
1 2 4 8 16 18 26 44 62
1 2 4 8 16 18 36 44 62
1 2 4 8 16 18 36 54 62
1 2 4 8 16 20 21 41 62
1 2 4 8 16 20 21 42 62
1 2 4 8 16 20 22 40 62
1 2 4 8 16 20 22 42 62
1 2 4 8 16 20 40 42 62
1 2 4 8 16 20 40 60 62
Brian Borchers
number of multiplications. I suppose that this was the intent of the
exercise...
Brian Borchers borc...@nmt.edu
Department of Mathematics 505-835-5813
New Mexico Tech
Socorro, NM 87801
David Petry
>In article <93099.569...@LMSC5.IS.LMSC.LOCKHEED.COM> J04...@LMSC5.IS.LMSC.LOCKHEED.COM writes:
>>Does anyone know how you can compute X raised to the 62nd power using only
>>eight multiplications ? This is a problem posed in my DATA STRUCTURES
>>class and I'm getting nowhere.
>Normally, I wouldn't give away the answer to a class problem. But some
>correct answers have already been posted.
>
>I ran an exhaustive search and found 233 solutions. Is there a better
>way than running a huge search?
>
>Here are the solutions I found, in case anyone's interested.
The list Mr. Karsh gives is not quite exhaustive. For example, consider
the entries:
> 1 2 4 6 8 14 28 34 62
> 1 2 4 6 8 14 28 56 62
In these two sequences, 8 could be computed either by adding 4 to itself,
or by adding 2 and 6, thus giving two additional ways of solving the problem
which don't appear in his list.
David Petry
Tony Davie
Calculate x^2=x * x
x^3=x^2 * x
x^5=x^3 * x^2
x^10=x^5 * x^5
x^15=x^10 * x^5
x^30=x^15 * x^15
x^60=x^30 * x^30
x^62=x^60 * x^2
I don't know a systematic way of doing this but "Seminumerical Algorithms" by
D. Knuth says something about it all. Hope this helps
Tony Davie
Dave Dodson
Since this is a data structures class, have you considered how you could
use a directed graph with 8 nodes to represent a particular method of
calculating x^n with 8 multiplications? It seems like you then need to
search through the space of such graphs for one that computes x^62.
----------------------------------------------------------------------
Dave Dodson dod...@convex.com
Convex Computer Corporation Richardson, Texas (214) 497-4234
Dave Dodson
Since this is a data structures class, have you considered how you could
Tony Davie
which raises the additional question - How many ways are there of calculating
x^N in M multiplations?
Dipankar Gupta
TD> which raises the additional question - How many ways are there of calculating
TD> x^N in M multiplations?
This is the ``addition chain'' problem and has a fairly long history.
Look up Knuth's ``Seminumerical Algorithms'' pp 444-462 for a
wonderful description.
Cheers,
Dipankar