Issue-38: backend cleanup
Closes #38 (closed)
A list of changes that were made:
STRUCTURE: In all backends now methods are in following order:
// CONSTRUCTORS
// ASSIGNMENT OPERATORS
// ACCESSORS
// ARITHMETIC OPERATIONS
// MODULAR ARITHMETIC OPERATIONS
// SHIFT OPERATIONS
// COMPARE
// CONVERTERS
// OTHER FUNCTIONS
// STRINGS & STREAMS
// SERIALIZATION
METHOD NAMES:
-
Methods for modulo operations are reconsidered:
- methods with Fast suffix - components < modulus.
- methods with additional mu parameter - we use Barrett reduction.
- method for multiplication with Precon suffix and bInv parameter - we use Shoup method
-
Examples for multiplication:
- ModMul(b, mod) naive modulo multiplication
- ModMulFast(b, mod) naive modulo multiplication with components < modulus
- ModMul(b, mod, mu) multiplication using Barrett reduction.
- ModMulFast(b, mod, mu) multiplication using Barrett reduction with components < modulus
- ModMulFastPrecon(b, mod, bInv) Shoup multiplication.
IMPLEMENTATION:
- All methods that are implemented have a variant with Eq.
- A few methods I'm not sure in have FIXME tasks.
- In interface.h methods MultiplyAndRound/DivideAndRound added to BigIntegerInterface
- ComputeMu() now in interface, not in nbtheory
- Not all methods are implemented:
- ModMulPrecon(b, mod, bInv) we always have components smaller than modulus, so no need for this method
- ModAddFast(b, mod, mu) seems to be same as ModAdd(b, mod, mu), so there is only ModAdd(b, mod, mu) implemented.
- Removed modulus.GetMSB() > MAX_MODULUS_SIZE support, as we use NativeVectors only to have fast arithmetics. SetModulus() throws an exception if modulus.GetMSB() > MAX_MODULUS_SIZE. Removed all checks in other places.
- In ckkspackedencoding.cpp line 56 changed q from 2^63-1 to 2^60-1 not to throw exception (Not sure if it is ok, but all tests works)
CLEANUP:
- Tried to unify the comments for arithmetic methods.
- In exp_int removed commented code and DEBUG checks.
Edited by Yuriy Polyakov