Integer exponent in OCaml

Question

Is there a function for integer exponentiation in OCaml? ** - only for floats. Although this is apparently mostly accurate, there is no possibility of precision errors, something like 2. ** 3. = 8. Sometimes a lie comes back? Is there a library function for integer exponentiation? I could write my own, but there are problems with efficiency, and I would be surprised if such a function no longer exists.

Answer 1

Regarding the floating point part of your question: OCaml calls the pow() base system. Floating-point intensity is a complex function to implement, but it must be true (i.e., accurate to unity in the last place ) to make 2. ** 3. = 8. evaluate true because 8.0 is the only float inside one ULP mathematically correct result 8.

All math libraries should (*) be correct, so you don’t have to worry about this particular example. But not all of them are actually there , so you can worry.

---

The best cause for concern would be if you use 63-bit integers or wider, then the arguments or the result of exponentiation cannot be represented exactly like OCaml float (in fact IEEE 754 double-precision numbers that cannot represent 9_007_199_254_740_993 or 2 ⁵³ + 1). In this case, floating-point exponentiation is a poor substitute for integer exponentiation, not because of weakness in a particular implementation, but because it is not intended to represent exactly integer large ones.

---

(*) Another interesting reading link on this topic: " The logarithm is too smart in half " by William Kahan.

Answer 2

Not in the standard library. But you can easily write one (using exponentiation, squaring to be fast), or reuse the extended library that provides this. At Batteries, it's Int.pow .

Below is a suggested 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 are manipulating very large numbers, you should probably use a library with a large integer such as Zarith , which provides all kinds of exponential functions.

(You might need a “modular exponentiation”, a computation of (a^n) mod p , which can be done in such a way as to avoid overflow by applying the mod in intermediate calculations, for example, in the pow function above.)

Answer 3

Here's another implementation that uses squared exponentiation (e.g. the one provided by @gasche), but this one is tail recursive

 let is_even n = n mod 2 = 0 (* https://en.wikipedia.org/wiki/Exponentiation_by_squaring *) let pow base exponent = if exponent < 0 then invalid_arg "exponent can not be negative" else let rec aux accumulator base = function | 0 -> accumulator | 1 -> base * accumulator | e when is_even e -> aux accumulator (base * base) (e / 2) | e -> aux (base * accumulator) (base * base) ((e - 1) / 2) in aux 1 base exponent