A New Kind of Science: The NKS Forum > Pure NKS > computing powers of x
Author
sasha

Registered: Oct 2005
Posts: 2

computing powers of x

please excuse my lack of correct mathematical nomenclature, but i am curious if there exists a recursive method (algorithm or function) for computing successive values of x^n that only uses addition.

to be precise, for x^3 successive values are:
1,8,27,64,125,... (for integers)

is there a way to go from 27 to 64 to 125 ... w/o taking in the value of x, only using addition, and staying O(1)? if such a method does exist, is it generic for any power of n ( and still O(1) )? where is/would such a method be useful?

thanks in advance for any insight.

Report this post to a moderator | IP: Logged

10-21-2005 07:11 PM
Val Smith

Registered: Jun 2005
Posts: 39

Are you asking if you can count in any power with addition only? Yes. Try it with tiles and dice. It appears to be generic for any integer power.

Are you asking if you can calculate x^n without using (x-1)^n using addition only? I would not set arbitrary limits on the solution of a problem so I would only know if I found it to be convenient. Especially for a recursive algorithm.

I forgot and can't find the definition for O(1) at the moment. CA's can count in powers in one step per number in the sequence.

Powers seem to be useful for compressing large numbers, and everything is a large number.

__________________
If something is zero, and zero is nothing, then something must be nothing.

Report this post to a moderator | IP: Logged

10-24-2005 11:05 AM
sasha

Registered: Oct 2005
Posts: 2

i've since realized it was fairly trivial.

the O(1) was referring to the amount of calc per step and using (x-1)^n is fine.