Блог пользователя a_gt3_rs

Автор a_gt3_rs, история, 2 месяца назад, По-английски

When I was doing 1207F - Remainder Problem, I don't know why my program got TLE. Then this ONE trick cut 1 second off my program. You can see this video for more information: https://www.youtube.com/watch?v=ssDBqQ5f5_0. When the compiler compiles x/9, the code roughly converts to ((long long)954437177*x)>>33. Division is a much more expensive operation than multiplies and shifts. But what's the special constant 954437177? It's $$$\lceil \frac{2^{33}}{9} \rceil$$$. So we have this identity which is vaild for every $$$0\leq a< 2^{31}$$$:

$$${\lfloor \frac{a}{x} \rfloor} ={ \lfloor{\frac{a*\lceil{2^{33}/x}\rceil}{2^{33}}}\rfloor}.$$$

You can clearly see how this speeds up 1207F: 244531668, 244540601. Note that gcc also does this trick on 64 bits, but the exponent 33 is replaced by 64 ($$$0\leq a<2^{63}$$$).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

Автор a_gt3_rs, история, 2 месяца назад, По-английски

This is only a suggestion. GCC 13.2 have nearly full C++23 support & (we once had GCC 11 with C++20). So I just want that GCC 13.2 (or 14) has C++23 support enabled with -std=c++23 (as another GCC 13 compiler option, or when GCC 14 is released, or when GCC 11 is back).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится