z4120's blog

By z4120, history, 5 years ago, In English

Note: This technique had been used before at https://codeforces.net/blog/entry/60851 (editorial code of problem F) and https://codeforces.net/problemset/submission/1017/41357847 .

While this solution is faster than using int64_t (because Codeforces machines are 32-bit), the time limit should be loose enough for solution that does not use this trick to pass. However, this trick may be useful if you want to be very fast or implement an unintended/suboptimal brute force solution. (the same thing can be said about fast input/output methods. On Codeforces, cin/cout is usually fast enough)

This is definitely faster than the usual return (long long)a * b % mod, but it might be slower than Montgomery multiplication.


Given a positive integer md, and two positive integers a and b in range [0, md-1], the following function will compute (int) ((long long) a * b % md): (the quotient of the division is stored in variable d)

int mul(int a, int b) {
  unsigned long long x = (long long) a * b;
  unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
  asm(
    "divl %4; \n\t"
    : "=a" (d), "=d" (m)
    : "d" (xh), "a" (xl), "r" (md)
  );
  return m;
}

x86 assembly has an instruction to divide a 64-bit integer by a 32-bit integer, provided that both the quotient and the remainder fits in 32 bits. (More details)

However, it's not a compiler bug that GCC does not optimize code like this

uint32_t f(uint64_t a, uint32_t b) { return a % b; }

to use that assembly instruction, because that would not work well (as required by the C++ standard) when the quotient exceeds 2^32. See also 64308 – Missed optimization: 64-bit divide used when 32-bit divide would work.

Unfortunately, I think there isn't any intrinsic function of GCC that provides the functionality, and it's necessary to use asm. (source)


Benchmark code: (you can copy-paste that to https://codeforces.net/problemset/customtest )

Code

Because Codeforces caches the result, you may need to change the input or some whitespaces in the code to re-run the code. When I run it the result is ~= 0.45 vs 0.65, which is a 30% performance gain.

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

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Can you share the results of the benchmark which showed performance gains?

On the contrary, I didn't observe any gain for 64-bit: http://quick-bench.com/SUfusGHbNvP8a961_8QrWYLqbJw

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

    Is that on a 32-bit machine?

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

    You used mul_complex function in both measurements. So you just compare it with itself. Nothing strange that you didn't see the difference :)

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    Also, static_assert(sizeof(size_t) == 4, "not 32 bit machine"); fails on quick-bench, which shows that they use a 64-bit machine.

    UPD: Benchmark code added to the post, which shows a 30% performance improvement on Codeforces machines.