A new faster algorithm to compute 64-bit signed floor division
benjoffe.com37 points by benjoffe 2 days ago
37 points by benjoffe 2 days ago
> 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.
Hello, you are correct that part of it is done to death for standard integer division.
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).