A new faster algorithm to compute 64-bit signed floor division

I love to see this kind of optimization, of course, but there are other cases where Robison division is great, just because it has basically the same form for every divisor:

1. The divisor is not actually a compile-time constant, but comes from a small set. You can compute a table of corresponding constants and use the same code for every divisor.

2. You want to do many divisions by many different divisors (whether known at compile-time or drawn from a small set, like above, or pre-computable and applied many times... think of something like a quantization matrix for image coding, for example). Here Robison easily SIMDifies, whereas an algorithm that needs different code paths for every divisor is going to be much more difficult.

Regarding the lack of native signed-unsigned multiplies, as someone who does a lot of multimedia processing, I find the set of available multiplication instructions on x86 and ARM to be rather shamefully limited (especially x86). I recall a colleague who used to optimize for VideoCore (the GPU in a Raspberry Pi) saying that when he first started he was astounded that it had 80 different multiply instructions, but within a year or two he had used basically all of them.

> 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.

I have great respect for those who conduct research on algorithm optimization.