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

[Billy Mays]

On 08/02/2011 10:15 AM, Steven D'Aprano wrote:
> 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".

Perhaps the individual number is big, but compare that to:

(fibo(n) - fib(n)) / fib(n)

The number is still quite close to the actual answer.

> 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

Yes, I mentioned possibly using the decimal class, which I suppose does 
lose the constant access time depending on how its implemented.

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

Amortized perhaps, but this assumes the call happening a number of 
times.  Also, this requires linear memory to store previous values.

> 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.
>

Not all recursive functions can be memoized (or they can but for 
practically no benefit).  What I was getting at was that a closed form 
expression of a recurrence might be significantly faster at an 
acceptable loss in accuracy.  For an example, see the Ackermann function.

> 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.

I was trying to show that there is an alternate method of calculation. 
Accuracy losses are really a problem with the underlying machinery 
rather than the high level code.  If the recursive form of fib() were 
written in c, the integers would have overflown a long while ago 
compared to float.

One other note, Fibonacci numbers grow exponentially fast (with respect 
to the number of bits), and python's integer multiplication takes 
exponential time (karatsuba rather than fft).  If we are going to 
discuss the behavior of python's numeric types, then lets talk about how 
slow python will become for the nth Fibonacci integer and how much space 
it will take compared to the floating point short concise and almost as 
close form.

--
Bill