DGtal  0.9.3beta
Integer computations

Table of Contents

Author(s) of this documentation:
Jacques-Olivier Lachaud

Part of the Arithmetic package.

This module gathers several functions to make computations with integers (either basic types or big integer representations). The main part of the module is the class IntegerComputer, which holds methods but also data to perform computations efficiently.

Integer types and standard arithmetic operations

We use integer types DGtal::int32_t, DGtal::int64_t, and DGtal::BigInteger (integers of arbitrary size). The last type is available only if DGtal was compiled with cmake -DWITH_GMP=true ...

You may use any of these types or new ones, provided they satisfy the concepts CInteger, as well as its semantic. See also Number and Integer Concepts.

These types provide the standard arithmetic operators +, -, *, /, %, arithmetic comparisons <, <=, >=, >, ==, !=, assignements =, +=, *=, -=, /=, %=.

More elaborate computations with integers

The templated class IntegerComputer is parameterized by a type that is a model of CInteger. Most – but not all – of the methods of this class require the class to be instantiated. Indeed, it allows the instantiation of mutable integer data members, which are then used in all intermediate computations. This is especially useful with GMP big integers, where memory management takes a lot of time. The idea is thus to allocate once and for all these variables.

We list below the main methods:

// computes the vector X solution to a X_0 + b X_1 = c.
// when c is a multiple of gcd( a, b ).
typedef IntegerComputer<int32_t> IC;
IC ic;
IC::Vector2I X = ic.extendedEuclid( a, b, c );
bool ok = a * X[ 0 ] + b * X[ 1 ] == c; // should be true.