Быстрые алгоритмы деления. Деление чисел методом Ньютона

6. Быстрые алгоритмы деления

Деление чисел методом Ньютона

Для определенности будем считать, что делимое  и делитель  записаны в позиционной системе счисления по основанию . При этом длины чисел  и  равны, соответственно,  и .

Предварительное обсуждение

Задача нахождения частного сводится к определению приближенного значения дроби  с точностью ½, с последующим его округлением до ближайшего целого, и, возможно его уточнением. Уточнение частного требуется, если округление приближенного значения дроби  происходит не в ту сторону. Пусть — полученное частное. Тогда , и, значит, искомое частное отличается от полученного, не более чем на 1. Для уточнения частного вычислим остаток  и, если , то частное надо уменьшить на 1. Если , то частное надо увеличить на 1.

Приближенное значение дроби  с точностью до ½ можно получить как произведение  на приближенное значение дроби с точностью . Последний факт следует из неравенства . В свою очередь, приближенное значение дроби  можно получить, решая уравнение  методом Ньютона (методом касательных).

Описание метода

Пусть  — некоторое начальное приближение к дроби . О методах выбора  поговорим ниже. Допустим, на -ой итерации построено приближение . Уравнение касательной в точке  к функции  имеет вид . Точка пересечения касательной с осью абсцисс равна . Взяв эту точку в качестве следующего приближения , повторим процесс. И так до тех пор, пока не будет достигнута требуемая точность приближения.

Условия сходимости

Обозначим через  погрешность приближенного решения , т.е. . При  имеем , или .

Из полученной рекуррентной формулы  выводим  или . Из равенства  вытекает, что величина  стремится к нулю с ростом k только тогда, когда .

Выбор начального приближения

Укажем способ выбора , при котором выполняется неравенство . Положим  равным , где  — ближайшее целое, не превосходящее дроби . Трудоемкость вычисления значащих разрядов  имеет порядок . Далее, . Подставим вместо  выражение , где , получим . Поскольку в модуле стоит разность одинаковых по знаку чисел, то  не превосходит наибольшего из них. Так как и , то .

Оценка числа итераций метода

Оценим число итераций метода Ньютона, необходимое для достижения требуемой точности. Из равенства  и неравенства  выводим соотношение . Из неравенства  и  находим , или . Таким образом, число итераций методом Ньютона не больше .

Влияние погрешности вычислений на число итераций

Полученная оценка числа итераций метода Ньютона справедлива, если на каждой итерации  выполняется неравенство .

Выполнение этих неравенств гарантировано при точном вычислении  по формуле . Однако, точное вычисление  по этой формуле приводит к быстрому росту числа знаков после запятой. Чтобы избежать роста числа знаков после запятой предлагается округлить , но так чтобы неравенство  сохранилось.

Для определенности, пусть . В силу выпуклости функции  величина  всегда находится левее , т.е. . Действительно, . Таким образом, если округлить величину  в сторону увеличения с точностью до , то неравенство  сохранится. Обозначим через τ ошибку округления . Тогда . Поскольку под модулем стоит разность одинаковых по знаку чисел, то . Отсюда, учитывая неравенства τ< и выводим .

Оценим трудоемкость k-ой итерации метода Ньютона (k ≥ 1). Из сказанного ранее следует, что x_k-1 можно округлить в сторону возрастания с точностью до. Таким образом, число знаков после запятой x_k-1 больше 2^k-1+n. Из неравенств и b≥p^n-1делаем вывод, что первые n-1 разрядов после запятой равны нулю. То есть, число x_k-1 представляется в виде , где z_k-1 — целое число по длине не больше 2^k-1+1.

Общая оценка трудоемкости

Пусть трудоемкость умножения целых чисел длины s и l равна T_у(s + l). Тогда трудоемкость вычисления x_k по формуле (2-bх_k-1)х_k-1 = (2, с последующим округлением в  разрядах по порядку определяется величиной О(T_у(2^k+n)). Общая трудоемкость метода Ньютона не превосходит по порядку О.

Приведем оценку трудоемкости операции деления методом Ньютона в предположении, что умножение проводится с использованием быстрого преобразования Фурье. В этом случае T_у(l) = О(l∙logl) и вычисление x_k лучше вести по формуле . При этом, образы ,  вычисляются сразу. Потом над ними проводятся соответствующие операции умножения, вычитания, и только после этого восстанавливается результат. Поскольку , то длина произведения  не превосходит 2^k-1+1+n. Таким образом, трудоемкость k-ой итерации деления по порядку не превосходит О, а, значит, трудоемкость всего метода ограничена сверху величиной О O(m log m log (m-n)).

Тем самым доказана

Теорема. Трудоемкость деления чисел с остатком ограничена сверху величиной O(m log m log (m-n)).

Деление целых чисел без остатка

Если числа а и b заведомо делятся друг на друга, то можно воспользоваться версией метода Ньютона в р-адической арифметике. В дальнейшем будем считать р простым числом. Если b делится на p^k, то его последние k разрядов равны 0. Поскольку а делится на b, то а делится на p^k. Отбрасывая последние k нулевых разрядов чисел а и b, приходим к задаче деления, где b не делится на р. Так как р — простое число и b₀≠0, то наибольший общий делитель b₀ и р равен 1. Расширенным алгоритмом Евклида найдем числа u и v, что ub₀+рv = 1. Положим х₀ = u. Далее проводим итерации метода Ньютона, вычисляя х_k по формуле х_k = (2-х_k-1b)х_k-1. Поскольку р — основание системы счисления, то, по сути, мы проводим операции над младшими 2^k разрядами, отбрасывая старшие. Обозначим через η_k величину 1-bх_k. Индукцией по k покажем сравнение η_k ≡ 0 . При k = 0 имеем: η₀ = 1-bх₀ ≡ 1- b₀u ≡ 0(mod р). Пусть η_k-1≡0_. Тогда, η_k=1-bх_k≡1-b(2-х_k-1b)х_k-1≡

≡(1-bх_k-1)² ≡.

Единственным решением сравнения а ≡ bх(mod р^m-n) является частное а/b. Поэтому, не более чем через log₂(m-n)+1 итерацию метода, частное будет найдено. Трудоемкость метода Ньютона в этом случае не превосходит O(). Если для умножения используется быстрое преобразование Фурье, то Т_у(l) = O(l logl). Трудоемкость метода в этом случае оценивается величиной O(. Как видим, за счет более экономной схемы умножения, трудоемкость деления чисел нацело, по порядку, имеет ту же трудоемкость, что и умножение.

Тем самым доказана

Теорема. Трудоемкость деления чисел без остатка ограничена сверху величиной .

Резюме

•В лекции подробно разобраны быстрые алгоритмы деления.

•Приведены оценки трудоемкости.

Контрольные вопросы и упражнения:

•Возможность распараллеливания алгоритма деления.

•Как изменится алгоритм деления чисел без остатка, если основание системы счисления будет составное.

•Насколько принципиальный характер носит отличие верхних оценок трудоемкости алгоритмов деления с остатком и без остатка.

•Составить алгоритм деления целых чисел без остатка при основании равном 10.

•Составить алгоритм деления целых чисел без остатка при основании равном 2k.