3 people like it.
Like the snippet!

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