Class FloatElementaryModMath
 Direct Known Subclasses:
FloatModMath
float
data.
Note that although a floatingpoint data type is used, the data
will always be integers.
Since the moduli are close to 2^{24} 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 nearinteger result that would be rounded incorrectly, e.g. as in
0.333... * 3 = 0.999...
.
 Version:
 1.0
 Author:
 Mikko Tommila

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionfloat
Get the modulus.float
modAdd(float a, float b)
Modular addition.float
modMultiply(float a, float b)
Modular multiplication.float
modSubtract(float a, float b)
Modular subtraction.void
setModulus(float modulus)
Set the modulus.

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.
