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

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

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

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

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

Алгоритм Тоома - Кука весьма сложен, поэтому мы не будем подробно объяснять его; за этим можно обратиться к книге Кнута. Все же необходимо сообщить основные идеи и обозначения. Длинные числа должны быть как-то представлены; будем писать [p, u] для обозначения числа n из p битов. Вероятно, внутреннее представление [p, u] будет некоторой разновидностью списка или цепочки. Кроме основного алгоритма нам понадобятся подпрограммы для сложения и вычитания длинных чисел (используйте стандартный ручной метод сложения слева направо), умножения длинного числа на короткое (небольшое) число, деления длинного числа на короткое, сдвига длинного числа путем приписывания нулей справа и для разбиения длинного числа [p, u] на более короткие длинные числа [p/(r+1), u_r], [p/(r+1), u_r-1], ..., [p/(r+1), u₀], как описано выше. Кроме подпрограмм, работающих непосредственно с числами, алгоритм использует четыре стека для хранения промежуточных частичных результатов и несколько временных переменных, поэтому требуются подпрограммы для выполнения некоторых действий над стеком, а также подпрограммы для выделения и освобождения памяти под длинные числа. При написании всяческих вспомогательных подпрограмм черновой работы может оказаться предостаточно.

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

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

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

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

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

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