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