Алгоритм деления

Алгоритм деления — это алгоритм, вычисляющий для двух данных целых чисел и их частное и/или остаток, результат деления с остатком. Некоторые из алгоритмов предназначены для вычислений вручную, другие реализованы в цифровых схемах и программном обеспечении. Алгоритмы деления разбиваются на две большие категории: медленное деление и быстрое деление. Алгоритмы медленного деления дают по одному знаку результата за итерацию. Примерами медленного деления служат алгоритмы деления , и . Методы быстрого деления начинаются с аппроксимации конечного частного и дают вдвое больше знаков в конечном результате на каждой итерации. Алгоритмы и попадают в эту категорию. Варианты этих алгоритмов позволяют использовать быстрые алгоритмы умножения. В результате этого для больших целых чисел время вычисления, необходимое для деления, будет тем же самым (с точностью до постоянного множителя), что и время, необходимое для выполнения умножения, какой бы алгоритм из перечисленных не был применён. Обсуждение будет использовать обозначения , где * — числитель (делимое) * — знаменатель (делитель) являются входными числами, а * — частное * — остаток являются выходными данными.