Skip to content

Boost numerical data type for real numbers representation

Notifications You must be signed in to change notification settings

BoostGSoC18/Real

Repository files navigation

Boost.Real

Boost.Real numerical data type for real numbers representation using range arithmetic.

Build Status codecov

Documentation

Introduction

The problem addressed by boost::real

Several times, when dealing with complex mathematical calculus, numerical errors can be carried from one operation to the next and after several steps, the error may significantly increase obtaining a non-trustworthy result. Normally, in these situations, the error is generated by the representation precision limit that truncates those numbers that do not fit in the representation precision generating errors without at least keeping track of the magnitude of the error. When this is the case, the real result is equal to the obtained approximated result plus the error (which is unknown).

Another major problem when dealing with real numbers is the representation of the irrational number as the number π or eπ, they are not handled by the native number data types causing limitations when calculations are based on those numbers. Normally we define a truncation of those numbers that are good enough for our purposes, but many times, the needed precision depends on the operation to do and to the composition of multiple operations, therefore, we are unable to determine which is the correct precision until we run the program.

The boost::real solution

Boost::real is a real number representation data type that address the mentioned issues using range arithmetic [1] and defining the precision as dynamical to be determined in run-time. The main goal of this data type is to represent a real number x as a program that returns a finite or infinite set of intervals containing the number x x(k) = [mk - ek, mk + ek], K ∈ N ≥ 0, ek ≥ 0. Where K1 < K2 ⇒ |x(k2)| < |x(k1)|. For this purposes, any Boost::real number has a precision const iterator that iterates the serie of intervals representing the number. The intervals within the serie are sorted from larger to smaller, thus, each time the iterator is increased, the number precision increases due the new calculated interval is smaller than the previous one until the interval is the number itself (if possible).

Also, to allow representing irrational numbers as π or eπ, boost::real has a constructor that takes as parameter a function pointer, functor (function object with the operator ()) or lambda expression that for any integer n > 0, the function returns the n-th digit of the represented number. For example, the number 1/3 can easily be represented by a program that for any input n > 0, the function returns 3.

The boost::real numbers representation

In boost::real, a number has one of the next three representations:

  1. Explicit number: A number is a vector of digits sorted as in the number natural representation. To determine where the integer part ends and the fractional part starts, an integer is used as the exponent of a floating point number and determines where the integer part start and the fractional ends. Also a boolean is used to set the number as positive (True) or negative (False)
  2. Algorithmic number: This representation is equal to the Explicit number but instead of using a vector of digits, a lambda function must be provided. The lambda function takes an unsigned integer "n" as parameter and returns the n-th digit of the number.
  3. A number is a composition of two numbers related by an operator (+, -, *), the number creates pointers to the operands and each time the number is used, the operation is evaluated to return the result.

Because of the third representation type, a number resulting from a complex calculus is a binary tree where each internal vertex is an operation and the vertex children are its operands. The tree leaves are those numbers represented by either (1) or (2) while the internal vertex are those numbers represented by (3). More information about the used number representation can be found in [3]

The boost::real precision iterator.

The boost::real::const_precision_iterator is a forward iterator [4] that iterates through the number interval precisions. The iterator returns two numbers, a lower and an upper boundary that represent the [mk - ek, mk + ek] limits of the number approximation interval for a given precision. Each time the iterator is incremented, the interval approximation_interval is decreased and a new interval with a better precision is obtained. Normally, there is no need to interact with the precision iterator and it is used by the boost::real operators <<, < and >.

Interface

Constructors and destructors

1. boost::real(const std::string& number)
2. boost::real(const initializer_vector<int> digits)
3. boost::real(const initializer_vector<int> digits, bool positive)
4. boost::real(const initializer_vector<int> digits, int exponent)
5. boost::real(const initializer_vector<int> digits, int exponent, bool positive)
6. boost::real((unsigned int) -> int digits, int exponent)
7. boost::real((unsigned int) -> int digits, int exponent, bool positive)
8. boost::real(const boost::real& x)
9. boost::~real()

