18 Feb 12:58 2007

## 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)
```
18 Feb 13:38 2007

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

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)

```

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
```
18 Feb 20:58 2007

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

```

19 Feb 00:15 2007

### 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:

```

19 Feb 04:45 2007

### 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
```

19 Feb 04:59 2007

### Re: speeding up fibonacci with memoizing

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

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
```

19 Feb 06:38 2007

### 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
```
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

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

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.

-- wli
```
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
```
19 Feb 09:32 2007

### 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)
```

20 Feb 17:54 2007

### 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
```

6 Nov 03:34 2007

### 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)
```
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)
>
>
>
> _______________________________________________
>
>
```
6 Nov 04:46 2007

### Re: Re: speeding up fibonacci with memoizing

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

:)

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)
> >
> >
> >
> >_______________________________________________
> >
> >
>
```

6 Nov 14:56 2007

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