Темы курсовых работ по «Технология программирования (Python)»
Комментарии к алгоритму Тоома—Кука
жүктеу/скачать 0,69 Mb.
|
| Комментарии к алгоритму Тоома—Кука
Мы почти не обосновывали и не объясняли алгоритм; вам придется кое в чем поверить на слово. Причина отсутствия объяснений кроется в том, что они крайне длинны и математичны, и у нас просто не хватило бы места. Изложение алгоритма в большой степени опирается на монографию Кнута; если вы хотите ознакомиться с алгоритмом подробнее, обратитесь к этой книге. Мы все же дадим некоторые комментарии, возможно способствующие лучшему пониманию. 1. (Структура алгоритма.) Наша версия алгоритма отличается от описанной у Кнута в основном структурой циклов. На рис. 20.1 представлена общая схема верхнего уровня алгоритма Тоома—Кука. Рисунок 20.1. Управляющая схема алгоритма Тоома—Кука. 2. (Таблицы размеров.) Значения массивов, вычисленные на шаге 2, показаны в табл. 20.1; число в колонке nk равно наибольшему числу битов, которое может быть обработано алгоритмом при K = k. Очевидно, что предельное значение 10 для K не является очень серьезным ограничением. При желании этот предел можно повысить.
Таблица 20.1. Значения q, r и n
3. (Глубина стеков в первом цикле.) Максимальная глубина стеков U и V на шагах с 5-го по 8-й равна 2(rK−1 + 1). Глубина стека С может возрастать до . 4. (Глубина стеков во втором цикле.) Общая глубина стека W может достигать . Управляющий стек может достигать глубины . На шагах 14, 15 и 16 верхняя часть стека W используется как массив. Этот массив может содержать максимум 2rk−1 + 2 элементов. 5. (Размер исходных данных.) Для любого числа битов n в диапазоне ni−1 + 1 ≤ n ≤ ni алгоритм Тоома—Кука требует одинакового времени вычислений. Таким образом, сложность вычислений весьма негладко зависит от размера исходных данных. Поэтому при выполнении длинных вычислений имеет смысл подбирать число битов вблизи верхнего конца одного из диапазонов для n. Учитывайте, что для представления одной десятичной цифры требуется примерно 3⅓ бита. 6. (Как умножить два 32-разрядных числа?) На шаге 9 требуется умножить два 32-разрядных числа, получив 64-разрядное произведение, причем оба сомножителя обязательно положительны. На многих ЭВМ имеется аппаратная возможность такого умножения, но результат нельзя получить, пользуясь языками высокого уровня. Ну и, конечно, некоторые ЭВМ не имеют подобней аппаратуры. Поэтому для выполнения этого умножения нужно написать подпрограмму, причем она должна быть эффективной, поскольку время работы алгоритма определяется главным образом временем умножения 32-разрядных чисел. Вероятно, достаточно хорошим методом будет разбиение чисел на части и моделирование ручного способа умножения. Тем не менее если нужно получить произведение uv и число и записано в виде u1·216 + u0, a v — в виде v1·216 + v0, то произведением будет (232 + 216)u1v1 + 216(u1 − u0)(v0 − v1) + (216 + 1)u0v0. Вычисление по этой формуле выполняется при помощи только 16-битовых вычитаний и умножений, а также некоторых сдвигов и сложений. Обратите внимание, что одно умножение сэкономлено. жүктеу/скачать 0,69 Mb. Достарыңызбен бөлісу:
|