Wow! Everybody jumped on the "floating point inaccuracy" topic, I'm

surprised no one tried to find out what the OP was trying to do with his

cube root solver in the first place. Of course, the first-cut approach to

solving the cube root is to raise to the 1/3 power, but this is not the only

possible approach. Assuming that the OP wanted to try to find cube roots

for integers, or raise an exception if the given number is not a perfect

cube, I came up with this:

def cube_root(n):

"A modified Newton's Method solver for integral cube roots."

if int(n) != n:

raise ValueError("must provide an integer")

if n in (-1,0,1): return n

offset = (1,-1)[n > 0]

x = n/2

seen = set()

steps = 0

while 1:

y = x**3

if y == n:

#~ print "Found %d ^ 1/3 = %d in %d steps" % (n,x,steps)

return x

dydx = 3.0*x*x

x += int((n-y)/dydx)+offset

x = x or 1

if x in seen:

raise ValueError("%d is not a perfect cube" % n)

seen.add(x)

steps += 1

This will correctly give 4 for 64, 5 for 125, etc., not 3.99999999999.

Then I went googling for "python cube root", and found this curious

solution:

def root3rd(x):

y, y1 = None, 2

while y!=y1:

y = y1

y3 = y**3

d = (2*y3+x)

y1 = (y*(y3+2*x)+d//2)//d

return y

This only works for perfect cubes, but could be made more robust with this

test just before returning y:

if y*y*y != x:

raise ValueError("%d is not a perfect cube" % x)

I was intrigued at this solution - timing it versus mine showed it to be 5x

faster. I tried to see some sort of Newton's method implementation, but

instead its more of a binary search. This was confirmed by adding this line

inside the while loop:

print y,y1

And to solve for the cube root of 1860867 (123**3), I get this output:

None 2

2 4

4 8

8 16

16 32

32 62

62 105

105 123

with the value 123 returned as the answer. Note that the guess (variable

y1) is initially doubled and redoubled, until the solution is neared. I

tried initializing y1 to a different guess, the original number, and got

this:

None 1860867

1860867 930434

930434 465217

465217 232609

232609 116305

116305 58153

58153 29077

29077 14539

14539 7270

7270 3635

3635 1818

1818 909

909 456

456 235

235 141

141 123

Now the guess is halved each time until nearing the solution, then again

converging to the solution 123.

This algorithm is also robust in that it can do more than just cube roots.

By changing this line:

y3 = y**3

to:

y3 = y**4

We get a 4th root solver! Unfortunately, this breaks down at the 5th root,

as I found solutions would not converge. At this point, I lost interest in

the general applicability of this algorithm, but it is still an interesting

approach - does anyone know the theoretical basis for it?

I guess I was just disappointed that taking cube roots of so small a number

as 64 quickly got us into floating-point roundoff errors, and if the OP is

doing something like looking for perfect cubes, then there are alternatives

to the one-size-fits-almost-all logarithmic implementation of the '**'

operator.

-- Paul

_______________________________________________

Tutor maillist -

[hidden email]
http://mail.python.org/mailman/listinfo/tutor