can multi-core improve single funciton?

[Steven D'Aprano]

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.



-- 
Steven