## 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"
else
1I
| _ when n=1I -> x
| _ when n=2I -> x*x
| _ ->
if n%2I = 0I then
let y = power(x, n/2I)
y*y
else
let y = power(x, (n-1I)/2I)
y*y*x

power(10I, 3I)

#### 2 comments:

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.