public class DoubleElementaryModMath extends Object
double
data.
Note that although a floatingpoint data type is used, the data
will always be integers.Modular addition and subtraction are trivial, when the modulus is less than 2^{52} 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 104bit result of multiplying two 52bit 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 floatingpoint 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 104bit result whenever possible, to save a few operations.
The basic approach is to get an approximation of a * b / modulus
(using floatingpoint 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 2^{52}
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.
Constructor and Description 

DoubleElementaryModMath()
Default constructor.

Modifier and Type  Method and Description 

double 
getModulus()
Get the modulus.

double 
modAdd(double a,
double b)
Modular addition.

double 
modMultiply(double a,
double b)
Modular multiplication.

double 
modSubtract(double a,
double b)
Modular subtraction.

void 
setModulus(double modulus)
Set the modulus.

public final double modMultiply(double a, double b)
a
 First operand.b
 Second operand.a * b % modulus
public final double modAdd(double a, double b)
a
 First operand.b
 Second operand.(a + b) % modulus
public final double modSubtract(double a, double b)
a
 First operand.b
 Second operand.(a  b + modulus) % modulus
public final double getModulus()
public final void setModulus(double modulus)
modulus
 The modulus.Copyright © 2017. All rights reserved.