This looks very interesting, and very well written. I'll definitely give a it a thorough read when I get the time, and probably include the technique in our compiler. Floor division is almost always more useful than truncating division, so having a fast path there would be nice.

I can't help but do a shameless plug for another recent result in that space: we developed fast algorithms for 64-bit integer divisions (by constants and non-constants) for JavaScript, where you don't even have 64-bit integers to start with. Paper [1] and slides [2] available. The Scala.js compiler uses all of that. The Kotlin/JS compiler recently accepted my PR for the non-constant divisors algorithms.

[1] https://arith2026.org/papers/64-bit%20Integer%20Division%20f...

[2] https://arith2026.org/slides/session_1_2_doeraene.pdf