3 people like it.

# Exponentiation by squaring

Function, what calculates x^n by non-recursive basic exponentiation squaring algorithm. This method uses the bits of the exponent to determine computing powers. Generic parameter x suitable for any type what supports multiplication. I do not suppose existence of inverse operator like "/", thus parameter n must be a positive integer only. It is not difficult to define an extended variant for a type what supports division.

 ``` 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: ``` ``````let inline fastPow x (n:int) = if n < 1 then failwith "Parameter n must be greater then 0" else new System.Collections.BitArray([|n|]) |> Seq.cast //cast bit array to bool array |> Seq.rev |> Seq.skipWhile (fun b -> not b) //skip leading false bits |> Seq.skip 1 //skip one true bit |> Seq.fold ( fun a b -> let sq = a*a if b then //if true bit printfn "square and mul (2 ops)" sq * x //squaring and then multiplying else //if false bit printfn "just square (1 op)" sq //only squaring ) x //test fastPow 3 11 fastPow 1.3 16 fastPow (new System.Numerics.Complex(1.1,1.02)) 17 fastPow 15I 16 //function narrowed to float type //let floatPow x n:float = if n = 0 then 1.0 elif n<0 then 1.0 / (fastPow x (-n)) else fastPow x n ``````
val fastPow : x:'a -> n:int -> 'a (requires member ( * ))

Full name: Script.fastPow
val x : 'a (requires member ( * ))
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 failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
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 b : 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 : 'a (requires member ( * ))
val sq : 'a (requires member ( * ))
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
namespace System.Numerics
Multiple items
type Complex =
struct
new : real:float * imaginary:float -> Complex
member Equals : obj:obj -> bool + 1 overload
member GetHashCode : unit -> int
member Imaginary : float
member Magnitude : float
member Phase : float
member Real : float
member ToString : unit -> string + 3 overloads
static val Zero : Complex
static val One : Complex
...
end

Full name: System.Numerics.Complex

--------------------
System.Numerics.Complex()
System.Numerics.Complex(real: float, imaginary: float) : unit