public class FloatElementaryModMath extends Object
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...
.
Constructor and Description |
---|
FloatElementaryModMath()
Default constructor.
|
Modifier and Type | Method and Description |
---|---|
float |
getModulus()
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.
|
public final float modMultiply(float a, float b)
a
- First operand.b
- Second operand.a * b % modulus
public final float modAdd(float a, float b)
a
- First operand.b
- Second operand.(a + b) % modulus
public final float modSubtract(float a, float b)
a
- First operand.b
- Second operand.(a - b + modulus) % modulus
public final float getModulus()
public final void setModulus(float modulus)
modulus
- The modulus.Copyright © 2019. All rights reserved.