Хабы: Блог компании RUVDS.com, Ненормальное программирование, C++, Алгоритмы
Все мы в школе проходили деление «столбиком» — простой алгоритм, который несложно реализовать, вот только не очень быстрый.
В прошлый раз мы рассматривали, как компилятор оптимизирует деление в случаях, когда делитель известен во время компиляции, но применение его напрямую, чтоб оптимизировать деление для делителей, определямых в run-time, невозможно: вычисление констант сдвига и умножения само по себе требует деления.
В этот раз хочется поговорить о другом методе, сводящем деление к умножениям и битовым сдвигам, основанном на методе поиска корней функции.
Смотреть код, формулы и анимации