Missing correctness of arithmetic operations
Closed this issue · 7 comments
For + the calculations not always correct if mod >= typemax(T) ÷ 2.
For * the calculations are not always correct if mod^2 >= typemax(T).
Test cases:
julia> p = typemax(T) ÷ 4 * 3
6917529027641081853
julia> Mod(-1, p) + Mod(-2, p) == Mod(-3, p)
false
julia> p = Int(ceil(sqrt(typemax(T)))) + 1
3037000501
julia> Mod(-1, p) * Mod(-1, p) == Mod(1, p)
false
julia> a = Mod(UInt32(p-1), p)
Mod(999998,999999)
julia> a * a
Mod(590895,999999)
julia> p = UInt32(999999)
0x000f423f
julia> a = Mod(UInt32(p-1), p)
Mod(999998,999999)
julia> a * a == Mod(UInt32(1), p)
false
That is due to unhandled arithmetic overflow in the bits integer + and * operations.
We have the same issue with ordinary integers. For example:
julia> a = typemax(Int)-2
9223372036854775805
julia> a*a > a
false
A fix could be made but that might result in a performance hit. I think the better option for folks working with very large integers is to create Mod values based on BigInt values.
julia> p = typemax(Int) ÷ 4 * 3
6917529027641081853
julia> p = big(p)
6917529027641081853
julia> Mod(-1,p) + Mod(-2,p) == Mod(-3,p)
true
We have the same issue with ordinary integers
true, but everybody knows, that for example Int64 performs arithmetic operations modulo 2^64.
There are Int64 and Int32 operators with overflow available, which would allow to fix that without much performance penalty. For example multiplication:
prod, ovf = Base.mul_with_overflow(a, b)
ovf || return prod % mod
oftype(mod, widemul(a, b) % mod) # double precision product only in case of overflow
or addition:
sum = a + b
0 <= sum < mod ? sum : sum - mod # assuming 0 <= a, b < mod
Hmmm... OK, I'll think on this :-)
I think I've got it fixed.
I see, the operations are correct now. I you could add the corresponding test cases ...
btw, I am an undiscrete mathematician :-)
Yes ... I should do that ...
OK. Tests added. And as a discrete mathematician, I need continuous improvement :-).