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

ac-library/atcoder/modint.hpp

Lines 74 to 83 in 6c88a70

	mint& operator+=(const mint& rhs) {
	_v += rhs._v;
	if (_v >= umod()) _v -= umod();
	return *this;
	}
	mint& operator-=(const mint& rhs) {
	_v -= rhs._v;
	if (_v >= umod()) _v += umod();
	return *this;
	}

ac-library/atcoder/modint.hpp

Lines 191 to 200 in 6c88a70

	mint& operator+=(const mint& rhs) {
	_v += rhs._v;
	if (_v >= umod()) _v -= umod();
	return *this;
	}
	mint& operator-=(const mint& rhs) {
	_v += mod() - rhs._v;
	if (_v >= umod()) _v -= umod();
	return *this;
	}

rust-lang-ja/ac-library-rs@ab2c3ed#diff-9c0db0574dc35afe73adabeaba95ec11f15af83bb2cf1d5d70b916b6da84e2eaR793-R812

Related Issue/PR

• mul_mod for 2^31 < m < 2^32 #149
• fix #149: improve barret algorithm #163
• mul_mod for 2^31 < m < 2^32 rust-lang-ja/ac-library-rs#111
• u32 modulo fix rust-lang-ja/ac-library-rs#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.