In article <pan.2009.02.18.07.24...@remove.this.cybersource.com.au>,
Steven D'Aprano <ste...@remove.this.cybersource.com.au> wrote:
>> .
>> .
>> .
>>>> And now for my version (which admitedly isn't really mine, and returns
>>>> slightly incorrect fib(n) for large values of n, due to the limited
>>>> floating point precision).
>>>
>>>The floating point version is nice, but it starts giving incorrect
>>>answers relatively early, from n=71. But if you don't need accurate
>>>results (a relative error of 3e-15 for n=71), it is very fast.
>> .
>> .
>> .
>> While my personal opinion is that it's silly to characterize an error of
>> 3e-15 as not "accurate",
>
>That's a *relative* error. The absolute error is 1 for n=71, 59 for n=80,
>1196093 for n=100, and 1875662300654090482610609259 for n=200. As far as
>I can tell, the absolute error grows without bounds as n increases -- and
>it overflows at n=1475.
>
>I agree that a relative error is small, and if your use allows it, then
>by all means use the inexact floating point function. But if you need
>exact results, then you won't get it using floats.
>
>
>
>> I think more constructive is to focus on the
>> fact that the closed-form solution can be touched up to give a precise
>> integral solution, while re- taining its (approximately) O(log n)
>> run-time cost.
>
>I doubt that. Since both phi and sqrt(5) are irrational numbers, it would
>require an infinite number of integer digits to get precise integral
>solutions unless there was some sort of freakish cancellation. But you
>probably could get a very good integral solution which gives exact
>results up to whatever limit you wanted, bound only by the amount of
>memory and time you were willing to spend.
.
.
.
There *is* freakish cancellation.
I entirely recognize that Python builds in floating-point
calculations of limited precision. The closed-form expres-
sion for Fibonacci, though, is exact, and can be coded in
terms of, for example, Python infinite-precision integers.
If there's sufficient interest, I'll cheerfully do so, al-
though only after meeting my own deadlines for February
for commitments outside comp.lang.python.
--
http://mail.python.org/mailman/listinfo/python-list
