Thomas Hartman | 18 Feb 12:58 2007
Picon

speeding up fibonacci with memoizing

I just thought this was interesting, so I would share it.

Thanks to whoever it was on #haskell who helped me, sorry I can't remember who.

-- horribly slow. try slow_fibs 30, not too much higher than that and it hangs
slow_fibs = map slow_fib [1..]
slow_fib 1 = 1
slow_fib 2 = 1
slow_fib n = ( slow_fib (n-2) )  + (slow_fib(n-1))

-- versus, try memoized_fibs !! 10000
memoized_fibs = map memoized_fib [1..]
memoized_fib = ((map fib' [0 ..]) !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)
Felipe Almeida Lessa | 18 Feb 13:38 2007
Picon

Re: speeding up fibonacci with memoizing

On 2/18/07, Thomas Hartman <tphyahoo <at> gmail.com> wrote:
> -- versus, try memoized_fibs !! 10000
> memoized_fibs = map memoized_fib [1..]
> memoized_fib = ((map fib' [0 ..]) !!)
>     where
>       fib' 0 = 0
>       fib' 1 = 1
>       fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)

How about this:
zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)]
zip_fib = (!!) zip_fibs

A naïve performance test:

----------------------------------------------------------------
module Main (main) where

import System (getArgs)

zip_fibs = 0 : 1 : [x+y | ~(x,y) <- zip zip_fibs (tail zip_fibs)]
zip_fib = (!!) zip_fibs

memoized_fibs = map memoized_fib [1..]
memoized_fib = ((map fib' [0 ..]) !!)
   where
     fib' 0 = 0
     fib' 1 = 1
     fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)

(Continue reading)

Yitzchak Gale | 18 Feb 13:50 2007

Re: speeding up fibonacci with memoizing

Besides memoizing, you might want to use the fact
that:

fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
fib (2*k-1) == (fib k)^2 + (fib (k-1))^2

Regards,
Yitz
Felipe Almeida Lessa | 18 Feb 20:58 2007
Picon

Re: speeding up fibonacci with memoizing

On 2/18/07, Yitzchak Gale <gale <at> sefer.org> wrote:
> Besides memoizing, you might want to use the fact
> that:
>
> fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
> fib (2*k-1) == (fib k)^2 + (fib (k-1))^2

Nice one:
$ time ./a.out another_fib 200000
Using 'another_fib' to calculate fib of 200000
 -> 15085683557988938992[...]52246259408175853125

real    0m1.177s
user    0m1.051s
sys     0m0.017s

Implementation details:
-----------------------------------------
another_fibs = 0 : 1 : 1 : map f [3..]
    where
      square x = x * x
      sqfib = square . another_fib
      f n | even n = sqfib (k+1) - sqfib (k-1) where k = n `div` 2
      f n          = sqfib k + sqfib (k-1) where k = (n + 1) `div` 2
another_fib = (!!) another_fibs
-----------------------------------------

Conclusion: it's often better to improve the algorithm than the
implementation =).

(Continue reading)

ajb | 19 Feb 00:15 2007
Picon

Re: speeding up fibonacci with memoizing

G'day all.

On 2/18/07, Yitzchak Gale <gale <at> sefer.org> wrote:

> Besides memoizing, you might want to use the fact
> that:
>
> fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
> fib (2*k-1) == (fib k)^2 + (fib (k-1))^2

Quoting Felipe Almeida Lessa <felipe.lessa <at> gmail.com>:

> Implementation details:
> -----------------------------------------
> another_fibs = 0 : 1 : 1 : map f [3..]
>     where
>       square x = x * x
>       sqfib = square . another_fib
>       f n | even n = sqfib (k+1) - sqfib (k-1) where k = n `div` 2
>       f n          = sqfib k + sqfib (k-1) where k = (n + 1) `div` 2
> another_fib = (!!) another_fibs
> -----------------------------------------

First off, your memo structure is a linked list, which takes O(n) time
to access the nth element.  The first call takes O(n) time, the second
takes O(n/2) time, the third takes O(n/4) time etc etc, so in total, it's
O(n).

That's the same complexity as the naive iterative algorithm:

(Continue reading)

Stefan O'Rear | 19 Feb 04:45 2007
Picon
Picon

Re: speeding up fibonacci with memoizing

Prior art trumps all.  (by a few %)  granted it doesn't do much memoizing anymore :)

gs > ajb > f > d > u, it, z > s > n

stefan <at> stefans:/tmp$ ./h n 42
28.92user 0.14system 0:29.85elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+494minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h d 42
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+254minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h z 100
0.00user 0.00system 0:00.00elapsed 200%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+259minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h z 10000
0.03user 0.00system 0:00.03elapsed 105%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+746minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h z 100000
3.46user 0.02system 0:03.48elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+1981minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h d 100000
1.00user 0.00system 0:01.01elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+759minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h s 100000
3.70user 0.03system 0:03.73elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+2175minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h it 100000
3.43user 0.02system 0:03.46elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+1981minor)pagefaults 0swaps
stefan <at> stefans:/tmp$ ./h u 100000
3.41user 0.03system 0:03.45elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
(Continue reading)

