Creating a Fast Exponent Function

Question

I'm having trouble finding a quicker version of the typical exponent function in OCaml. Here are some guidelines that I'm trying to follow:

1. Rather than the typical recursive exponent version of expt b n ==> b * (b * (b ...) this function receives two arguments b and n and basically takes a divide and conquer stance.
2. If n is even, then fastexpt b n => (b ^ (n / 2))^2 else if n is odd then fastexpt b n => b * (b ^ (n - 1))

Here's the code that I have written so far:

let fastexpt : int -> int -> int
= fun b n ->
    if n = 0 then 1
    else if ((n mod 2) = 0) then (expt b (n / 2)) * (expt b (n / 2)) 
    else b * (expt b (n - 1));;

My question is: Is there a way to write this function without using the expt function?

Answer 1

What you're doing here is using the divide and conquer method the first time and then using the normal one for the rest of the computation (if we consider that you already declared expt)

Another thing is that if n is odd, you can return b * b^((n-1)/2) * b^((n-1)/2), that's the purpose of the fast exponentiation.

What you should do is just defining fastexpt as recursive and use it all the way :

let rec fastexpt : int -> int -> int
= fun b n ->
    if n = 0 then 1
    else 
      let b2 = fastexpt b (n / 2) in
      if n mod 2 = 0 then b2 * b2 
      else b * b2 * b2;;