0 people like it.

Fast Fibonacci numbers calculation

This snippet based on Binet's formula combined with fast power algorithm. Four multiplications run in parallel, thus processor with four cores recommended. Bitwise operators improve divisions and multiplications by pow of 2.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
type Fpair (a:bigint,b:bigint) =
  member this.a=a
  member this.b=b

  //Fpair multiplication
  static member (.*) (left:Fpair,right:Fpair) = 
      Fpair(left.a*right.a+5I*left.b*right.b, 
            left.b*right.a + left.a*right.b) 
  //square Fpair 
  static member (~+) (arg:Fpair) = 
    Fpair(arg.a*arg.a+5I*arg.b*arg.b, 
          2I*arg.a*arg.b) 
  //Fpair division
  static member (./) (left:bigint,right:Fpair) =
    Fpair(right.a/left,right.b/left)
  static member one = Fpair(1I,1I)

let fastFib (n:int) =
   let ans = new System.Collections.BitArray([|n|]) 
            |> Seq.cast<bool>
            |> Seq.rev
            |> Seq.skipWhile (fun x -> not x)
            |> Seq.skip 1
            |> Seq.fold (
                 fun a x -> if x then 
                              + a |> (.*) Fpair.one |> (./) 4I
                            else 
                              + a |> (./) 2I) 
                 Fpair.one
   ans.b 

let pFib n = 
   [async {return fastFib (n-2)}
    async {return fastFib (n-1)}]
     |> Async.Parallel 
     |> Async.RunSynchronously 
     |> Array.reduce (+)
Multiple items
type Fpair =
  new : a:bigint * b:bigint -> Fpair
  member a : bigint
  member b : bigint
  static member one : Fpair
  static member ( ./ ) : left:bigint * right:Fpair -> Fpair
  static member ( .* ) : left:Fpair * right:Fpair -> Fpair
  static member ( ~+ ) : arg:Fpair -> Fpair

Full name: Script.Fpair

--------------------
new : a:bigint * b:bigint -> Fpair
val a : bigint
type bigint = System.Numerics.BigInteger

Full name: Microsoft.FSharp.Core.bigint
val b : bigint
val this : Fpair
member Fpair.a : bigint

Full name: Script.Fpair.a
member Fpair.b : bigint

Full name: Script.Fpair.b
val left : Fpair
val right : Fpair
property Fpair.a: bigint
property Fpair.b: bigint
val arg : Fpair
val left : bigint
static member Fpair.one : Fpair

Full name: Script.Fpair.one
val fastFib : n:int -> bigint

Full name: Script.fastFib
val n : int
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val ans : Fpair
namespace System
namespace System.Collections
Multiple items
type BitArray =
  new : length:int -> BitArray + 5 overloads
  member And : value:BitArray -> BitArray
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit
  member Count : int
  member Get : index:int -> bool
  member GetEnumerator : unit -> IEnumerator
  member IsReadOnly : bool
  member IsSynchronized : bool
  member Item : int -> bool with get, set
  ...

Full name: System.Collections.BitArray

--------------------
System.Collections.BitArray(length: int) : unit
System.Collections.BitArray(bytes: byte []) : unit
System.Collections.BitArray(values: bool []) : unit
System.Collections.BitArray(values: int []) : unit
System.Collections.BitArray(bits: System.Collections.BitArray) : unit
System.Collections.BitArray(length: int, defaultValue: bool) : unit
module Seq

from Microsoft.FSharp.Collections
val cast : source:System.Collections.IEnumerable -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.cast
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
val rev : source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.rev
val skipWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skipWhile
val x : bool
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold
val a : Fpair
property Fpair.one: Fpair
val pFib : n:int -> bigint

Full name: Script.pFib
val async : AsyncBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.async
Multiple items
type Async
static member AsBeginEnd : computation:('Arg -> Async<'T>) -> ('Arg * AsyncCallback * obj -> IAsyncResult) * (IAsyncResult -> 'T) * (IAsyncResult -> unit)
static member AwaitEvent : event:IEvent<'Del,'T> * ?cancelAction:(unit -> unit) -> Async<'T> (requires delegate and 'Del :> Delegate)
static member AwaitIAsyncResult : iar:IAsyncResult * ?millisecondsTimeout:int -> Async<bool>
static member AwaitTask : task:Task -> Async<unit>
static member AwaitTask : task:Task<'T> -> Async<'T>
static member AwaitWaitHandle : waitHandle:WaitHandle * ?millisecondsTimeout:int -> Async<bool>
static member CancelDefaultToken : unit -> unit
static member Catch : computation:Async<'T> -> Async<Choice<'T,exn>>
static member FromBeginEnd : beginAction:(AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg:'Arg1 * beginAction:('Arg1 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * beginAction:('Arg1 * 'Arg2 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * arg3:'Arg3 * beginAction:('Arg1 * 'Arg2 * 'Arg3 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromContinuations : callback:(('T -> unit) * (exn -> unit) * (OperationCanceledException -> unit) -> unit) -> Async<'T>
static member Ignore : computation:Async<'T> -> Async<unit>
static member OnCancel : interruption:(unit -> unit) -> Async<IDisposable>
static member Parallel : computations:seq<Async<'T>> -> Async<'T []>
static member RunSynchronously : computation:Async<'T> * ?timeout:int * ?cancellationToken:CancellationToken -> 'T
static member Sleep : millisecondsDueTime:int -> Async<unit>
static member Start : computation:Async<unit> * ?cancellationToken:CancellationToken -> unit
static member StartAsTask : computation:Async<'T> * ?taskCreationOptions:TaskCreationOptions * ?cancellationToken:CancellationToken -> Task<'T>
static member StartChild : computation:Async<'T> * ?millisecondsTimeout:int -> Async<Async<'T>>
static member StartChildAsTask : computation:Async<'T> * ?taskCreationOptions:TaskCreationOptions -> Async<Task<'T>>
static member StartImmediate : computation:Async<unit> * ?cancellationToken:CancellationToken -> unit
static member StartWithContinuations : computation:Async<'T> * continuation:('T -> unit) * exceptionContinuation:(exn -> unit) * cancellationContinuation:(OperationCanceledException -> unit) * ?cancellationToken:CancellationToken -> unit
static member SwitchToContext : syncContext:SynchronizationContext -> Async<unit>
static member SwitchToNewThread : unit -> Async<unit>
static member SwitchToThreadPool : unit -> Async<unit>
static member TryCancelled : computation:Async<'T> * compensation:(OperationCanceledException -> unit) -> Async<'T>
static member CancellationToken : Async<CancellationToken>
static member DefaultCancellationToken : CancellationToken

Full name: Microsoft.FSharp.Control.Async

--------------------
type Async<'T>

Full name: Microsoft.FSharp.Control.Async<_>
static member Async.Parallel : computations:seq<Async<'T>> -> Async<'T []>
static member Async.RunSynchronously : computation:Async<'T> * ?timeout:int * ?cancellationToken:System.Threading.CancellationToken -> 'T
module Array

from Microsoft.FSharp.Collections
val reduce : reduction:('T -> 'T -> 'T) -> array:'T [] -> 'T

Full name: Microsoft.FSharp.Collections.Array.reduce
Next Version Raw view Test code New version

More information

Link:http://fssnip.net/7Xd
Posted:4 years ago
Author:Pavel Tatarintsev
Tags: fibonacci , fold , operator overloading , parallel , mapreduce , code reuse