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
--
http://mail.python.org/mailman/listinfo/python-list
