ModInt 2^31 <= m < 2^32 for addition/subtruction

[mizar]

The implementation of addition and subtraction in the ModInt structure does not seem to assume $2^{31}\le m\lt 2^{32}$.

Suggested mitigation

• Addition (plan A, cast 32/64-bit integer):
  • Cast this._v and rhs._v to 64-bit integer type.
  • Performs addition and compares it with the value of umod().
  • If the sum is greater than umod(), subtract the value of umod() from the sum.
  • Cast the result to a 32-bit integer type.
• Addition (plan B, 32-bit integer overflow detection):
  • Performs addition and detects overflow.
    • GCC/Clang: Integer-Overflow-Builtins
    • x86 intrinsic: _addcarry_u32
    • MSVC intsafe.h: UIntAdd
    • boost: Safe Numerics
  • If the addition is overflowing or the sum is greater than or equal to the value of umod(), subtract umod() from the sum.
• Subtraction:
  • If rhs._v is greater than self._v, then self._v - rhs._v + umod(), otherwise self._v - rhs._v.

Code

https://github.com/atcoder/ac-library/blob/6c88a70c8f95fef575af354900d107fbd0db1a12/atcoder/modint.hpp#L74-L83 https://github.com/atcoder/ac-library/blob/6c88a70c8f95fef575af354900d107fbd0db1a12/atcoder/modint.hpp#L191-L200 https://github.com/rust-lang-ja/ac-library-rs/pull/112/commits/ab2c3ed512c4470374c09cd5ce0089af8c8894f4#diff-9c0db0574dc35afe73adabeaba95ec11f15af83bb2cf1d5d70b916b6da84e2eaR793-R812

Related Issue/PR

• https://github.com/atcoder/ac-library/issues/149
• https://github.com/atcoder/ac-library/pull/163
• https://github.com/rust-lang-ja/ac-library-rs/issues/111
• https://github.com/rust-lang-ja/ac-library-rs/pull/112

[yosupo06]

Thanks for suggestion, but we don't have a plan to extend mod range to m < 2^32. As far as I know, at least 99% usage of modint is m < 2^31. TBH I don't came up any recent problems that requires 2^31 < m < 2^32. So, we prefer to prepare m < 2^31 modint rather than m < 2^32 modint with tricky technique.