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