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

Habr ·

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

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

Источник: Habr