# Class DoubleElementaryModMath

java.lang.Object
org.apfloat.internal.DoubleElementaryModMath

Direct Known Subclasses:
  `DoubleModMath`

public class DoubleElementaryModMath extends Object
Elementary modulo arithmetic functions for `double` data. Note that although a floating-point data type is used, the data will always be integers.

Modular addition and subtraction are trivial, when the modulus is less than 252 and overflow can be detected easily.

Modular multiplication is more complicated, and since it is usually the single most time consuming operation in the whole program execution, the very core of the Number Theoretic Transform (NTT), it should be carefully optimized.

The algorithm for multiplying two `double`s containing an integer and taking the remainder is not entirely obvious. The basic problem is to get the full 104-bit result of multiplying two 52-bit integers. This can basically be done in two parts: by multiplying two `long`s, the lowest 64 bits can be acquired easily. Multiplying the `double`s as floating-point numbers and scaling properly, the highest (roughly) 52 bits of the result can be acquired.

The first observation is that since the modulus is practically constant, it should be more efficient to calculate (once) the inverse of the modulus, and then subsequently multiply by the inverse of the modulus instead of dividing by it.

The second observation is that to get the remainder of the division, we don't necessarily need the actual result of the division (we just want the remainder). So, we should discard the topmost 52 bits of the full 104-bit result whenever possible, to save a few operations.

The basic approach is to get an approximation of `a * b / modulus` (using floating-point operands, that is `double`s). The approximation should be within +1 or -1 of the correct result. Then calculate `a * b - approximateDivision * modulus` to get the remainder. This calculation must use the lowest 52 (or more, actually 64) bits and is done using `long`s. As the modulus is less than 252 it is easy to detect the case when the approximate division was off by one (and the remainder is `±modulus` off).

To ensure that only one comparison is needed in the check for the approximate division, we use `1 / (modulus + 0.5)` as the inverse modulus. In this case the result of the approximate division is always either correct or 1 less.

Version:
  1.0
Author:
  Mikko Tommila

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `DoubleElementaryModMath()`
  Default constructor.

- ## Method Summary

  Modifier and Type
  Method
  Description
  `final double`
  `getModulus()`
  Get the modulus.
  `final double`
  `modAdd(double a, double b)`
  Modular addition.
  `final double`
  `modMultiply(double a, double b)`
  Modular multiplication.
  `final double`
  `modSubtract(double a, double b)`
  Modular subtraction.
  `final void`
  `setModulus(double modulus)`
  Set the modulus.

  ### Methods inherited from class Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- ## Constructor Details

  - ### DoubleElementaryModMath

    public DoubleElementaryModMath()
    Default constructor.

- ## Method Details

  - ### modMultiply

    public final double modMultiply(double a, double b)
    Modular multiplication.
    Parameters:
      `a` - First operand.
      `b` - Second operand.
    Returns:
      `a * b % modulus`

  - ### modAdd

    public final double modAdd(double a, double b)
    Modular addition.
    Parameters:
      `a` - First operand.
      `b` - Second operand.
    Returns:
      `(a + b) % modulus`

  - ### modSubtract

    public final double modSubtract(double a, double b)
    Modular subtraction. The result is always >= 0.
    Parameters:
      `a` - First operand.
      `b` - Second operand.
    Returns:
      `(a - b + modulus) % modulus`

  - ### getModulus

    public final double getModulus()
    Get the modulus.
    Returns:
      The modulus.

  - ### setModulus

    public final void setModulus(double modulus)
    Set the modulus.
    Parameters:
      `modulus` - The modulus.