Inverse function for monotonically increasing function, OverflowError for log10 ()

Question

For assignment, we were asked to create a function that returns the inverse function. The main problem was to create a square root function from a square function. I came up with a solution using binary search and another solution using Newton's method. My solution seems to work fine for the cube root and root, but not for log10. Here are my solutions:

#Binary Search def inverse1(f, delta=1e-8): """Given a function y = f(x) that is a monotonically increasing function on non-negative numbers, return the function x = f_1(y) that is an approximate inverse, picking the closest value to the inverse, within delta.""" def f_1(y): low, high = 0, float(y) last, mid = 0, high/2 while abs(mid-last) > delta: if f(mid) < y: low = mid else: high = mid last, mid = mid, (low + high)/2 return mid return f_1 #Newton Method def inverse(f, delta=1e-5): """Given a function y = f(x) that is a monotonically increasing function on non-negative numbers, return the function x = f_1(y) that is an approximate inverse, picking the closest value to the inverse, within delta.""" def derivative(func): return lambda y: (func(y+delta) - func(y)) / delta def root(y): return lambda x: f(x) - y def newton(y, iters=15): guess = float(y)/2 rootfunc = root(y) derifunc = derivative(rootfunc) for _ in range(iters): guess = guess - (rootfunc(guess)/derifunc(guess)) return guess return newton 

No matter which method is used, when I get the input n = 10000 for log10 () in the professor test function, I get this error: (EXCEPTION: when my newton method function is used, log10 () is disabled, while this binary search method is relatively accurate until the input threshold is reached, in both cases both solutions give this error when n = 10000)

  2: sqrt = 1.4142136 ( 1.4142136 actual); 0.0000 diff; ok 2: log = 0.3010300 ( 0.3010300 actual); 0.0000 diff; ok 2: cbrt = 1.2599211 ( 1.2599210 actual); 0.0000 diff; ok 4: sqrt = 2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 4: log = 0.6020600 ( 0.6020600 actual); 0.0000 diff; ok 4: cbrt = 1.5874011 ( 1.5874011 actual); 0.0000 diff; ok 6: sqrt = 2.4494897 ( 2.4494897 actual); 0.0000 diff; ok 6: log = 0.7781513 ( 0.7781513 actual); 0.0000 diff; ok 6: cbrt = 1.8171206 ( 1.8171206 actual); 0.0000 diff; ok 8: sqrt = 2.8284271 ( 2.8284271 actual); 0.0000 diff; ok 8: log = 0.9030900 ( 0.9030900 actual); 0.0000 diff; ok 8: cbrt = 2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 10: sqrt = 3.1622777 ( 3.1622777 actual); 0.0000 diff; ok 10: log = 1.0000000 ( 1.0000000 actual); 0.0000 diff; ok 10: cbrt = 2.1544347 ( 2.1544347 actual); 0.0000 diff; ok 99: sqrt = 9.9498744 ( 9.9498744 actual); 0.0000 diff; ok 99: log = 1.9956352 ( 1.9956352 actual); 0.0000 diff; ok 99: cbrt = 4.6260650 ( 4.6260650 actual); 0.0000 diff; ok 100: sqrt = 10.0000000 ( 10.0000000 actual); 0.0000 diff; ok 100: log = 2.0000000 ( 2.0000000 actual); 0.0000 diff; ok 100: cbrt = 4.6415888 ( 4.6415888 actual); 0.0000 diff; ok 101: sqrt = 10.0498756 ( 10.0498756 actual); 0.0000 diff; ok 101: log = 2.0043214 ( 2.0043214 actual); 0.0000 diff; ok 101: cbrt = 4.6570095 ( 4.6570095 actual); 0.0000 diff; ok 1000: sqrt = 31.6227766 ( 31.6227766 actual); 0.0000 diff; ok Traceback (most recent call last): File "/CS212/Unit3HW.py", line 296, in <module> print test() File "/CS212/Unit3HW.py", line 286, in test test1(n, 'log', log10(n), math.log10(n)) File "/CS212/Unit3HW.py", line 237, in f_1 if f(mid) < y: File "/CS212/Unit3HW.py", line 270, in power10 def power10(x): return 10**x OverflowError: (34, 'Result too large') 

