Книга: Этюды для программистов

Что можно сказать относительно деления?

При вычислении предложенных рядов наряду с умножением используется деление чисел высокой точности. К счастью, при помощи алгоритма умножения удается выполнять деление почти так же быстро, как умножение. Для нахождения частного нужно приблизительно угадать число, обратное к делителю, скорректировать его, чтобы обратное стало точным, и затем умножить на делимое. Уточнение обратного осуществляется по методу Ньютона. Даны два числа [m, u] и [n, v]; мы считаем, что u ? v (хотя это предположение несущественно) и что n-й бит v равен 1 (т. е. у v нет старших нулей). Чем больше разница размеров и и v, тем более точным будет частное; разницу можно увеличить, умножая и на степень двойки. Отметим, что алгоритм деления будет неоднократно вызывать алгоритм умножения. Для нескольких первых из этих умножений можно воспользоваться обычной операцией умножения коротких чисел. Кроме того, все умножения и деления на степень двойки суть фактически сдвиги влево и вправо.

1. (Выбор размера обратного.) Найти наименьшее j, такое, что 2^j ? max (m, 2n). Присвоить к значение 2^j?1.

2. (Нормализация v.) Присвоить [k, v] значение 2^k?n [n, v]. На этом шаге мы сдвигаем v влево, чтобы оно заняло k битов, причем левый бит был бы равен 1. Присвоить [2, а] значение [2, 2].

3. (Вычисление последовательных приближений к 1/v.) Выполнить шаг 4 для i = 1, 2, …, j ? 1.

4. (Вычисление приближения из 2ⁱ битов.) Присвоить [2ⁱ⁺¹, d] значение

2^3·2i [2^i?1 + 1, a] ? [2^i?1 + 1, a]² ([k, v]/2^k?2i)

Деление в скобках (фактически сдвиг вправо) должно выполнятъся до умножения; идея состоит в том, чтобы ускорить умножение, отбросив лишние биты v, ненужные в данном приближения. Хотя кажется, что результат d может содержать больше 2ⁱ⁺¹ битов, этого никогда не произойдет. Затем присвоить [2ⁱ + 1, а] значение [2ⁱ⁺¹, d]/2^i?1.

5. (Улучшение окончательной оценки.) Присвоить [3k, d] значение

2^2k[k + 1, а] ? [k + 1, а]²·[k, v].

Затем присвоить [k + 1, а] значение

([Зk, d] + 2^2k?2)/2^2k?1.

6. (Окончательное деление.) Выдать в качестве результата

([k + 1, a] · [m, u] + 2^k+n?2)/2^2+k?1[33].

Оглавление книги