# Class IntElementaryModMath

java.lang.Object
org.apfloat.internal.IntElementaryModMath

Direct Known Subclasses:
  `IntModMath`

public class IntElementaryModMath extends Object
Elementary modulo arithmetic functions for `int` data.

Modular addition and subtraction are trivial, when the modulus is less than 231 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 obvious (but not very efficient) algorithm for multiplying two `int`s and taking the remainder is

`(int) ((long) a * b % modulus)`

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 modulus instead of dividing by the modulus.

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 32 bits of the full 64-bit result whenever possible, to save a few operations.

The basic approach is to get some approximation of `a * b / modulus`. The approximation should be within +1 or -1 of the correct result. Then calculate `a * b - approximateDivision * modulus` to get the remainder. This calculation needs to use only the lowest 32 bits. As the modulus is less than 231 it is easy to detect the case when the approximate division was off by one (and the remainder is `±modulus` off).

There are different algorithms to calculate the approximate division `a * b / modulus`. This implementation simply converts all the operands to `double` and performs the multiplications. This requires that converting between integer types and floating point types is efficient. On some platforms this may not be true; in that case it can be more efficient to perform the multiplications using 64-bit integer arithmetic.

To simplify the operations, we calculate the inverse modulus as `1.0 / (modulus + 0.5)`. Since the modulus is assumed to be prime, and a `double` has more bits for precision than an `int`, the approximate result of `a * b / modulus` will always be either correct or one too small (but never one too big).

Version:
  1.0.2
Author:
  Mikko Tommila

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `IntElementaryModMath()`
  Default constructor.

- ## Method Summary

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

  ### Methods inherited from class Object

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

- ## Constructor Details

  - ### IntElementaryModMath

    public IntElementaryModMath()
    Default constructor.

- ## Method Details

  - ### modMultiply

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

  - ### modAdd

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

  - ### modSubtract

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

  - ### getModulus

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

  - ### setModulus

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