where the function has problem? n = 900 is OK , but n = 1000 is ERROR

[Steven D'Aprano]

Billy Mays wrote:

> On 08/02/2011 08:45 AM, Alain Ketterlin wrote:
>> produce integers. And it will fail with overflow for big values.
> 
> If it would make you feel better I can use decimal.
> 
> Also, perhaps I can name my function billy_fibo(n), which is defined as
> billy_fibo(n) +error(n) = fibo(n), where error(n) can be made
> arbitrarily small.

So you say, but I don't believe it. Given fibo, the function you provided
earlier, the error increases with N:

>>> fibo(82) - fib(82)  # fib returns the accurate Fibonacci number
160.0
>>> fibo(182) - fib(182)
2.92786721937918e+23

Hardly "arbitrarily small".


Your function also overflows for N = 1475:

>>> fibo(1475)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in fibo
OverflowError: (34, 'Numerical result out of range')


The correct value only has 307 digits, so it's not that large a number for
integer math. I won't show them all, but it starts and ends like this:

8077637632...87040886025


> This runs in constant time rather than linear  
> (memoized) 

A good memoisation scheme will run in constant time (amortised).


> or exponential (fully recursive) 

Good heavens no. Only the most naive recursive algorithm is exponential.
Good ones (note plural) are linear. Combine that with memoisation, and you
have amortised constant time.


> at the cost of a minutia of accuracy.

I'm reminded of a time my wife was travelling across the US with her band's
roadies. At some point crossing the miles and miles of highway through the
desert, she pointed out that they were lost and nowhere even close to the
city where they were supposed to be playing. The driver answered, "Who
cares, we're making great time!"

(True story.)


> I find this tradeoff acceptable. 

Given that Fibonacci numbers are mostly of interest to number theorists, who
care about the *actual* Fibonacci numbers and not almost-but-not-quite
Fibonacci numbers, I'm having a lot of difficulty imagining what sort of
application you have in mind that could legitimately make that trade-off.



-- 
Steven