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

Комментарии к алгоритму Тоома - Кука

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

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

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

Мы почти не обосновывали и не объясняли алгоритм; вам придется кое в чем поверить на слово. Причина отсутствия объяснений кроется в том, что они крайне длинны и математичны, и у нас просто не хватило бы места. Изложение алгоритма в большой степени опирается на монографию Кнута; если вы хотите ознакомиться с алгоритмом подробнее, обратитесь к этой книге. Мы все же дадим некоторые комментарии, возможно способствующие лучшему пониманию.

1. (Структура алгоритма.) Наша версия алгоритма отличается от описанной у Кнута в основном структурой циклов. На рис. 22.1 представлена общая схема верхнего уровня алгоритма Тоома - Кука.

2. (Таблицы размеров.) Значения массивов, вычисленные на шаге 2, показаны в табл. 22.1; число в колонке n_k равно наибольшему числу битов, которое может быть обработано алгоритмом при K = k. Очевидно, что предельное значение 10 для K не является очень серьезным ограничением. При желании этот предел можно повысить.

3. (Глубина стеков в первом цикле.) Максимальная глубина стеков U и V на шагах с 5-го по 8-й равна 2(r_k-1+1). Глубина стека C может возрастать до ∑(r_i + 1) для i=1...K-1.

4. (Глубина стеков во втором цикле.) Общая глубина стека W может достигать ∑r_i для i=1...K-1. Управляющий стек может достигать глубины (∑r_i для i=1...K-1) + l. На шагах 14, 15 и 16 верхняя часть стека W используется как массив. Этот массив может содержать максимум 2r_k-1 + 2 элементов.

5. (Размер исходных данных.) Для любого числа битов n в диапазоне ni-i + 1 ≤ n ≤ n_i алгоритм Тоома - Кука требует одинакового времени вычислений. Таким образом, сложность вычислений весьма негладко зависит от размера исходных данных. Поэтому при выполнении длинных вычислений имеет смысл подбирать число битов вблизи верхнего конца одного из диапазонов для n. Учитывайте, что для представления одной десятичной цифры требуется примерно 3¹/₃ бита.

6. (Как умножить два 32-разрядных числа?) На шаге 9 требуется умножить два 32-разрядных числа, получив 64-64-разрядное произведение, причем оба сомножителя обязательно положительны. На многих ЭВМ имеется аппаратная возможность такого умножения, но результат нельзя получить, пользуясь языками высокого уровня. Ну и, конечно, некоторые ЭВМ не имеют подобней аппаратуры. Поэтому для выполнения этого умножения нужно написать подпрограмму, причем она должна быть эффективной, поскольку время работы алгоритма определяется главным образом временем умножения 32-разрядных чисел. Вероятно, достаточно хорошим методом будет разбиение чисел на части и моделирование ручного способа умножения. Тем не менее если нужно получить произведение uv и число u записано в виде u₁·2¹⁶ + u₀ a v - в виде v₁·2¹⁶ + u₀, то произведением будет
(2³² + 2¹⁶)·u₁v₁ + 2¹⁶·(u₁ - u₀)(v₁ - v₀) + (2¹⁶ + 1)·u₀v₀

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

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

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

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

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

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

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