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: 38: 39: 40: 41: 42: ``` ``````//Binet's formula F(n) = ( (1 + sqrt(5))^n/2^n) - (1 - sqrt(5))^n/2^n))/sqrt(5) //(a+b sqrt(5)) <=> (a,b) type Fpair (a:bigint,b:bigint) = member this.a=a member this.b=b //Fpair multiplication static member (.*) (left:Fpair,right:Fpair) = let tasks = [| async {let bb = left.b*right.b return bb + (bb <<< 2)} async {return left.a*right.a} async {return left.b*right.a} async {return left.a*right.b}|] let res = tasks |> Async.Parallel |> Async.RunSynchronously Fpair(res.[0] + res.[1], res.[2] + res.[3]) //square Fpair (a + b sqrt(5))^2 = a^2 + 5b^2 + 2(ab)sqrt(5) static member (~+) (arg:Fpair) = let tasks =[|async {let bb = arg.b*arg.b return bb + (bb <<< 2)} //5b^2 async {return arg.a*arg.a} //a^2 async {return arg.a*arg.b <<< 1}|] //2ab let res = tasks |> Async.Parallel |> Async.RunSynchronously Fpair(res.[0]+res.[1],res.[2]) //Fpair division by pow of 2 static member (./) (left:int,right:Fpair) = Fpair(right.a >>> left,right.b >>> left) //First Fpair 1 + sqrt(5) static member one = Fpair(1I,1I) let fastFib (n:int) = let ans = new System.Collections.BitArray([|n|]) |> Seq.cast |> Seq.rev |> Seq.skipWhile (fun x -> not x) |> Seq.skip 1 |> Seq.fold ( fun a x -> if x then + a |> (.*) Fpair.one |> (./) 2 else + a |> (./) 1) Fpair.one ans.b ``````
Multiple items
type Fpair =
new : a:bigint * b:bigint -> Fpair
member a : bigint
member b : bigint
static member one : Fpair
static member ( ./ ) : left:int * 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
val async : AsyncBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.async
val bb : System.Numerics.BigInteger
property Fpair.b: bigint
property Fpair.a: bigint
val res : System.Numerics.BigInteger []
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 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 StartChild : computation:Async<'T> * ?millisecondsTimeout:int -> Async<Async<'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
val arg : Fpair
val left : 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<_>
static member Fpair.one : Fpair

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

Full name: Script.fastFib
val n : 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 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