points by rf15 22 hours ago | 0 comments
> As you can see, the technique is so simple that I'd expect that somebody has done this before, but I've looked around and not found it documented anywhere.
I'm one of those people I suppose. Yes, if you want to play with microoptimisations and part of a calculation are known, you can flip a division into a mult (and shift).
This might seem somewhat useless at first, but you can use this to e.g. speed up calculations in nested loops, where you can precompute this for relevant loop-layers.
[–] benjoffe 22 hours ago
[–] rf15 21 hours ago
I found this by accident because I wanted to speed up a part on my Pebble watch face, I didn't even know the history of past attempts. The floor variant was born out of a particular rounding optimisation attempt that felt like it could be easier if I just use floor/ceil and moved it into a large int-multiplication space. (this is very tempting because certain constants for rendering and angle calculations are based around large integer constants on that platform, kinda doing half the work towards this idea by creating this particular constraint)
[–] Sharlin 17 hours ago
The mul-shift part is what any optimizing compiler does for known divisors and has done since the 90s, if anything it was more vital back then when the gap between div and mul was wider than today.
The `new` thing is the range-splitting which achieves the floor division for negative inputs (eg. sign-selected for 60% of divisors, and the negative/positive bump for the remaining 20%/20% of cases each).