Использование двоичной системы счисления и длинной арифметики в задаче оптимизации теста Люка – Лемера

Гончаренко Валерий Евстафиевич
Кандидат технических наук, доцент Ивановского филиала РЭУ им. Г.В. Плеханова, г. Иваново.
 

Использование двоичной системы счисления и длинной арифметики в задаче оптимизации теста Люка – Лемера

 
Существует ряд задач, решение которых программным путём невозможно с использованием только стандартных типов данных и функций. В статье рассматривается одна из таких задач – это тест Люка – Лемера, который доказывает принадлежность чисел Мерсенна к простым или составным числам. Современные исследования проводятся со сверхбольшими числами Мерсенна, в записи которых содержатся миллионы десятичных цифр. Хранить и обрабатывать такие числа в памяти ЭВМ можно лишь по алгоритмам длинной арифметики, что требует больших затрат процессорного времени. Представление этих чисел в двоичной системе счисления позволило существенно снизить вычислительную сложность обработки этих чисел и реализовать оптимизированный алгоритм теста в программе на языке С++.
 

Продолжение…

Оставьте комментарий