File BinaryInteger.h

↰ Parent directory (ADS/numeric)

The arithmetic on integers of n bits, vectors of bits from the least significant one, of section 2.6:

Definition (ADS/numeric/BinaryInteger.h)

Detailed Description

  • binaryAdd(), the sum with the propagation of the carry, :math:` Theta( n ) `, optimal since every bit must be read;

  • multiplyBinarySchool(), the product of the school, a partial product per bit, :math:` Theta( n^2 ) `;

  • multiplyBinaryFour() and multiplyBinaryKaratsuba(), X = a 2^{n/2} + b and Y = c 2^{n/2} + d, with four products or with the three of Karatsuba, :math:` Theta( n^2 ) ` and :math:` Theta( n^{log_2 3} ) : the products of the polynomials of the bits [see :ref:`file_ADS_numeric_Polynomial.h] followed by the carries;

  • ahmes(), the multiplication of the papyrus of Ahmes (1650 b.C.), which adds b to p when a is odd, halves a and doubles b, until a = 0: from :math:` a b = ( a / 2 ) ( 2 b ) ` for a even and :math:` a b = ( ( a - 1 ) / 2 ) ( 2 b ) + b ` for a odd, O( log a ) steps, the shift and add of the arithmetic units.

The contracts [see File Contract.h]: a vector of bits holds only 0 and 1, an audit on the inputs of the sums and of the products, and fromBits() needs at most 64 of them; toBits() gives at least n bits whose value is x, and ahmes() gives the product modulo 2^64. The functions are defined in BinaryInteger.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 1.4 and 2.6, https://algoritmicamente.it/materiali/libro/capitoli/cap02.pdf

  1. Karatsuba, Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady 7, 595-596, 1963

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs