This code gives pretty accurate result when deltanum = 0.0000000000001
but gets into an infinite loop when deltanum = 0.00000000000001
(adding another zero into deltanum
).
It occurs only for non-perfect cubes, it works fine for perfect cubes like 1000. Why?
I am new to programming, following OSSU.
num = 100
high = num
low = 0
icount = 0
cuberoot = (high + low)/2 #cuberoot of num
deltanum = 0.00000000000001
while abs(cuberoot**3 - num)>=deltanum:
icount+=1
print(icount)
if cuberoot**3 > num:
high = cuberoot
elif cuberoot**3 < num:
low = cuberoot
else:
break
cuberoot = (high + low)/2
print("Cube root: " + str(cuberoot))
print("Number of iterations: " + str(icount))
You are using
float
s.float
math is flawed precision wise - your delta might be to small to work correctly and your solution flipps between values without ever reaching yourwhile
conditions limit. See Is floating point math broken? for more reasoning about why float is sometimes "broken".You can limit it to a certain amount of repeats as well:
Output:
Most people would name that
epsilon
, and would usedelta
forcuberoot**3 - num
.Toward the end, you're hoping that this expression,
will buy you approximately one more bit of precision in your answer on each iteration. (Near the beginning it approximately cuts the number of error bits in half each time.)
You're complaining that an IEEE-754 double has limited precision when computing cubes, and also differences. Fifty-three bits gives you almost sixteen decimal digits, and your epsilon is
1e-14
. But an inputnum
that is a few digits long will eat away at your margin, as you found.For higher precision computations, you might prefer to use Decimal. Or, look into the gmp library.
You believe a certain loop invariant holds, that the quanities
cuberoot
andcuberoot ** 3
will change on each iteration. It's simple to verify. Just assign them to temp variables, and verify they change. Terminate the loop early if they don't. More generally, to detect oscillation between a handful of limiting values, put previous values in aset
and terminate early upon seeing a repeat value.