Here is the test function:

 def test(): import math nums = [2,4,6,8,10,99,100,101,1000,10000, 20000, 40000, 100000000] for n in nums: test1(n, 'sqrt', sqrt(n), math.sqrt(n)) test1(n, 'log', log10(n), math.log10(n)) test1(n, 'cbrt', cbrt(n), n**(1./3.)) def test1(n, name, value, expected): diff = abs(value - expected) print '%6g: %s = %13.7f (%13.7f actual); %.4f diff; %s' %( n, name, value, expected, diff, ('ok' if diff < .002 else '**** BAD ****')) 

Here's how the testing is configured:

 #Using inverse() or inverse1() depending on desired method def power10(x): return 10**x def square(x): return x*x log10 = inverse(power10) def cube(x): return x*x*x sqrt = inverse(square) cbrt = inverse(cube) print test() 

Other published solutions do not seem to have problems with the full set of test inputs (I tried not to look at the published solutions). Any understanding of this error?

---

Consensus seems to be the size of a number, however my professor code works fine for all cases:

 #Prof code: def inverse2(f, delta=1/1024.): def f_1(y): lo, hi = find_bounds(f, y) return binary_search(f, y, lo, hi, delta) return f_1 def find_bounds(f, y): x = 1 while f(x) < y: x = x * 2 lo = 0 if (x ==1) else x/2 return lo, x def binary_search(f, y, lo, hi, delta): while lo <= hi: x = (lo + hi) / 2 if f(x) < y: lo = x + delta elif f(x) > y: hi = x - delta else: return x; return hi if (f(hi) - y < y - f(lo)) else lo log10 = inverse2(power10) sqrt = inverse2(square) cbrt = inverse2(cube) print test() 

Results:

  2: sqrt = 1.4134903 ( 1.4142136 actual); 0.0007 diff; ok 2: log = 0.3000984 ( 0.3010300 actual); 0.0009 diff; ok 2: cbrt = 1.2590427 ( 1.2599210 actual); 0.0009 diff; ok 4: sqrt = 2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 4: log = 0.6011734 ( 0.6020600 actual); 0.0009 diff; ok 4: cbrt = 1.5865107 ( 1.5874011 actual); 0.0009 diff; ok 6: sqrt = 2.4486818 ( 2.4494897 actual); 0.0008 diff; ok 6: log = 0.7790794 ( 0.7781513 actual); 0.0009 diff; ok 6: cbrt = 1.8162270 ( 1.8171206 actual); 0.0009 diff; ok 8: sqrt = 2.8289337 ( 2.8284271 actual); 0.0005 diff; ok 8: log = 0.9022484 ( 0.9030900 actual); 0.0008 diff; ok 8: cbrt = 2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 10: sqrt = 3.1632442 ( 3.1622777 actual); 0.0010 diff; ok 10: log = 1.0009756 ( 1.0000000 actual); 0.0010 diff; ok 10: cbrt = 2.1534719 ( 2.1544347 actual); 0.0010 diff; ok 99: sqrt = 9.9506714 ( 9.9498744 actual); 0.0008 diff; ok 99: log = 1.9951124 ( 1.9956352 actual); 0.0005 diff; ok 99: cbrt = 4.6253061 ( 4.6260650 actual); 0.0008 diff; ok 100: sqrt = 10.0004883 ( 10.0000000 actual); 0.0005 diff; ok 100: log = 2.0009756 ( 2.0000000 actual); 0.0010 diff; ok 100: cbrt = 4.6409388 ( 4.6415888 actual); 0.0007 diff; ok 101: sqrt = 10.0493288 ( 10.0498756 actual); 0.0005 diff; ok 101: log = 2.0048876 ( 2.0043214 actual); 0.0006 diff; ok 101: cbrt = 4.6575475 ( 4.6570095 actual); 0.0005 diff; ok 1000: sqrt = 31.6220242 ( 31.6227766 actual); 0.0008 diff; ok 1000: log = 3.0000000 ( 3.0000000 actual); 0.0000 diff; ok 1000: cbrt = 10.0004883 ( 10.0000000 actual); 0.0005 diff; ok 10000: sqrt = 99.9991455 ( 100.0000000 actual); 0.0009 diff; ok 10000: log = 4.0009756 ( 4.0000000 actual); 0.0010 diff; ok 10000: cbrt = 21.5436456 ( 21.5443469 actual); 0.0007 diff; ok 20000: sqrt = 141.4220798 ( 141.4213562 actual); 0.0007 diff; ok 20000: log = 4.3019052 ( 4.3010300 actual); 0.0009 diff; ok 20000: cbrt = 27.1449150 ( 27.1441762 actual); 0.0007 diff; ok 40000: sqrt = 199.9991455 ( 200.0000000 actual); 0.0009 diff; ok 40000: log = 4.6028333 ( 4.6020600 actual); 0.0008 diff; ok 40000: cbrt = 34.2003296 ( 34.1995189 actual); 0.0008 diff; ok 1e+08: sqrt = 9999.9994545 (10000.0000000 actual); 0.0005 diff; ok 1e+08: log = 8.0009761 ( 8.0000000 actual); 0.0010 diff; ok 1e+08: cbrt = 464.1597912 ( 464.1588834 actual); 0.0009 diff; ok None 

