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<bool>                     //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 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 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
Raw view Test code New version

More information

Link:http://fssnip.net/7Xz
Posted:4 years ago
Author:Pavel Tatarintsev
Tags: fold , generic functions , sequence