# Class FloatElementaryModMath

java.lang.Object
org.apfloat.internal.FloatElementaryModMath

Direct Known Subclasses:
  `FloatModMath`

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

Since the moduli are close to 224 some attention must be paid to avoiding overflow in modular addition and subtraction. This can be done easily e.g. by casting the operands to `double`. Note that an IEEE float has a mantissa with a precision of 24 bits (1 + 23).

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.

Some obvious (but not very efficient) algorithms for multiplying two `float`s and taking the remainder would be to call `Math.IEEEremainder()`, or cast the operands to `long`, e.g.

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

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 algorithm used in this implementation casts the operands to `double`, performs the multiplication, multiplies by the inverse modulus, then takes the integer part. Getting the integer part is typically a lot faster by casting to `int` compared to e.g. calling `Math.floor()`. An `int`, holding 32 bits, can easily contain the result of the cast, which will have a maximum of 24 bits.

Overflow is not a problem, since a `double` can hold 53 bits precisely in the mantissa – more than doubly what a `float` can. Note that multiplying by the inverse modulus is also trivial, when the inverse modulus has more than twice accurate bits than what are in each of the multiplicands. Since the modulus is assumed to be prime, there can be no situations where multiplication by the inverse modulus would have a near-integer result that would be rounded incorrectly, e.g. as in `0.333... * 3 = 0.999...`.

Version:
  1.15.0
Author:
  Mikko Tommila

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `FloatElementaryModMath()`
  Default constructor.

- ## Method Summary

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

  ### Methods inherited from class Object

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

- ## Constructor Details

  - ### FloatElementaryModMath

    public FloatElementaryModMath()
    Default constructor.

- ## Method Details

  - ### modMultiply

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

  - ### modAdd

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

  - ### modSubtract

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

  - ### getModulus

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

  - ### setModulus

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