madhur4127's blog

Avoid silly overflow mistakes taking modulo in C++
By madhur4127, history, 6 years ago, In English

TL;DR This article features Modular class which can be conviniently used for modular arithmetic more "naturally".

Motivation

Recent round featured an interesting problem 1081C - Colorful Bricks (if you plan to solve it, read this later). Combinatoric solution requires you to calculate:

Many contestants failed pretest because of missing modulo operation somewhere in code.

Solution

Many contestants use functions like add(ll a, ll b) or mul(ll a , ll b) which makes implementation somewhat clumsy.

I present you an alternate approach using Modular class.

template <int MOD=998'244'353>
struct Modular {
  int value;
  static const int MOD_value = MOD;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};

Using this code can be written more naturally in modular field just like integers. This implementation simplifies usage, for example:

// Chained Multiplication or Successive Simple Multiplication
Modular<998244353> a=1, m=123456789;
a *= m * m * m; // a = 519994069
// Inverse
a=inverse(m) // a=25170271
// fractions
Modular<> frac=(1,2); // frac=1*2^(-1) % 998244353 = 499122177
// Modular exponentiation
Modular<> power(2);
power=mexp(power,500); // power = 616118644

Credits to Jakube and here's the link to original source. Link: Modular.h

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

I have seen similar implementations before, but I'm not sure if performance is not an issue. Do you have benchmarks comparing this to the non-wrapped implementation, in terms of both time and memory usage?

I think having this in a critical loop (which runs, say 10^8 times) might be problematic, but I'm not sure; C++ compilers can do a lot of magic.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    that's c++. such abstractions do not cost anything here.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Isn't there overhead for the function call? Or can we be certain it is inlined

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        you are right, overhead for function calls is possible but for such trivial function I just assume they are inlined (I use such class for several years, didn't have any problem).

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I use a similar class. In my experience the abstraction doesn't noticeably reduce efficiency compared to manually applying the same operations, but it can cause you to use more operations that you actually need. In particular, when taking the sum of N numbers, it is more efficient to first sum them in long long, then reduce that sum, than to reduce after every addition.

    → Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Exactly what Wave said.

Perfomance in many cases of modular tasks is an issue and you should avoid copying by const Modular& rather using plain const Modular (since it doesn't really matter whether you put const here or not, you can keep it if you want compliler to help you a little) in most of your operators.

See this: this. Although being too unrealistic, you should generally avoid passing references to classes where sizeof(class) is around a single pointer due to a perfomance overhead over plain copy of that class.

P.S. I don't see this struct Modular <int N> as a good solution because such class makes it significantly harder to pass ints to functions

P.P.S. and yeah, specialization for long long modulo would've been really cool, since this is something really lame to implement over and over

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    Since all the methods and friend functions are implemented in the class, they will be inlined by default, and there is no difference in passing argument by reference or by value.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      being inline and being inlined is more or less orthogonal

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

integer do not form field btw

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Your implementation is very limiting. First, only int modulo is supported, no long long or any custom big integer class. Second, it won't work if the modulo isn't fixed, i.e. given in the input file.

I have similar class that can be found for example in these submissions: 26577783 24552744. Indeed, it's very convenient and I never faced any performance issues.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another issue is that it relies on the modulo being prime (the inverse is found using fermat's).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      yes, this works for prime modulo which is very common otherwise you can replace inverse with extended euclid.

      Because it is not very common where you need to find inverse in non-prime modulo (not for problems focused on extended euclid), so focusing on speed fermat is used.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    btw you may use std::integral_constant when modulo is constant instead of creating new class manually

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    1 . Considering general modulo (1e9+7, 9998244353), long long is not supported as multiplication function will change to somewhat like code below, which will not be efficient in case of common integer mod.

    Code

    2 . Submission (26577783) is not visible to me. Can you share code via other methods?

    3 . BigIntegers classes typically contain modulo operation.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, here's another submission 24552744

      There's also efficient long long multiplication in there.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's the result of running the code below in Custom test on Codeforces:

Code

The results (2e8 iterations) are:

Execution time (w/ class): 2338.19 ms.
Execution time (w/o class): 2797.18 ms.
=====
Used: 5116 ms, 0 KB
→ Reply