Answer 1

This is actually a problem in your understanding of mathematics instead of a program. The algorithm is perfect, but the initial delivery condition is not.

You define inverse(f, delta) as follows:

 def inverse(f, delta=1e-5): ... def newton(y, iters=15): guess = float(y)/2 ... return newton 

therefore, you will guess that the result 1000 = 10 ^x is 500.0, but of course 10 ^{500 is} too large. The initial assumption must be chosen as valid for f, not selected for the inverse of f.

I assumed that you are initializing with assumption 1, i.e. replace this line with

 guess = 1 

and it should work fine.

---

By the way, your binary initial search condition is also incorrect, because you assume that the solution is between 0 and y:

 low, high = 0, float(y) 

This is true for your test cases, but it's easy to create sample counters, for example. log ₁₀ 0.1 (= -1), & radic; 0.36 (= 0.6), etc. (Your find_bounds method for your solution solves the & radic; 0.36 problem, but still won't process the ₁₀ 0.1 log.)

Answer 2

I traced your error, but this is mainly due to the fact that 10 ** 10000000 causes overflow in python. quick check using math library

 math.pow(10,10000000) Traceback (most recent call last): File "<pyshell#3>", line 1, in <module> math.pow(10,10000000) OverflowError: math range error 

I did a little research for you and found this

Handling large numbers in code

You need to either overestimate why you need to calculate such a large quantity (and change your code accordingly), or start searching for some even larger quantity processing solutions.

You can edit your inverse function to see if certain inputs will lead to it (try statement), which can also solve some problems with zero division, if the functions arent monotonically increasing and avoid OR areas

you can reflect several points in the "interesting" area around y = x and use the interpolation scheme through these points to create the "inverse" function (hermit, Taylor series, etc.).

Answer 3

If you use Python 2.x, int and long are different types, and OverflowError can occur only for ints (qv, Built-in exceptions ). Try explicitly using longs instead (either using the built-in long() function for your integral values, or adding L to numeric literals).

Edit: Obviously, as Pavel Sib and KennyTM pointed out in their excellent answers, this is not a remedy for an algorithmic flaw.