EN
Быстрые алгоритмы умножения и деления натуральных чисел с помощью клеточных автоматов с локаторами
Гасанов Э. Э., Хайбуллин Б. Ф.
Опубликована: 2024 год, том 28, выпуск 3, С. 103–130
Аннотация
Для умножения и деления \(n\)-значных натуральных чисел известны алгоритмы со сложностью порядка \(n^{\log_2 3}\) и даже порядка \(n^{\log n}\). В данной работе предложен алгоритм умножения \(n\)-значных натуральных чисел за \(2n + 2\) такта. Здесь под значностью числа a понимается число \(]\log_2 a[\). Для деления натуральных чисел с остатком предложен алгоритм с временем работы \(3n + 8\) тактов, где \(n\) — значность частного. Предложенные алгоритмы в качестве вычислителей используются двумерные клеточные автоматы с локаторами.
Ключевые слова: умножение натуральных чисел, деление натуральных чисел, клеточные автоматы с локаторами.
BibTeX
@article{IS-Gasanov-Khaybullin2024,
author = {Гасанов, Эльяр Эльдарович and Хайбуллин, Бакир Фаридович},
title = {{Быстрые алгоритмы умножения и деления натуральных чисел с помощью клеточных автоматов с локаторами}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2024},
volume = {28},
number = {3},
pages = {103--130},
}
AMSBIB
\RBibitem{IS-Gasanov-Khaybullin2024}
\by Э.\,Э.~Гасанов, Б.\,Ф.~Хайбуллин
\paper Быстрые алгоритмы умножения и деления натуральных чисел с помощью клеточных автоматов с локаторами
\jour Интеллектуальные системы. Теория и приложения
\yr 2024
\vol 28
\issue 3
\pages 103--130