Разработка комплексного алгоритма умножения
Design of complex multiplication algorithm

УДК 519.688

В данной работе предложен комплексный рекурсивный алгоритм умножения длинных целых чисел, сочетающий асимптотически быстрый метод Карацубы и метод сдвигов и сложений на нижних уровнях рекурсии. Приведены варианты реализации алгоритма и результаты экспериментального исследования эффективности.

In this article we propose a complex 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.

Авторы:

Куляс Михаил Евгеньевич

ФГБОУ ВПО «Национальный исследовательский университет «МЭИ», Москва
Аспирант кафедры «Математического Моделирования»

Список цитируемой литературы:

  • Кнут Д., Искусство программирования, т. 2, Получисленные алгоритмы // М.: Вильямс, 2004.
  • Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ДАН СССР том 145 № 2, с. 293–294, 1962.
  • Тоом А. Л. О сложности схемы из функциональных элементов, реализующей умножение целых чисел // ДАН СССР, т. 150, с. 496–498, 1963.
  • Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing, Vol. 7, P. 271–282, 1971.
  • Fürer M. Faster integer multiplication // Proc. 39th ACM STOC Conf. P. 57–66, 2007.
  • Гашков С. Б. Занимательная компьютерная арифметика. Быстрые алгоритмы операций с числами и многочленами // М.: УРСС, Либроком, 2012.
  • Фролов А. Б., Винников А. М. О машинном синтезе некоторых линейных программ // Программная инженерия № 6, с. 24–30, 2011.

Последние новости

Случайный материал

  • В статье рассматриваются вопросы эффективной организации мониторинга процессов оказания электронных услуг. В качестве инструмента проведения мониторинга предлагается использовать автоматизированную систему, обеспечивающую адаптивную организацию процессов сбора, хранения и обработки данных. Сформулированы системные и технологические задачи организации мониторинга, раскрыты их сущность и принципы решения.
    Фролов Алексей Иванович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
  • В данной статье рассматриваются подходы к созданию подсистемы стабилизации температуры в барокамере экспериментальной системы контроля качества приборов. Данная подсистема позволяет управлять величиной тока, подаваемого на термоэлектрический модуль, для поддержания воздушной среды управляемого объекта – барокамеры в пределах заданной величины.
    Демина Юлия Александровна, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Вереницын Андрей Игоревич, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Демина Елена Григорьевна, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
  • В данной статье рассматривается актуальность применения свободного программного обеспечения для оказания электронных услуг населению, а также выявляются проблемы при его внедрении и сопровождении.
    Стычук Алексей Александрович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел
    Постников Максим Владимирович, ФГБОУ ВПО «Госуниверситет – УНПК», г. Орел