Donald Bruce Stewart | 19 Feb 04:59 2007
Picon
Picon

Re: speeding up fibonacci with memoizing

Would someone please update the entries on our 'archive of fibs' page?

    http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

Cheers.

stefanor:
> Prior art trumps all.  (by a few %)  granted it doesn't do much memoizing anymore :)
> 
> gs > ajb > f > d > u, it, z > s > n
> 
> stefan <at> stefans:/tmp$ ./h n 42
> 28.92user 0.14system 0:29.85elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+494minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h d 42
> 0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+254minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h z 100
> 0.00user 0.00system 0:00.00elapsed 200%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+259minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h z 10000
> 0.03user 0.00system 0:00.03elapsed 105%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+746minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h z 100000
> 3.46user 0.02system 0:03.48elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+1981minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h d 100000
> 1.00user 0.00system 0:01.01elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
> 0inputs+0outputs (0major+759minor)pagefaults 0swaps
> stefan <at> stefans:/tmp$ ./h s 100000
(Continue reading)

ajb | 19 Feb 06:38 2007
Picon

Re: speeding up fibonacci with memoizing

G'day all.

Quoting Stefan O'Rear <stefanor <at> cox.net>:

> Prior art trumps all.  (by a few %)  granted it doesn't do much memoizing
> anymore :)

Ah, butbutbut... of course the Gosper/Salamin one is going to be
faster if you only compute one Fibonacci number per instance.  The
memoed version is optimised for programs that want more than one.

Cheers,
Andrew Bromage
Bertram Felgenhauer | 19 Feb 10:36 2007

Re: speeding up fibonacci with memoizing

Stefan O'Rear wrote:
> Prior art trumps all.  (by a few %)  granted it doesn't do much memoizing anymore :)
> 
> gs > ajb > f > d > u, it, z > s > n

[snip]

Nice. I took the opportunity to polish my generic linear recurrence
module somewhat and test its speed. It does quite well I think:

using
  http://int-e.home.tlink.de/haskell/LinRec.hs

and defining

> import qualified LinRec as L
> 
> -- generic linear recurrence generator
> genfib = L.get [1,1] [0,1]

I get:

# ./t.sh gen 50000000
11.65user 0.06system 0:11.71elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+17092minor)pagefaults 0swaps
# ./t.sh gs 50000000
4.67user 0.06system 0:04.79elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+11746minor)pagefaults 0swaps

for a slowdown of about 2.5.
(Continue reading)

William Lee Irwin III | 19 Feb 06:24 2007

Re: speeding up fibonacci with memoizing

On Sun, Feb 18, 2007 at 06:15:25PM -0500, ajb <at> spamcop.net wrote:
> Now that's an industrial-strength Fibonacci.  It's O(log n) not
> including the cost of adding and multiplying large Integers, and
> uses a bounded amount of memory between calls, making it suitable
> for a library.
> The slowest part of the test program is actually the bit that prints
> the number.  So I used this driver program:

I've been here before.

http://www.haskell.org/pipermail/haskell-cafe/2005-January/008839.html

-- wli
Mikael Johansson | 19 Feb 08:47 2007

Re: speeding up fibonacci with memoizing

On Sun, 18 Feb 2007, Yitzchak Gale wrote:
> Besides memoizing, you might want to use the fact
> that:
>
> fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
> fib (2*k-1) == (fib k)^2 + (fib (k-1))^2
>

Or, you know, go straight to the closed form for the fibonacci numbers! :)

--

-- 
Mikael Johansson                 | To see the world in a grain of sand
mikael <at> johanssons.org            |  And heaven in a wild flower
http://www.mikael.johanssons.org | To hold infinity in the palm of your hand
                                  |  And eternity for an hour
Stefan O'Rear | 19 Feb 09:32 2007
Picon
Picon

Re: speeding up fibonacci with memoizing

