visual_fsharp (original) (raw)

1) Naive implementation:

F#, using GeSHi 1.0.8.6

  1. let rec fibnaive n =
  2. if n < 2 then 1I
  3. else
  4. fibnaive (n - 1) + fibnaive (n - 2)

Parsed in 0.008 seconds at 11.48 KB/s

Horrible performance. fibnaive 40 took 16.6 sec on my laptop

2) Matrix algorithm:

It’s handy that F# have matrix type in Microsoft.FSharp.Math namespace.

The type matrix uses float numbers. Let’s see how we could calculate Fibonacci’s:

F#, using GeSHi 1.0.8.6

  1. open Microsoft.FSharp.Math
  2. let matrixd = matrix [ [ 1.; 1. ];[ 1.; 0. ] ]
  3. let rec fibmatd n =
  4. if n < 2 then matrixd
  5. else matrixd * fibmatd(n - 1)
  6. let fib n =
  7. if n < 2 then 1I
  8. else
  9. let m = fibmatd n
  10. System.Numerics.BigInteger(m.[1, 0])

Parsed in 0.013 seconds at 21.61 KB/s

Result of fib 1000:

Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : System.Numerics.BigInteger =
4346655768693742750699615555111373698901493060675
3135940421893445574924103291704556590724031629457
1302242425620098031386057959852750558837247446456
7001785294423082188544814790061823421628580750638
3791353495552

It’s pretty fast but it has a problem: if I remember correctly Fibonacci of 1000, it calculates only first 15 digits right.

3) Generic matrix:

But this namespace has generic version of matrix type – we can use any arbitrary type to construct our matrix. We would use BigInteger to get a correct results.

F#, using GeSHi 1.0.8.6

  1. open Microsoft.FSharp.Math
  2. let anymatrix = Matrix.Generic.ofList
  3. let fibceed = anymatrix [ [ 1I; 1I ];[ 1I; 0I ] ]
  4. let rec fibmat n =
  5. if n < 2 then fibceed
  6. else fibceed * fibmat(n - 1)
  7. let fib n =
  8. if n < 2 then 1I
  9. else
  10. let m = fibmat n
    m.[0, 1]

Parsed in 0.012 seconds at 23.16 KB/s

Now the result of fib 1000:
Real: 00:00:00.006, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : System.Numerics.BigInteger =
4346655768693745643568852767504062580256466051737
1780402481729089536555417949051890403879840079255
1692959225930803226347752096896232398733224711616
4299644090653318793829896964992851600370447613779
5166849228875

It’s slightly slower but it calculates Fibonacci of 1000 correctly.

4) Another algorithm:

F#, using GeSHi 1.0.8.6

  1. let rec fibb (n1: bigint) (n2: bigint) c =
  2. if c = 1 then
  3. n2
  4. else
  5. fibb n2 (n1+n2) (c-1)
  6. let fibfast num =
  7. (fibb 1I 1I (num - 1))

Parsed in 0.009 seconds at 17.89 KB/s

It’s results are so far fastest I could get:

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val it : bigint =
4346655768693745643568852767504062580256466051737
1780402481729089536555417949051890403879840079255
1692959225930803226347752096896232398733224711616
4299644090653318793829896964992851600370447613779
5166849228875

And it’s tail recursive so we can play with it up to OutOfMemory exception for very very big integers. I’m always wanted to know what would be Fibonacci of 1000000. And now I can get it in slightly more than 2 min:

Real: 00:02:06.986, CPU: 00:02:10.229, GC gen0: 18414, gen1: 2523, gen2: 395
I don’t put it here because it consists of 208993 digits, but it starts with:

19532821287077577316320149475962563324435…

5) And finally using Seq type:

F#, using GeSHi 1.0.8.6

  1. let fibonacci =
  2. (fun (current, next) -> Some(current, (next, current + next)))
    (0I, 1I)
  3. let term n= fibonacci |> Seq.take n
  4. let fib 1000 = Seq.nth 1000 (term 1001)

Parsed in 0.012 seconds at 17.07 KB/s

It’s also pretty fast. Here are results of calculating 1000 Fibonacci numbers:
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

If anyone have another interesting algorithm to share – welcome to comments!