can multi-core improve single funciton?
steven at REMOVE.THIS.cybersource.com.au
Wed Feb 18 08:24:35 CET 2009
On Tue, 17 Feb 2009 14:30:27 +0000, Cameron Laird wrote:
> In article <pan.2009.02.10.22.26.39 at REMOVE.THIS.cybersource.com.au>,
> Steven D'Aprano <steven at 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.
More information about the Python-list