Структуры данных: стек и список

Задания для практических занятий по теме
«Вычислительная сложность алгоритмов»
часть 2

Быстрое умножение длинных целых чисел

Рассмотрим процедуру перемножения двух N-значных целых чисел. Для этого можно применить обычное перемножение "столбиком", сложность которого легко оценивается и равна N².

Однако, рассмотрим другой способ, который назовем быстрое перемножение. Для простоты будем считать, что N - это степень двойки, т.е. N=2ⁿ. Пусть исходные множители X и Y имеют вид X=AB и Y=CD, где A, B, C и D являются уже N/2-значными числами (другими словами, это левые и правые половинки исходных чисел). Итак, произведение X×Y можно переписать как (A×10^N/2+B)(C×10^N/2+D). Если теперь раскрыть скобки, то получится A×C×10^N+(AD+BC)×10^N/2+B×D. В таком виде вычисление произведения X×Y сводится к вычислению четырех произведений, но с меньшей разрядностью множителей. Легко показать, что вычислительная сложность при этом останется той же, т.е. N².

Главная идея быстрого умножения состоит в модификации выражения A×C×10^N+(A×D+B×C)×10^N/2+B×D таким образом, чтобы уменьшить количество операций умножения: A×C×10^N+(AD+BC)×10^N/2+B×D = A×C×10^N+(A-B)×(D-C)×10^N/2+B×D+(A×C+B×D)×10^N/2. Видно, что теперь необходимо найти лишь три произведения N/2-значных чисел.

Задание.

1) Реализовать алгоритм сложения двух длинных целых чисел.
2) Реализовать алгоритм умножения двух длинных целых чисел.
3) Реализовать нерекурсивный алгоритм быстрого умножения.
    а) в программе должен присутствовать механизм контроля используемой памяти (пиковый расход).
    б) сделать модификацию алгоритма для перемножения чисел, разрядность которых не является степенью двойки.
4) Реализовать рекурсивный алгоритм быстрого умножения.
5) Написать тестовую программу для сравнения двух реализаций.
6) Написать тестовые программы для демонстрации правильности работы программ.
    а) входные данные хранятся в файле mult.txt: в первой строке разрядность чисел, во второй и третьей - сами множители.
    б) входные данные должны дублироваться на экране, результат перемножения тоже выводить на экран.
7) Разработать набор тестов для проверки правильности (включает не менее 10 тестовых случаев). Реализовать режим пакетной прогонки разработанных тестов.