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:

How about the built-in

pown 2I 3

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.

Post a Comment