Arithmetics

This documentation page deals with the internal arithmetic functions in the hypertiling package. Since those functions are at the core of the package, some of them are heavily optimized, using e.g. numba just-in-time compilation and furthermore particularly designed to be numerically stable, given the coordinate singularities and largely varying coordinate dimensions that come with the Poincare disk representation of hyperbolic geometry. Some of the transformations are available in double-double precision.

Kahan summation

Kahan summation algorithm, also known as compensated summation, is a method to improve the numerical accuracy of the total sum of a sequence of finite precision floating point numbers. The algorithm significantly reduces the numerical error in the total obtained by adding a sequence of numbers compared to the simple approach of adding them in sequence. This is particularly important in cases where the sum involves a large number of terms or when the numbers vary greatly in magnitude.

hypertiling.arithmetics.kahan(x, y)

Transform the addition of two floating point numbers:

\[x + y = r + e\]

(Dekker1971) showed that this transform is exact, if abs(x) > abs(y).

Parameters:

x (float): a floating point number. y (float): a floating point number with abs(y) < abs(x).

Returns:

r (float): x + y e (float): the overflow

Branch-free transformations

Branch-free summation and differences, as described, e.g., by Donald Knuth, is an approach used in computer programming and numerical analysis to perform addition operations without causing conditional branches. Conditional branches can be expensive in terms of CPU cycles, especially on modern processors with deep pipelines and speculative execution. Branch mispredictions can lead to significant performance penalties, so eliminating branches, when possible, can lead to more efficient code execution.

hypertiling.arithmetics.twosum(x, y)

Perform a branch-free transformation of addition according to Knuth’s method.

This function computes the sum of x and y in a branch-free manner, which can be beneficial for performance on certain hardware architectures. The method follows the approach proposed by Donald Knuth.

Parameters:

  • x (float or float[:]) – The first addend in the addition operation.

  • y (float or float[:]) – The second addend in the addition operation.

Returns:

  • r (float or float[:]) – The sum of x and y.

  • e (float or float[:]) – The error term of the addition.

hypertiling.arithmetics.twodiff(x, y)

Perform a branch-free transformation of subtraction.

This function computes the difference (x - y) in a way that does not involve conditional branches, which can be beneficial for performance on certain hardware architectures.

Parameters:

  • x (float or float[:]) – The minuend of the subtraction operation.

  • y (float or float[:]) – The subtrahend of the subtraction operation.

Returns:

  • r (float or float[:]) – The result of the subtraction (x - y).

  • e (float or float[:]) – The error term of the subtraction.

Double-double precision

Double-double precision is a technique used in computing to achieve higher precision than what is provided by a standard double-precision floating-point format. While a standard double-precision floating-point number uses 64 bits to represent a number, double-double precision effectively uses two 64-bit double-precision numbers to represent a single number with greater precision. This technique allows for a significant increase in the number of significant digits that can be accurately represented.

hypertiling.arithmetics.htadd(x, dx, y, dy)

Perform addition of numbers (x,dx) and (y,dy) given in double double representation.

Parameters:

x (float): a floating point number. dx (float): overflow of x y (float): a floating point number. dy (float): overflow of y

Returns:

r (float): x + y + (dx + dy) e (float): the overflow

hypertiling.arithmetics.htdiff(x, dx, y, dy)

Perform subtraction of numbers given in double double representation.

Parameters:

  • x (float or float[:]) – A floating point number or array.

  • dx (float or float[:]) – Overflow of x.

  • y (float or float[:]) – A floating point number or array.

  • dy (float or float[:]) – Overflow of y.

Returns:

  • r (float or float[:]) – The result of the subtraction (x - y).

  • e (float or float[:]) – The error term of the subtraction.

hypertiling.arithmetics.htprod(x, dx, y, dy)

Performs multiplication of two numbers represented in double-double format.

Parameters:

  • x (float or float[:]) – A number or an array of numbers.

  • dx (float or float[:]) – The error term of x.

  • y (float or float[:]) – Another number or array of numbers.

  • dy (float or float[:]) – The error term of y.

Returns:

  • r (float or float[:]) – The product of x and y.

  • e (float or float[:]) – The error term of the result.

hypertiling.arithmetics.htcplxprod(a, da, b, db)

Performs multiplication of complex double double numbers using the Gauss/Karatsuba trick.

Parameters:

  • a (complex128) – A complex number.

  • da (complex128) – Overflow of a.

  • b (complex128) – Another complex number.

  • db (complex128) – Overflow of b.

Returns:

  • result (complex128) – The result of the complex multiplication.

  • overflow (complex128) – The overflow of the result.

Notes

This function employs the Gauss/Karatsuba trick for multiplication:

\[(ar + I * ai)*(br + I*bi) = ar*br - ai*bi + I*[ (ar + ai)*(br + bi) - ar*br - ai*bi ]\]
hypertiling.arithmetics.htcplxprodconjb(a, da, b, db)

Perform multiplication of complex double double numbers where b is conjugated.

\[(a, da) * (b, db)^* = (r, dr)\]
Parameters:
afloat

a floating point number.

dafloat

overflow of a

bfloat

a floating point number.

dbfloat

overflow of b

Returns:

r : float

drfloat

the overflow

This function employs the Gauss/Karatsuba trick for multiplication:

\[(ar + I * ai)*(br + I*bi) = ar*br - ai*bi + I*[ (ar + ai)*(br + bi) - ar*br - ai*bi ]\]
hypertiling.arithmetics.htcplxadd(a, da, b, db)

Perform addition of complex double-double numbers.

Parameters:

  • a (complex128) – Complex double-double numbers to add.

  • da (complex128) – Complex double-double numbers to add.

  • b (complex128) – Complex double-double numbers to add.

  • db (complex128) – Complex double-double numbers to add.

Returns:

A tuple of the sum and its overflow.

Return type:

complex128

hypertiling.arithmetics.htcplxdiff(a, da, b, db)

Perform subtraction of complex double-double numbers.

Parameters:

  • a (complex128) – Complex double-double numbers to subtract.

  • da (complex128) – Complex double-double numbers to subtract.

  • b (complex128) – Complex double-double numbers to subtract.

  • db (complex128) – Complex double-double numbers to subtract.

Returns:

A tuple of the difference and its overflow.

Return type:

complex128

hypertiling.arithmetics.htcplxdiv(a, da, b, db)

Perform division of complex double-double numbers.

Parameters:

  • a (complex128) – The dividend complex double-double number.

  • da (complex128) – The dividend complex double-double number.

  • b (complex128) – The divisor complex double-double number.

  • db (complex128) – The divisor complex double-double number.

Returns:

A tuple of the quotient and its overflow.

Return type:

complex128