Wednesday, October 24, 2012

F# on Algorithm - Exponential Computation

find the power(2,3) = 8 seems not that difficult. The possible solution is to multiple 2 three times. The complex is O(n), where n is the second parameter. Is there a better way to do it? Yes, the code below (O(lg n)) is a sample.  The "I" suffix is to indicate the number is a F# bigint type.

This sample is more to demonstrate how the algorithm, rather than being used for real world application. F# has built-in application pown (3I, 2), which should be applied whenever is possible.

let rec power(x,n) =
    match n with
    | _ when n=0I ->
        if x=0I then
            failwith "invalid operation"
    | _ when n=1I -> x
    | _ when n=2I -> x*x
    | _ ->
        if n%2I = 0I then
            let y = power(x, n/2I)
            let y = power(x, (n-1I)/2I)
power(10I, 3I)


Don said...

How about the built-in

pown 2I 3

Tao said...

Good point, this is an algorithm more demonstrate how the underlying exponential algorithm works. The pown 2I 3 should be good enough for real world application.