RU
Fast algorithms for multiplication and division of natural numbers using cellular automata with locators
Gasanov E. E., Khaybullin B. F.
Published: 2024, vol. 28, issue 3, pp. 103–130
Abstract
For multiplication and division of \(n\)-digit natural numbers, algo-rithms with complexity of order \(n^{\log_2 3}\) and even order \(n^{\log n}\) are known. In this paper, an algorithm for multiplying \(n\)-digit natural numbers in \(2n + 2\) cycles is proposed. Here, the digit of number a is understood as the number \(]\log_2 a[\). For division of natural numbers with remainder, an algorithm with a running time of \(3n + 8\) cycles is proposed, where n is the digit of the quotient. The proposed algorithms use two-dimensional cellular automata with locators as calculators.
Keywords: multiplication of natural numbers, division of natural numbers, cellular automata with locators.
BibTeX
@article{IS-Gasanov-Khaybullin2024,
author = {Gasanov, Elyar Eldarovich and Khaybullin, Bakir Faridovich},
title = {{Fast algorithms for multiplication and division of natural numbers using cellular automata with locators}},
journal = {Intelligent Systems. Theory and Applications},
year = {2024},
volume = {28},
number = {3},
pages = {103--130},
}
AMSBIB
\Bibitem{IS-Gasanov-Khaybullin2024}
\by E.\,E.~Gasanov, B.\,F.~Khaybullin
\paper Fast algorithms for multiplication and division of natural numbers using cellular automata with locators
\jour Intelligent Systems. Theory and Applications
\yr 2024
\vol 28
\issue 3
\pages 103--130
\lang In Russian