Integer exponentiation in OCaml

Question

Is there a function for integer exponentiation in OCaml? ** is only for floats. Although it seems to be mostly accurate, isn't there a possibility of precision errors, something like 2. ** 3. = 8. returning false sometimes? Is there a library function for integer exponentiation? I could write my own, but efficiency concerns come into that, and also I'd be surprised if there isn't such a function already.

Answer 1

Not in the standard library. But you can easily write one yourself (using exponentiation by squaring to be fast), or reuse an extended library that provides this. In Batteries, it is Int.pow.

Below is a proposed implementation:

let rec pow a = function
  | 0 -> 1
  | 1 -> a
  | n -> 
    let b = pow a (n / 2) in
    b * b * (if n mod 2 = 0 then 1 else a)

If there is a risk of overflow because you're manipulating very big numbers, you should probably use a big-integer library such as Zarith, which provides all sorts of exponentiation functions.

(You may need the "modular exponentiation", computing (a^n) mod p; this can be done in a way that avoids overflows by applying the mod in the intermediary computations, for example in the function pow above.)