(1) String constructor Creates a real instance by parsing the string. The string must have a valid number, in other case, the constructor will throw an boost::real::invalid_string_number_exception exception.

(2) Initializer list constructor Creates a real instance that represents an integer number where all the digits numbers are form the integer part in the same order.

(3) Signed initializer list constructor Creates a real instance that represents the number where the positive parameter is used to set the number sign and the elements of the digits parameter list are the number digits in the same order.

(4) Initializer list constructor with exponent Creates a real instance that represents the number where the exponent is used to set the number integer part and the elements of the digits list are the digits the number in the same order.

(5) Initializer list constructor with exponent and sign Creates a real instance that represents the number where the exponent is used to set the number integer part and the elements of the digits list are the digits the number in the same order. This constructor uses the sign to determine if the number is positive or negative.

(6) Lambda function constructor with exponent Creates a real instance that represents the number where the exponent is used to set the number integer part and the lambda function digits is used to know the number digit, this function returns the n-th number digit.

(7) Lambda function constructor with exponent and sign Creates a real instance that represents the number where the exponent is used to set the number integer part and the lambda function digits is used to know the number digit, this function returns the n-th number digit. This constructor uses the sign to determine if the number is positive or negative.

(8) Copy constructor Creates a copy of the number x, if the number is an operation, then, the constructor creates new copies of the x operands.

(9) Default destructor If the number is an operator, the destructor destroys its operands.

Operators

1. boost::real operator+=(const boost::real& x)
2. boost::real operator-=(const boost::real& x)
3. boost::real operator*=(const boost::real& x)
4. boost::real operator+(const boost::real& x) const
5. boost::real operator-(const boost::real& x) const
6. boost::real operator*(const boost::real& x) const
7. boost::real& operator=(const boost::real& x)
8. boost::real& operator=(const std::string& x)
9. boost::real& operator==(const boost::real& x)
10. bool operator<(const real& other) const
11. std::ostream& operator<<(std::ostream& os, const boost::real& x)
12. int operator[](unsigned int n) const

(1) Modifies the number to use the third representation. and sets copies of *this and x respectively as the left and right operands and sets addition as the operation.

(2) Modifies the number to use the third representation. and sets copies of *this and x respectively as the left and right operands and sets subtraction as the operation.

(3) Modifies the number to use the third representation. and sets copies of *this and x respectively as the left and right operands and sets multiplication as the operation.

(4) Creates a new boost::real number using the third representation. For this purpose, the operator creates copies of *this and x to use as the new real number operands and defines the addition as the operation.

(5) Creates a new boost::real number using the third representation. For this purpose, the operator creates copies of *this and x to use as the new real number operands and defines the subtraction as the operation.

(6) Creates a new boost::real number using the third representation. For this purpose, the operator creates copies of *this and x to use as the new real number operands and defines the multiplication as the operation.

(7) Uses the copy constructor to create a copy of x stored in *this

(8) Uses the string constructor to create a real that represents the number specified in the x string.

(9) compares *this with x to check if they represent the same number. WARNING: Because different numbers can have an arbitrary number of equal intervals, numbers equality can be checked only for those numbers that can be fully represented with the maximum_precision or their approximation intervals stop overlapping before the maximum_precision is reached. In other case, it will throw a boost::real::precision_exception.

(10) Compares *this with x to check if *this is lower than x. This operator creates two precision iterators (one for each number) and iterates until the number intervals stop overlapping when that happens, it compares the intervals boundaries to determine if *this is less than x. WARNING: If *this is equal to x, then the intervals will always overlap, because of this, and if the numbers intervals still overlap once the maximum_precision is reached, the operator throws a boost::real::precision_exception.

(11) Creates a const_precision_iterator to print the number using the iterator << operator.

(12) Returns the n-th digit of the represented number. WARNING: This operator throws invalid_representation_exception for the third representation because only explicit and algorithmic numbers can be asked for the n-th digit.

Other methods

