Surreal

Surreal library is an exact real arithmetic library for objective caml.

Feature

Exact real arithmetic often requires frequent re-calculation of the same real number in different accuracy. Using some heuristics, Surreal computes higher accuracy than necessary in each calculation and caches the result, in order to avoid re-calculation. This strategy may achieve better performance for large scale computation. For a very simple example, Surreal can evaluate a formula involving 2000-3000 operands within a minute.

The library is currently just a rough sketch, and not well tested. There is no plan to further development. I am tired of error bound estimation. However, if someone is interested, I would love to share ideas.

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

Download

Download

Installation

No installation procedure is provided. To compile the library, just do make in the top of the source directory. You need Michel Quercia's Numerix (0.18 or above) for compilation.

Usage

See README.

Algorithm

Evaluation strategy is the following. We assume that approximation with accuracy 2^(-d) is required.

The case the real does not depend on the value of the other real. For example, constants as pi fall into this case. Let 2^k0 < d <= 2^k1. We compute approximation of the real with accuracy 2^(2^k1).

The case the real depend on the value of the other real. For example, exp(pi) is fall into the case. First, we evaluate pi in the least required accuracy. In this case, accuracy 2^-(d + 2) is required for pi. Then we obtain approximation of pi with accuracy 2^(-d1), where d1 is determined as the above. Now, we evaluate exp(pi) in the highest accuracy which can be obtained from the approximation of pi with accuracy 2^(-d1). In this case 2^(-d1 + 2).

For computation of exp and triangular functions, Surreal uses an algorithm with O(d^1/3)-multiplication. See mp.ml

Contact to the author.

See the author's homepage.