org.apfloat.internal
Class IntElementaryModMath

java.lang.Object
  |
  +--org.apfloat.internal.IntElementaryModMath
Direct Known Subclasses:
IntModMath

public class IntElementaryModMath
extends java.lang.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 ints 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. One would be to convert all the operands to double. But, on most platforms converting between integer types and floating point types is not very efficient. Another option is to use fixed-point multiplication using long operands. This is the approach used in this implementation.

As the modulus is slightly less than 231, we can divide 263 by the modulus, to get a fixed-point approximation of the inverse modulus (rounded towards zero) to a precision of 33 bits. The result of a * b takes 62 bits; shifting that right by 30 bits and multiplying by the fixed-point inverse modulus will always fit to 64 bits (because a and b are less than the modulus and the inverse modulus was rounded towards zero). This result can be further right-shifted by 33 to get the approximate result of a * b / modulus.


Constructor Summary
IntElementaryModMath()
          Default constructor.
 
Method Summary
 int getModulus()
          Get the modulus.
 int modAdd(int a, int b)
          Modular addition.
 int modMultiply(int a, int b)
          Modular multiplication.
 int modSubtract(int a, int b)
          Modular subtraction.
 void setModulus(int modulus)
          Set the modulus.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

IntElementaryModMath

public IntElementaryModMath()
Default constructor.

Method Detail

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.