SOFTWARE IMPLEMENTATION OF KARATSUBA’S MULTIPLICATION ALGORITHM
Keywords:
multiplication of long integers, Karatsuba’s algorithm, recursion, linear program, multithreading programming
Abstract
In this article we propose a combined recursive multiplication algorithm for long integers, which combines asymptotically fast Karatsuba’s method and method of shifts and additions at lower levels of recursion. We present variants of implementation with comparison of their efficiency.
References
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.
Published
2018-11-30
Issue
Section
Informatics, computer engineering and control (05.13.00)
