Special support for 63-bit division (unsigned)? about libdivide HOT 2 CLOSED

Yes and even better: if your numerator is N-1 bits, then we only need an N bit magic number, and we can do without the add path entirely:

uint64_t q = libdivide_mullhi_u64(denom->magic, numer);
return t >> denom->more;

I'm not sure how to evaluate whether N-1 bit division is broadly useful. The API surface area is already large and it's becoming unwieldy to maintain. N-1 bit division would nearly double the size.

from libdivide.

That's fair. I'll close this thread. If N-1 bit division is indeed broadly useful, someone will eventually re-open this thread and describe their use case.

Just for the record, I was just playing around with the idea of keeping the API the same and making a dynamic decision whether to use N-1 bit division. In order to minimize branch mispredictions, this decision would have to be sticky: once we've seen a numerator with bit N-1 set, the next 100 or so invocations of the division function would use the full N bit division, even if the numerators were small. The necessary state would be opportunistically kept on the stack (hoping that it would be preserved across function invocations, with should be true in hot loops, and shouldn't matter otherwise). Unfortunately, this approach turned out to generate way too much overhead (at least in my implementation).

from libdivide.