atcoder/ac-library

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

mizar opened this issue · 1 comments

mizar commented

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):
  • 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

yosupo06 commented

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.

  • 👍2
  • 👀1