Fast Fibonacci numbers calculation

 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<bool>
            |> 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 tasks : Async<System.Numerics.BigInteger> []

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

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