DOI: 10.17587/prin.8.66-75

УДК: 519.688

О синтезе программ умножения длинных целых чисел

М. Е. Куляс, аспирант, e-mail: KuliasMY@mpei.ru, ФГБОУ ВО НИУ Московский энергетический институт

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

Ключевые слова: умножение длинных чисел, метод Карацубы, последовательная программа, рекурсия, сложность вычислений

Стр. 66–75

Работа подготовлена при финансовой поддержке РФФИ, проект №14-01-00671-А.

Ссылка для цитирования:
Kulyas M. E. Synthesis of Computer Programs for Long Integers Multiplication, Programmnaya Ingeneria, 2017, vol. 8, no. 2, pp. 66—75.