|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apfloat.internal.IntElementaryModMath
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
int
s 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 |
public IntElementaryModMath()
Method Detail |
public final int modMultiply(int a, int b)
a
- First operand.b
- Second operand.
a * b % modulus
public final int modAdd(int a, int b)
a
- First operand.b
- Second operand.
(a + b) % modulus
public final int modSubtract(int a, int b)
a
- First operand.b
- Second operand.
(a - b + modulus) % modulus
public final int getModulus()
public final void setModulus(int modulus)
modulus
- The modulus.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |