Быстрое деление 64-битных чисел с округлением вниз

Что такое деление целых чисел со знаком с округлением вниз?
Деление целых чисел со знаком с округлением вниз — это когда мы выполняем a/b и получаем результат, округлённый в сторону −∞, в то время как стандартное деление (с усечением) чисел со знаком округляется в сторону 0. Как сказано в книге Hacker's Delight, «[Я подозреваю, что] деление с округлением вниз чаще даёт нужные нам результаты».
Эта статья посвящена делению с округлением вниз чисел во всём диапазоне, когда делитель известен во время компиляции.
Несмотря на полезность этой функции, мир деления целых чисел с округлением вниз находится в полном хаосе:
• В популярных компиляторах и многих языках нет нативной реализации такого деления (например, в C/C++/Go/Swift).
• Языки и программные библиотеки, которые всё же реализуют его, почти не никогда не применяют самые быстрые алгоритмы.
• По крайней мере в одной крайне распространённой программной библиотеке уже более четырёх лет присутствует забагованная реализация такого деления с переполнением! (подробности ниже)
• При онлайн-запросах и промптах к LLM обычно выдаются только самые медленные алгоритмы
• И, наконец, в Hacker's Delight (по сути, Библии низкоуровневой компьютерной математики) почти ничего о нём не говорится!
В этом посте я не только расскажу о быстрых алгоритмах, но и приведу новый быстрый алгоритм.















