Бен Джоффе представил новый алгоритм для деления 64-битных целых чисел с округлением вниз (в сторону минус бесконечности). Решение ориентировано на случаи, когда делитель известен на этапе компиляции, что актуально для языков C, C++, Go и Swift, где подобная операция не реализована нативно.
На архитектуре ARM новый метод обеспечивает прирост пропускной способности на 10–20% для большинства 64-битных делителей при сохранении прежних или меньших задержек. Для положительных 64-битных делителей производительность возрастает на 5–10% в 80% случаев, а для отрицательных — в 60% случаев.
Алгоритм применим для различных битовых длин, однако максимальную эффективность показывает именно на 64-битных вычислениях. Для меньших диапазонов автор рекомендует рассмотреть алгоритм Робисона. Код реализации распространяется по лицензии MIT.
Автор подчеркивает, что стандартное деление в большинстве языков программирования использует усечение в сторону нуля, что приводит к ошибкам при работе с отрицательными числами, например, при обработке временных меток. Новый алгоритм обеспечивает корректное деление во всем диапазоне 64-битных чисел.



