Эта публикация цитируется в 1 статье

Часть 3. Математические модели

Быстрые алгоритмы умножения и деления натуральных чисел с помощью клеточных автоматов с локаторами

Э. Э. Гасанов^a, Б. Ф. Хайбуллин<sup>b

a</sup> Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
^b ООО "Elius"

Аннотация: Для умножения и деления $ n $-значных натуральных чисел известны алгоритмы со сложностью порядка $ n^{\log_2 3} $ и даже порядка $ n^{\log n} $. В данной работе предложен алгоритм умножения $n$-значных натуральных чисел за $ 2n + 2 $ такта. Здесь под значностью числа $ a $ понимается число $ ]\log_2 a[ $. Для деления натуральных чисел с остатком предложен алгоритм с временем работы $ 3n + 8 $ тактов, где $n$ — значность частного. Предложенные алгоритмы в качестве вычислителей используются двумерные клеточные автоматы с локаторами.

Ключевые слова: умножение натуральных чисел, деление натуральных чисел, клеточные автоматы с локаторами