Fast Division Trick

Правка en9, от yoshi_likes_e5, 2024-05-24 13:35:43

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,x < 2^{31}$$$:

$$${\lfloor \frac{a}{x} \rfloor} ={ \lfloor{\frac{a*\lceil{2^{31+\lfloor{log_2(x)}\rfloor}/x}\rceil}{2^{31+\lfloor{log_2(x)}\rfloor}}}\rfloor}.$$$

You can clearly see how this speeds up 1207F: 244531668, 244540601. Note that gcc also does this trick on 64 bits.

After brute forcing with $$$a = 2^{31}-1$$$ I got this new, fixed identity. This should work for all a (while the old one does not).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский yoshi_likes_e5 2024-05-24 13:37:11 16
en9 Английский yoshi_likes_e5 2024-05-24 13:35:43 193 Tiny change: 'ceil}{2^{33}}}\rfloor' -> 'ceil}{2^{31+\lfloor{log_2(x)}\rfloor}}}\rfloor'
en8 Английский yoshi_likes_e5 2024-03-31 15:02:43 19 Tiny change: 'aced by 64.' -> 'aced by 64 ($0\leq a<2^{63}$).'
en7 Английский yoshi_likes_e5 2024-03-31 13:40:59 87
en6 Английский yoshi_likes_e5 2024-03-26 14:02:08 2 Tiny change: 'on:244531688], [submi' -> 'on:244531668], [submi'
en5 Английский yoshi_likes_e5 2024-03-26 14:01:23 1 Tiny change: '44531688],[submissio' -> '44531688], [submissio' (published)
en4 Английский yoshi_likes_e5 2024-03-26 14:00:15 3 Tiny change: '}}\rfloor}$$.You can cl' -> '}}\rfloor}.$$ You can cl'
en3 Английский yoshi_likes_e5 2024-03-26 13:59:47 99
en2 Английский yoshi_likes_e5 2024-03-26 13:58:12 58
en1 Английский yoshi_likes_e5 2024-03-26 13:42:10 580 Initial revision (saved to drafts)