Темы курсовых работ по «Технология программирования (Python)»
жүктеу/скачать 0,69 Mb.
|
- Бұл бет үшін навигация:
- Алгоритм быстрого умножения Тоома—Кука
| Алгоритм Тоома—Кука весьма сложен, поэтому мы не будем подробно объяснять его; за этим можно обратиться к книге Кнута. Все же необходимо сообщить основные идеи и обозначения. Длинные числа должны быть как-то представлены; будем писать [p, u] для обозначения числа u из p битов. Вероятно, внутреннее представление [p, u] будет некоторой разновидностью списка или цепочки. Кроме основного алгоритма нам понадобятся подпрограммы для сложения и вычитания длинных чисел (используйте стандартный ручной метод сложения слева направо), умножения длинного числа на короткое (небольшое) число, деления длинного числа на короткое, сдвига длинного числа путем приписывания нулей справа и для разбиения длинного числа [p, u] на более короткие длинные числа [p/(r + 1), ur], [p/(r + 1), ur−1], …, [p/(r + 1), u0], как описано выше. Кроме подпрограмм, работающих непосредственно с числами, алгоритм использует четыре стека для хранения промежуточных частичных результатов и несколько временных переменных, поэтому требуются подпрограммы для выполнения некоторых действий над стеком, а также подпрограммы для выделения и освобождения памяти под длинные числа. При написании всяческих вспомогательных подпрограмм черновой работы может оказаться предостаточно.
Алгоритм быстрого умножения Тоома—Кука Исходными данными служат два положительных длинных числа [n, u] и [n, v]; результатом — их произведение [2n, uv]. Используются четыре стека U, V, W и С, в которых при выполнении алгоритма будут храниться длинные числа, и пятый стек, содержащий коды временно приостановленных операций (имеется всего три кода, и для их представления можно воспользоваться малыми целыми числами). Массивы q и r целых чисел имеют индексы от 0 до 10; необходимо выделить память для этих двух массивов и для еще нескольких временных переменных, упомянутых в алгоритме. 1. (Начальная установка.) Сделать все стеки пустыми. Присвоить К значение 1, q0 и q1 — значение 16, r0 и r1 — значение 4, Q — значение 4 и R — значение 2. 2. (Построение таблицы размеров). Пока К < 10 и qK−1 + qK ≥ n, выполнять следующие вычисления. Изменить К на К + 1, Q — на Q + R; если (R + 1)² ≤ Q, то изменить R на R + 1; установить qK равным 2Q и rKравным 2R. Если цикл оканчивается из-за К = 10, то остановиться, выдав сообщение об ошибке — число битов n слишком велико, массивы q и r переполнились. В противном случае присвоить k значение K. Поместить [qK + qK−1, v] и за ним [qK−1 + qK, u] в стек С (вероятно, потребуется добавить к [n, u] и [n, v] слева нули). Поместить в управляющий стек код стоп. 3. (Главный внешний цикл.) Пока управляющий стек не пуст, выполнять шаги с 4-го по 18-й. Если на этом шаге управляющий стек окажется пустым, то остановиться с сообщением об ошибке; в управляющем стеке должен быть по крайней мере один элемент. 4. (Внутренний цикл разбиения и и v.) Пока к > 1, выполнять шаги с 5-го по 8-й. 5. (Установка параметров разбиения.) Установить k равным k − 1, s равным qk, t равным rk и р равным qk−1 + qk. 6. (Разбиение верхнего элемента стека С.) Длинное число [qk + qk+1, u] на вершине С следует рассматривать как t + 1 чисел длиной s битов каждое. Разбить [qk + qk+1, u] на длинные числа [s, Ut], [s, Ut−1], …, [s, U1], [s, U0]. Эти t + 1 чисел являются коэффициентами многочлена степени t, который следует вычислить в точках 0,1, …, 2t − 1, 2t no правилу Горнера. Для i = 0, 1, …, 2t − 1, 2t вычислить [р, Xi] по формуле (…([s, Ut]i + [s, Ut−1])i+ … + [s, U1])i + [s, U0] и сразу поместить [р, Xi] в стек U. Для выполнения умножений можно использовать подпрограмму умножения длинных чисел на короткие; никакой промежуточный или окончательный результат не потребует более p битов. Удалить [qk + qk+1, u] из стека С. 7. (Продолжение разбиения.) Выполнить над числом [m, v], находящимся сейчас на вершине стека С, ту же последовательность действий, что на шаге 6; полученные числа [p, Y0], …, [p, Y2t] поместить в стек V в порядке получения. Не забудьте удалить вершину стека С. 8. (Заполнение заново стека С.) Попеременно удалять (2t раз) вершины стеков V и U и помещать эти значения в стек С. В результате значения, вычисленные на шагах 6 и 7, будут помещены, чередуясь, в стек С в обратном порядке. После выполнения этого перемешивания верхняя часть стека С, рассматриваемая снизу вверх, будет иметь вид [р, Y2t], [p, X2t], …, [р, Y0], [p, Х0], на вершине будет [р, Х0]. Поместить в управляющий стек один код операции интерполировать и 2t кодов операции сохранять и вернуться к шагу 4. 9. (Подготовка к интерполяции.) Присвоить к значение 0. Выбрать два верхних элемента стека С и поместить их в обычные переменные и и v. Оба числа и и v будут состоять из 32 битов. Используя некоторую другую подпрограмму умножения, вычислить [64, w] = [64, uv]. Это умножение можно выполнить аппаратно или с помощью подпрограммы, как вы найдете нужным. 10. (Интерполяция при необходимости.) Выбрать вершину управляющего стека в переменную А. Если значение А есть интерполировать, то выполнить шаги с 11-го по 16-й, в противном случае перейти к шагу 17, 11. (Организация интерполяции.) Поместить [m, w] в стек W (это может быть значение, полученное на шаге 9 или 16). Присвоить s значение qk, t — значение rk, р — значение qk−1 + qk. Обозначим верхнюю часть стека W, рассматриваемую снизу вверх, как [2р, Z0], [2p, Z1], …, [2р, Z2t−1], [2p, Z2t], последнее из этих значений — на вершине стека. 12. (Внешний цикл деления Z.) Выполнять шаг 13 для i = 1, 2, …, 2t. 13. (Внутренний цикл деления Z.) Присвоить [2p, Zj] значение ([2р, Zj] − [2р, Zj−1])/i для j=2t, 2t − 1, …, i + 1, i. Все разности будут положительными, а все деления выполняются нацело, т. е. без остатка. 14. (Внешний цикл умножения Z.) Выполнять шаг 15 для i = 2t − 1, 2t − 2, …, 2, 1. 15. (Внутренний цикл умножения Z.) Заменить [2р, Zj] на [2p, Zj] − i[2p, Zj+1] для j = i, i + 1, …, 2t − 2, 2t − 1. Все разности будут положительными, и все результаты поместятся в 2р битов. 16. (Образование нового w и начало нового цикла.) Присвоить значение многочлена (… ([2р, Z2t]2s + [2p, Z2t−1]2s + … + [2p, Zi]2s + [2p, Z0] переменной [2(qk + qk+1), w]. Этот шаг можно выполнять, используя только сдвиги и сложения длинных чисел. Заметьте, что используется та же переменная [m, w], что и на шаге 9. Удалить [2р, Z2t], …, [2p, Z0] из стека W. Присвоить k значение k + 1 и вернуться к шагу 10. 17. (Проверка окончания.) Если А имеет значение стоп, то в переменной [m, w], уже вычисленной на шаге 9 или 16, находится результат алгоритма. В этом случае окончить работу. 18. (Сохранение значения.) Значением А должен быть код сохранить (если это не так, завершить алгоритм по ошибке). Присвоить k значение k + 1 и поместить [qk + qk−1, w] в стек W. Это значение w, только что вычисленное на шаге 9 или 16. Теперь вернуться к шагу 3. жүктеу/скачать 0,69 Mb. Достарыңызбен бөлісу:
|