Arithmetic package

Package managers:

Jacques-Olivier Lachaud

Since

0.5

LICENSE: LGPL

Package Overview

This package gathers tools to perform arithmetic computations. Standard arithmetic computations are provided: greatest common divisor, Bézout vectors, continued fractions, convergent, intersection of integer half-spaces. Several representations of irreducible fractions are provided. They are based on the Stern-Brocot tree structure. With these fractions, amortized constant time operations are provided for computing reduced fractions. A representation of digital standard line in the first quadrant is provided, as well as fast algorithms to recognize digital straight subsegments. Furthermore, since 0.6, it provides classes for representing 2D lattice polytopes (convex integer polygons) as well as methods to perform linear integer programming in the plane.

Parts of this package are backports from ImaGene: class IntegerComputer, class SternBrocot (written with Xavier Provençal), algorithms StandardDSLQ0::smartDSS and StandardDSLQ0::reversedSmartDSS (written with Mouhammad Said), class ConvexIntegerPolygon (written with Emilie Charrier), class COBANaivePlaneComputer (written with Emilie Charrier and Lilian Buzer).

Modules

• Integer computations (Jacques-Olivier Lachaud)
• Irreducible fraction, continued fractions (Jacques-Olivier Lachaud, Xavier Provençal)
• Patterns, digital straight lines and subsegments (Jacques-Olivier Lachaud, Mouhammad Said)
• Lattice polytopes in the digital plane ZxZ (convex polygons with vertices at integer coordinates) (Jacques-Olivier Lachaud, Emilie Charrier)

Package Concepts Overview

• Arithmetic Concepts and Models

Related documentation pages

Related examples

• extended-euclid.cpp
• approximation.cpp, convergents.cpp, convergents-biginteger.cpp, fraction.cpp
• pattern.cpp
• lower-integer-convex-hull.cpp