can multi-core improve single funciton?

[Niklas Norrthon]

On 10 Feb, 09:45, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:
> On Tue, 10 Feb 2009 18:18:23 +1000, Gerhard Weis wrote:
> > Once I have seen Haskell code, that ran fibonacci on a 4 core system.
>
> > The algorithm itself basically used an extra granularity paramet until
> > which new threads will be sparked. e.g. fib(40, 36) means, calculate
> > fib(40) and spark threads until n=36. 1. divide: fib(n-1), fib(n-2)
> > 2. divide: fib(n-2), fib(n-3)
> > 3. divide: fib(n-3), fib(n-4)
>
> > We tried this code on a 4 core machine using only 1 core and all 4
> > cores. 1 core wallclock: ~10s
> > 4 core wallclock: ~3s
>
> Three seconds to calculate fib(40) is terrible. Well, it's a great saving
> over ten seconds, but it's still horribly, horribly slow.
>
> Check this out, on a two-core 2.2 GHz system:
>
> >>> import timeit
> >>> timeit.Timer('fib(40)', 'from __main__ import fib').timeit(1)
>
> 7.2956085205078125e-05
>
> That's five orders of magnitude faster. How did I do it? I used a better
> algorithm.
>
> def fib(n, a=1, b=1):
>     if n==0:
>         return a
>     elif n==1:
>         return b
>     return fib(n-1, b, a+b)
>
> And for the record:
>
> >>> fib(500)
>
> 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626L

According to the common definition of fibonacci numbers fib(0) = 0, fib
(1) = 1 and fib(n) = fib(n-1) + fib(n-2) for n > 1. So the number
above is fib(501).

>>> timeit.Timer('fib(500)', 'from __main__ import fib').timeit(1)
>
> 0.00083398818969726562

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

>>> import math
>>> sqrt5 = math.sqrt(5)
>>> golden_section = (sqrt5 + 1) / 2
>>> def fib(n):
	return int(golden_section ** n / sqrt5 + 0.5)

>>> fib(501)
225591516161940121919323945317755919750165306733355143970858461525064153963081278412888159063487104942080L

>>> timeit.Timer('fib(501)', 'from __main__ import fib').timeit(1)
1.9555558083084179e-05

>
> Less than a millisecond, versus millions of years for the OP's algorithm.
> I know which I would choose. Faster hardware can only go so far in hiding
> the effect of poor algorithms.
>

I agree 100%

/Niklas Norrthon