Поделить нельзя — умножить, или Алгоритм быстрого деления по методу Ньютона-Рафсона

Поделить нельзя — умножить, или Алгоритм быстрого деления по методу Ньютона-Рафсона

Все мы в школе проходили деление «столбиком» — простой алгоритм, который несложно реализовать, вот только не очень быстрый. В прошлый раз мы рассматривали, как компилятор оптимизирует деление в случаях, когда делитель известен во время компиляции, но применение его напрямую, чтоб оптимизировать деление для делителей, определяемых в run-time, невозможно: вычисление констант сдвига и умножения само по себе требует деления.

В этот раз поговорим о другом методе, сводящем деление к умножениям и битовым сдвигам, основанном на методе поиска корней функции