ISSN 2305-9052 · EISSN 2410-7034
Языки: ru · en

ВЕСТНИК ЮЖНО-УРАЛЬСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА. СЕРИЯ: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И ИНФОРМАТИКА

РАСПРЕДЕЛЕНИЕ КВАДРАТОВ И ПРОВЕРКА ГИПОТЕЗ В НЕЧЕТНЫХ РАЗБИЕНИЯХ ЧИСЕЛ (2024)

В статье рассматриваются разбиения натурального числа n, части которого различны, нечетны и их произведение не является квадратом. Такие разбиения применимы для определения ранга группы центральных единиц целочисленного группового кольца знакопеременной группы. Количество разбиений растет экспоненциально, следовательно, задача перебора является вычислительно затратной. В статье предложен параллельный алгоритм в общей памяти для нахождения количества разбиений числа n с дополнительными условиями. Алгоритм основан на концепции распараллеливания по данным и использовании вложенного параллелизма. Выделяется множество длин K разбиения числа n, элементы которого обрабатываются параллельно. Во время обработки длины k разбиения числа n выделяется множество уровней L, рассмотрение которого также выполняется параллельно. Приемлемые значения ускорения и параллельной эффективности предложенного алгоритма получаются при использовании двух нитей на параллельный регион по длинам и двух - по уровням. Таким образом, ускорение при разных n превышает 2.1, а параллельная эффективность не опускается ниже 50 %. Полученные результаты использованы для проверки гипотез Каргаполова и анализа распределения значений нечетных разбиений на некоторых диапазонах. Предложен алгоритм поиска оптимального коэффициента c. С помощью этого алгоритма получена асимптотическая формула количества разбиения числа n, в котором части различны и нечетны, а их произведение является квадратом. Эта формула основана на экспериментальных данных и сформулирована как гипотеза.

Тип: Статья
Автор (ы): Самойлов A. A.
Ключевые фразы: РАЗБИЕНИЕ НАТУРАЛЬНОГО ЧИСЛА, асимптотическая формула, ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ, OPENMP

Идентификаторы и классификаторы

УДК
004.021. Алгоритмы
519.116. Комбинаторная теория разбиений натуральных чисел
eLIBRARY ID
65312690
Текстовый фрагмент статьи