Журнал "Программная инженерия"
Теоретический и прикладной научно-технический журнал
ISSN 2220-3397

Номер 2 2017 год

DOI: 10.17587/prin.8.66-75
УДК: 519.688
О синтезе программ умножения длинных целых чисел
М. Е. Куляс, аспирант, e-mail: KuliasMY@mpei.ru, ФГБОУ ВО НИУ Московский энергетический институт

Предложены два варианта комбинированных рекурсивных алгоритмов умножения длинных целых чисел, сочетающих асимптотически быстрый метод Карацубы, а также метод сдвигов и сложений на нижних уровнях рекурсии. Представлены варианты рекурсивной и последовательной (линейной) программной реализации предложенных алгоритмов, результаты экспериментального исследования их эффективности. Даны оценки объема требуемой памяти.

Ключевые слова: умножение длинных чисел, метод Карацубы, последовательная программа, рекурсия, сложность вычислений
Стр. 66–75
Работа подготовлена при финансовой поддержке РФФИ, проект №14-01-00671-А.