1. boost::real::const_precision_iterator boost::real::cbegin()
2. boost::real::const_precision_iterator boost::real::cend()
3. unsigned int boost::real::maximum_precision()
4. void boost::real::set_maximum_precision(unsigned int)

(1) Construct a new const_precision_iterator that iterate over the *this number precisions. The constructed iterator points to the first approximation interval (the ine with less precision).

(2) Construct a new const_precision_iterator that iterate over the *this number precisions. The constructed iterator points to the last approximation interval (the one with more precision) within the maximum precision.

(3) Returns the instance maximum precision at which the operators will throw a boost::real::precision_exception if they cannot determine the operation value before reaching the maximum precision.

(4) Sets a new maximum precision. If the set maximum precision is zero, the static default maximum precision will be used instead.

boost::real::const_precision_iterator interface

Constructors

1. boost::real::const_precision_iterator()
2. boost::real::const_precision_iterator(real const* x)
3. boost::real::const_precision_iterator(const boost::real::const_precision_iterator& x)

(1) ** Default constructor ** Create an empty iterator that does not point any number and thus, cannot yet be iterated.

(2) Creates an iterator that points to the x number and iterates the number precision. If the number is deleted, the iterator behaviour is undefined.

(3) ** Copy constructor ** Creates an iterator that points the same number than the x iterator does and is initialized in the same precision that x.

Operators

1. void operator++()
2. bool operator==(const boost::real::real::const_precision_iterator& other)
3. bool operator!=(const boost::real::real::const_precision_iterator& other)

(1) Increases the pointer to the next precision interval of the pointed number. If the pointed number is represented by a real_explicit number and the full number precision is reached, then the operator has no effect because the number approximation lower and upper boundaries are equals and the number interval is the number itself.

(2) It compare by value equality; two boost::real::real::const_precision_iterators are equals if they are pointing to the same real number and are in the same precision iteration.

(3) It compare by value not equal; two boost::real::real::const_precision_iterators.

Examples

#include <iostream>
#include <string>
#include <real/real.hpp>

unsigned int boost::real::real::maximum_precision = 10;
unsigned int boost::real::real_algorithm::maximum_precision = 10;

int main() {
    boost::real::real c = (std::string)"0.999999";
    boost::real::real d = (std::string)"0.999999";
    boost::real::real e = c + d;

    std::cout << "c: " << c << std::endl;
    std::cout << "d: " << d << std::endl;

    boost::real::real::const_precision_iterator it = e.cbegin();
    for(auto it = e.cbegin(); it != e.cend(); ++it) {
        std::cout << "e iteration " << it.approximation_interval << std::endl;
    }

    boost::real::real g = (std::string)"0.999998";

    if (g < d) {
        std::cout << "g < d --> true" << std::endl;
    } else {
        std::cout << "g < d --> false" << std::endl;
    }

    boost::real::real h = d - g;

    std::cout << "d: " << d << std::endl;
    std::cout << "g: " << g << std::endl;
    std::cout << "h: " << h << std::endl;

    return 0;
}

Output

c: 0.999999
d: 0.999999
e iteration [1.8, 2]
e iteration [1.98, 2]
e iteration [1.998, 2]
e iteration [1.9998, 2]
e iteration [1.99998, 2]
g < d --> true
d: 0.999999
g: 0.999998
h: 0.000001

Current limitations

  1. The number digits are of type int between 0 and 9, number representation must be correctly handled in a higher base to improve memory and time performances.
  2. The division algorithm is under implementation but is not currently available.

References

1. Computable calculus / Oliver Aberth, San Diego : Academic Press, c2001
2. Lambov, B. (2007). RealLib: An efficient implementation of exact real arithmetic. Mathematical Structures in Computer Science, 17(1), 81-98.
3. Aberth, O., & Schaefer, M. J. (1992). Precise computation using approximation_interval arithmetic, via C++. ACM Transactions on Mathematical Software (TOMS), 18(4), 481-491.
4. https://en.cppreference.com/w/cpp/concept/ForwardIterator