О программной реализации алгоритма умножения Карацубы
Ключевые слова:
умножение длинных чисел, алгоритм Карацубы, рекурсия, линейная программа, многопоточное программирование
Аннотация
Предложен комбинированный рекурсивный алгоритм умножения длинных целых чисел, сочетающий асимптотически быстрый метод Карацубы и метод сдвигов и сложений на нижних уровнях рекурсии. Приведены варианты реализации алгоритма и результаты экспериментального исследования его эффективности.
Литература
1. Кнут Д. Искусство программирования. Получисленные алгоритмы. Т. 2. М.: Вильямс, 2004.
2. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962. № 2. Т. 145. С. 293 — 294.
3. Гашков С.Б. Занимательная компьютерная арифметика. Быстрые алгоритмы операций с числами и многочленами. М.: УРСС, Либроком, 2012.
4. Карацуба А.А. Сложность вычислений // Труды математического института имени В. А. Стеклова. 1995. № 211. С. 186 — 202.
5. Фролов А.Б., Винников А.М. О машинном синтезе некоторых линейных программ // Программная инженерия. 2011. № 6. С. 24 — 30.
6. Эхтер Ш. Многоядерное программирование. СПб.: Питер, 2010.
2. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962. № 2. Т. 145. С. 293 — 294.
3. Гашков С.Б. Занимательная компьютерная арифметика. Быстрые алгоритмы операций с числами и многочленами. М.: УРСС, Либроком, 2012.
4. Карацуба А.А. Сложность вычислений // Труды математического института имени В. А. Стеклова. 1995. № 211. С. 186 — 202.
5. Фролов А.Б., Винников А.М. О машинном синтезе некоторых линейных программ // Программная инженерия. 2011. № 6. С. 24 — 30.
6. Эхтер Ш. Многоядерное программирование. СПб.: Питер, 2010.
Опубликован
2018-11-30
Выпуск
Раздел
Информатика, вычислительная техника и управление (05.13.00)
