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

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

Арифметические вычисления с высокой точностью

Чарлз Уэзерелл

Предыдущие разделы:
Арифметические вычисления числа π с высокой точностью. Общие соображения.
Как можно быстро умножать?
Алгоритм Тоома - Кука
Алгоритм быстрого умножения Тоома - Кука
Комментарии к алгоритму Тоома - Кука

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

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

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

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

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

4. (Вычисление приближения из 2ⁱ битов.) Присвоить [2ⁱ⁺¹, d] значение
2^{3·2^i}[2^i-1+1, a] - [2^i-1+1, a^]2·([k, v]/2^{k-2^i}).

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

5. (Улучшение окончательной оценки.) Присвоить [3k, d] значение
2^2k·[k+1, a] - [k+1, a]²·[k v].
Затем присвоить [k+1, a] значение
([3k, d] + 2^2k-2)/2^2k-1.

6. (Окончательное деление.) Выдать в качестве результата
([k+1, a]·[m, u] + 2^k+n-2)/2^k+n-1.

Примечание переводчика:

1) В алгоритм, вероятно, необходимо внести следующие изменения:
a) на шаге 1 заменить max(m, 2n) на max(2m-2n, 2n);
b) на шаге 4 заменить 2^{3·2^i} на 2^{3·2^(i-1)}.

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

Читать дальше:
Как использовать алгоритмы?
Литература

Подготовлено по публикации: Уэзерелл Ч. Этюды для программистов: Пер. с англ. - М.: Мир, 1982. - 288 с. Стр. 125 - 143.

К началу страницы

Web-сайт “Термист” (termist.com)
Термомеханическое упрочнение арматурного проката

Отсутствие ссылки на использованный материал является нарушением заповеди "Не укради"

Редактор сайта: Гунькин И.А. (termist.com@gmail.com)