Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Integer exponentiation in OCaml

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.

like image 971
user2258552 Avatar asked Jun 05 '13 22:06

user2258552


People also ask

Is there a power function in OCaml?

Regarding the floating-point part of your question: OCaml calls the underlying system's pow() function. Floating-point exponentiation is a difficult function to implement, but it only needs to be faithful (that is, accurate to one Unit in the Last Place) to make 2. ** 3. = 8.

What is int in OCaml?

int — Integers OCaml supports fixed-length integers two bits smaller than native machine integers — 30 bits on most machines (62 bits on some).

How are floats represented in OCaml?

To avoid such memory and runtime overhead, OCaml uses a special representation for arrays of floats. They are represented by blocks with a dedicated tag (254) that hold the unboxed floats.

How do you square root in OCaml?

The question asks for the square root , and there you are trying n^2 with n * n . To calculate the square root you can use the function sqrt available in OCaml Pervasives.


2 Answers

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.)

like image 167
gasche Avatar answered Oct 05 '22 07:10

gasche


Regarding the floating-point part of your question: OCaml calls the underlying system's pow() function. Floating-point exponentiation is a difficult function to implement, but it only needs to be faithful (that is, accurate to one Unit in the Last Place) to make 2. ** 3. = 8. evaluate to true, because 8.0 is the only float within one ULP of the mathematically correct result 8.

All math libraries should(*) be faithful, so you should not have to worry about this particular example. But not all of them actually are, so you are right to worry.


A better reason to worry would be, if you are using 63-bit integers or wider, that the arguments or the result of the exponentiation cannot be represented exactly as OCaml floats (actually IEEE 754 double-precision numbers that cannot represent 9_007_199_254_740_993 or 253 + 1). In this case, floating-point exponentiation is a bad substitute for integer exponentiation, not because of a weakness in a particular implementation, but because it is not designed to represent exactly integers that big.


(*) Another fun reference to read on this subject is “A Logarithm Too Clever by Half” by William Kahan.

like image 22
Pascal Cuoq Avatar answered Oct 05 '22 07:10

Pascal Cuoq