Исследование алгоритмов умножения для больших чисел

  • 22 мая 2014 г.
  • 990 Слова
Давыденко Д.О.
Смакаев А.В.
Чурилов А.С.


Научный руководитель: канд. физ.-мат. наук, доц.
Сергиенко Е.Н.
Белгородский государственный технологическийуниверситет им. В.Г.Шухова


ИССЛЕДОВАНИЕ АЛГОРИТМОВ УМНОЖЕНИЯ БОЛЬШИХ ЧИСЕЛ


Во многих научных расчетах оперируют в основном числами, разрядность которых превышает размер машинного словаданной вычислительной машины. Производить действия с такими числами стандартными алгоритмами очень затруднительно, а порой и совсем невозможно. Чтобы сократить время вычислений были придуманы быстрыеалгоритмы для осуществления операций большими числами.
Быстрые алгоритмы — область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью сиспользованием как можно меньшего числа битовых операций.
Сложность умножения [pic] определяется как количество битовых операций, достаточное для вычисления произведения двух [pic]– значных чисел посредствомданного алгоритма.


Алгоритм Карацубы-Оффмана
Рассмотрим идею быстрого алгоритма умножения, названного в честь советского и российского математика Анатолия Алексеевича Карацубы, известного каксоздателя первого быстрого метода умножения больших чисел. Сложность умножения данного алгоритма [pic].
Основная идея алгоритма Карацубы заключается в формулах, которые позволяют вычислятьпроизведения двух больших чисел [pic] и [pic], используя три умножения меньших чисел.


[pic]
[pic]


Действительно, пусть
[pic]
[pic]


Таким образом,

[pic]Описание алгоритма
Вход: целые числа [pic]
Выход: целое число [pic]


Шаг 1. Если числа [pic] представляются с помощью чисел длинной меньше [pic] цифр(обменная точкаалгоритма), то ищется [pic] произведение классическим способом.
Шаг 2. Разбить каждое из сомножителей на две части, старшую и младшую :
[pic]...