On Mon, Feb 19, 2007 at 08:47:39AM +0100, Mikael Johansson wrote:
> On Sun, 18 Feb 2007, Yitzchak Gale wrote:
> >Besides memoizing, you might want to use the fact
> >that:
> >
> >fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
> >fib (2*k-1) == (fib k)^2 + (fib (k-1))^2
> >
> 
> Or, you know, go straight to the closed form for the fibonacci numbers! :)

That's fine in the blessed realm of arithmatic rewrite rules, but
here we need bitstrings, and computing large powers of irrational numbers
is not exactly fast.

Phi is definable in finite fields (modular exponentiation yay!) but modular-ation
seems ... problematic.

I have a gut feeling the p-adic rationals might help, but insufficient knowledge
to formulate code.

The GMP fibbonacci implementation is of my quasilinear recurrence family, not
closed form.

And lest we forget the obvious - by far the fastest way to implement fib in GHC Haskell:

{-# OPTIONS_GHC -O2 -cpp -fglasgow-exts #-}
module 
#ifdef fibimpl
Main(main)
(Continue reading)

Jón Fairbairn | 20 Feb 17:54 2007
X-Face
Picon
Picon

Re: speeding up fibonacci with memoizing

"Thomas Hartman" <tphyahoo <at> gmail.com> writes:

-> I just thought this was interesting, so I would share it.

-> -- versus, try memoized_fibs !! 10000
-> memoized_fibs = map memoized_fib [1..]
-> memoized_fib = ((map fib' [0 ..]) !!)
->     where
->       fib' 0 = 0
->       fib' 1 = 1
->       fib' n = memoized_fib (n - 1) + memoized_fib (n - 2)

I can't let this thread go by without commenting that you
can do something a bit more general by providing a memoising
fixpoint operator that you can reuse for your other awkward
recursive functions:

> module MemoFib where

The unexciting version

> naive_fib 0 = 1
> naive_fib 1 = 1
> naive_fib n = naive_fib (n-1) + naive_fib (n-2)

The memoised version using a memoising fixpoint operator

> fibonacci
>     = memoFix fib
>       where fib fib 0 = 1
(Continue reading)

marnes | 6 Nov 03:34 2007
Picon

Re: speeding up fibonacci with memoizing


  fib :: Integer -> Integer
  fib n = fibaux n 0 1 1
   where
    fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
    fibaux i a b c | i==0 = a
                   | i/=0 = fibaux (i-1) b c (b+c)
Dan Weston | 6 Nov 04:44 2007

Re: Re: speeding up fibonacci with memoizing

Throwing in a trace statement in fibaux tells me that fibaux i a b c is 
not being memoized. If I do map fib [7..9], fibaux counts down to 0 
afresh for each of 7, 8, and 9. Ideally, in map fib [0..n], fib (i-2) 
and fib (i-1) should be memoized and fib i would be evaluated in 
constant time. This is what happens if the loop is unrolled explicitly.

marnes wrote:
>   fib :: Integer -> Integer
>   fib n = fibaux n 0 1 1
>    where
>     fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
>     fibaux i a b c | i==0 = a
>                    | i/=0 = fibaux (i-1) b c (b+c)
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 
Don Stewart | 6 Nov 04:46 2007

Re: Re: speeding up fibonacci with memoizing

If people write any new variants, please add them to:

    http://haskell.org/haskellwiki/The_Fibonacci_sequence

:)

westondan:
> Throwing in a trace statement in fibaux tells me that fibaux i a b c is 
> not being memoized. If I do map fib [7..9], fibaux counts down to 0 
> afresh for each of 7, 8, and 9. Ideally, in map fib [0..n], fib (i-2) 
> and fib (i-1) should be memoized and fib i would be evaluated in 
> constant time. This is what happens if the loop is unrolled explicitly.
> 
> marnes wrote:
> >  fib :: Integer -> Integer
> >  fib n = fibaux n 0 1 1
> >   where
> >    fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
> >    fibaux i a b c | i==0 = a
> >                   | i/=0 = fibaux (i-1) b c (b+c)
> >
> >
> >
> >_______________________________________________
> >Haskell-Cafe mailing list
> >Haskell-Cafe <at> haskell.org
> >http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >
> 
(Continue reading)

Henning Thielemann | 6 Nov 14:56 2007
Picon

Re: Re: speeding up fibonacci with memoizing


On Tue, 6 Nov 2007, marnes wrote:

>
>   fib :: Integer -> Integer
>   fib n = fibaux n 0 1 1
>    where
>     fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
>     fibaux i a b c | i==0 = a
>                    | i/=0 = fibaux (i-1) b c (b+c)

http://www.haskell.org/haskellwiki/Memoization

Gmane