Параллельный алгоритм распределения квадратов в произведениях разбиений натуральных чисел

Базаров В.А.

Параллельный алгоритм распределения квадратов в произведениях разбиений натуральных чисел

02.03.01 Математика и компьютерные науки

Математика

Дипломы

Вуз: Белгородский государственный университет - национальный исследовательский университет (НИУ «БелГУ»)

ID: 5b8877ef7966e1073081b26c

UUID: f0c7b9c0-8ed6-0136-b12f-525400005860

Язык: Русский

Опубликовано: около 6 лет назад

Просмотры: 8

Базаров В.А.

Источник: Федеральное государственное автономное образовательное учреждение высшего образования «Белгородский государственный национальный исследовательский университет»

Комментировать 0

Рецензировать 0

Скачать - 1,3 МБ

Поделиться работой

ФЕДЕРАЛЬНОЕ ГОСУДАРСТ ВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» (НИУ «БелГУ») ИНСТИТУТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ И ЕСТЕСТВЕННЫХ НАУК КАФЕДРА МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННЫХ СИСТЕМ ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РАСПРЕДЕЛЕНИЯ КВАДРАТОВ В ПРОИЗВЕДЕНИЯХ РАЗБИЕНИЙ НАТУРАЛЬНЫХ ЧИСЕЛ Выпускная квалификационная работа обучающегося по направлению подготовки 010200.62 «Математика и компьютерные науки» очной формы обучения группы 07001303 Базарова Владимира Алексеевича Научный руководитель: к.т.н. доцент Михелев Владимир Михайлович БЕЛГОРОД, 2017

СОДЕРЖАНИЕ ВВЕДЕНИЕ……………………………………………………………..……....…3 ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ…………………………………..…...…6 1.1. Анализ предметной области и обзор существующих алгоритмов…..…....6 1.2. Разработка основной части последовательного алгоритма……..……...….9 1.3. Разработка функции проверки квадратов………………………….….…..16 ГЛАВА 2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ …………………………………..…23 2.1. Разработка параллельного алгоритма………………………………….…..23 2.2. Описание программы………………………………………………….……26 ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ………………………………...34 3.1. Тестирование программы и результаты её работы ………………………34 3.2. Расчёт ускорения и эффективности.…………...………………….……….36 3.3. Анализ полученных результатов…………………………………………..38 ЗАКЛЮЧЕНИЕ……………………………………………………………….…48 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………...….50 ПРИЛОЖЕНИЕ 1……………………………………………………………..…51

3 ВВЕДЕНИЕ Разбиением натурального числа n называется представление n в виде суммы положительных целых чисел – частей или элементов разбиения. При этом их порядок, в отличие от композиций, не учитывается: два разбиения, отличающиеся только порядком слагаемых, являются равными. Разбиение принято записывать в порядке невозрастания его частей. Таким образом, разбиение с элементами a1 ≥ a2 ≥ … ≥ ak записывается в каноническом виде как {a1, a2, … , ak }. Общее количество разбиений натурального числа n обозначается p(n). Все возможные разбиения небольших n легко найти простым перебором. Например, для n = 6 имеем: {6}, {5, 1}, {4, 2}, {4, 1, 1}, {3, 3}, {3, 2, 1}, {3, 1, 1, 1}, {2, 2, 2}, {2, 2, 1, 1}, {2, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}. Таким образом, p(6) = 11. Однако при возрастании n перебор вручную становится неэффективным: получение p(24) = 1575 или p(45) = 89134 разбиений без помощи компьютера требует расхода значительного количества времени и усилий. Вместе с тем задачи, связанные с разбиениями, регулярно встречаются в различных областях математики, в первую очередь в комбинаторике и теории чисел. Одной из актуальных задач, связанных с разбиениями чисел, является вычисление рангов групп центральных единиц целочисленных групповых колец знакопеременных групп, используя разбиения числа. Известно [6], что ранг группы центральных единиц целочисленного группового кольца знакопеременной группы An равен количеству разбиений числа n, удовлетворяющих следующим свойствам: 1) Все части разбиения нечётны; 2) Части разбиения попарно различны; 3) (n – k) делится на 4, где k – количество частей разбиения;

4 4) Произведение всех частей разбиения не является квадратом натурального числа. Введём следующие функции для натурального аргумента n:  r (n) – количество разбиений числа n, удовлетворяющих условиям 1) – 2);  r4 (n) – количество разбиений числа n, удовлетворяющих условиям 1) – 3);  rank (n) – количество разбиений числа n, удовлетворяющих условиям 1) – 4);  sqrs (n) – количество разбиений числа n, удовлетворяющих условиям 1) – 3), но не удовлетворяющих условию 4). На данный момент существуют алгоритмы для нахождения значений функции rank (n), но пока нет такого, который выполняет это действие за приемлемое время. Вместе с тем, очевидно, что rank (n) = r4 (n) – sqrs (n), то есть для расчёта рангов достаточно уметь находить значений функций r4 (n) и sqrs (n). В данной работе будет решена задача расчёта этих функций, причём особое внимание будет уделяться функции sqrs (n) в силу того, что условие 4 самое сложное с практической точки зрения. Основной целью данной работы является разработка параллельного алгоритма для вычисления значений функции sqrs (n), то есть нахождение количества разбиений натурального числа n из различных нечётных натуральных слагаемых, таких, что их произведение является квадратом натурального числа, а разность между их количеством и n делится на 4. Для достижения данной цели необходимо решить следующие задачи:  Изучить предметную область;  Исследовать существующие алгоритмы;  Разработать эффективный алгоритм вычисления значений функции, определяющей количество разбиений натурального числа, состоящего из

5 различных нечётных частей, количество которых даёт тот же остаток при делении на 4, что и их сумма, а произведение является точным квадратом;  Распараллелить созданный алгоритм;  На основе данного алгоритма разработать программу для определения значений функции;  Вычислить значения функции для достаточно малых аргументов;  Проанализировать полученные результаты и понять характер функции. Работа содержит введение, три главы, заключение и список использованных источников. В первой части происходит обзор предметной области и разбираются теоретические основы для достижения поставленной цели, а именно разрабатывается эффективный последовательный алгоритм и с обоснованием правильности его работы. Во второй части происходит распараллеливание данного алгоритма и описание программы, которая создаётся на его основе. В третьей части производится тестирование полученной программы, фиксируются результаты её работы для некоторого множества входных данных и производится анализ полученных результатов с целью понять характер поведения функции. В заключении подводятся итоги всей работы. Объём работы составляет 50 страниц, объём использованной литературы – 10 источников. Работа содержит 7 таблиц, 23 рисунка, 4 формулы и 3 листинга.

6 ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 1.1. Анализ предметной области и обзор существующих алгоритмов Разбиение натурального числа – это его запись в виде суммы натуральных слагаемых, которые называются его частями или элементами [1]. Разбиения, совпадающие с точностью до порядка слагаемых, считаются одинаковыми. Следовательно, можно считать, что части разбиения следуют в порядке невозрастания. Существуют различные способы точного или приблизительного вычисления значений функции p (n). Так, в 1740 году Леонард Эйлер открыл формулу производящей функции числа разбиений: n Для вычисления k = знаменателя ) правой (1.1) части используется Пентагональная теорема Эйлера [5]: (1.2) Таким образом, через эти формулы можно находить значения функции p (n) путём деления формальных степенных рядов. Рассмотрим некоторые точные значения этой функции. Они приведены в таблице 1.1. Таблица 1. 1 Точные значения функции p (n) для некоторых n n p (n) 1 1 2 2

7 Таблица 1.1. Продолжение n p (n) 4 5 8 22 16 231 32 8 349 50 204 226 100 190 569 292 1000 24 061 467 864 032 622 473 692 149 727 991 Для оценки количества разбиений используется формула, полученная Харди и Рамануджаном [10]: (1.3) Так, p (1000) ≈ 2.44 * 1031. Кроме того, из этой формулы следует, что функция p (n) растёт экспоненциально. Таким образом, нахождение самого количества разбиений не представляет проблемы. Основная сложность возникает при переборе всех разбиений числа n, который в силу экспоненциальности функции p (n) уже для относительно небольших n становится слишком ресурсоёмким. Для полного перебора всех разбиений используется алгоритм Липского [2]. Он изображён на рис. 1.1.

8 Рис. 1.1. Алгоритм Липского для разбиений натурального числа Предложенный им алгоритм позволяет получить последовательность разбиений натурального числа N в порядке, обратном лексикографическому. При этом разбиение представлено переменными S[1], … , S[d], содержащими попарно различные части разбиения (S[1] > … > S[d]), а также переменными R[1], … , R[d]: R[i] равно количеству раз, которое i-е слагаемое появляется в разбиении, и R[i] ≠ 0. Очевидным недостатком алгоритма Липского для решения задачи о нахождении значений функции sqrs (n) является перебор слишком большого числа заведомо неподходящих разбиений. Проиллюстрируем сказанное рассмотрением разбиений для числа 25, которые указаны в таблице 1.2.

9 Таблица 1.2 Разбиения числа 25 # r (n) r4 (n) sqrs (n) 1 {25} {25} {25} 2 {21, 3, 1} {9, 7, 5, 3, 1} – 3 {19, 5, 1} – – 4 {17, 7, 1} – – 5 {17, 5, 3} – – 6 {15, 9, 1} – – 7 {15, 7, 3} – – 8 {13, 11, 1} – – 9 {13, 9, 3} – – 10 {13, 7, 5} – – 11 {9, 7, 5, 3, 1} – – Известно, что p (25) = 1958. Таким образом, из 1958 разбиений числа 25 нашлось всего 11, удовлетворяющих условиям 1-2, два, удовлетворяющих условиям 1-3, и одно, удовлетворяющее условиям 1-3, но не удовлетворяющее условию 4. Стало быть, время работы алгоритма уменьшится на несколько порядков, если перебирать не все разбиения числа n, а только те, которые удовлетворяют условиям 1-3. Следовательно, необходимо разработать алгоритм, который будет формировать все разбиения, удовлетворяющие условиям 1-3, и функцию, которая для каждого разбиения определяет, удовлетворяет ли она условию 4. Также будет объявлена переменная для подсчёта количества благоприятных разбиений, которая, в случае выполнения необходимых условий, будет увеличиваться на 1. Разработка этого алгоритма рассматривается далее.

10 1.2. Разработка основной части последовательного алгоритма Как было оговорено ранее, алгоритм для получения значений функции sqrs (N) будет состоять из двух частей: алгоритма, перебирающего все разбиения, удовлетворяющие условиям 1-3, и функции, которая для каждого разбиения проверяет выполняемость условия 4. Множество всех возможных разбиений натурального числа N на k различных нечётных натуральных слагаемых обозначим через A (N, k). Сами разбиения будем обозначать строчными латинскими буквами, например, a (N, k). Поскольку для задания такого разбиения достаточно указать лишь все его элементы в порядке убывания, будем считать, что разбиение a (N, k) равно {a1, a2, … , ak }, причём ai > aj при всех 1 ≤ i < j ≤ N. Введём операцию сравнения для разбиений одного числа на одинаковое количество слагаемых. Определение 1. Разбиение a (N, k) больше разбиения b (N, k) (обозначается a (N, k) > b (N, k)), если существует такое 1 ≤ i < k, что ai > bi, а aj = bj при всех j = 1, 2, … , i – 1. Аналогично, a (N, k) < b (N, k), если существует такое 1 ≤ i < k, что ai < bi, а aj = bj при всех j = 1, 2, … , i – 1. Если ai = bi при всех i = 1, 2, … , k, то разбиения a (N, k) и b (N, k) являются равными. Нетрудно убедиться, что операция сравнения разбиений транзитивна, то есть для любых трёх попарно различных разбиений a (N, k), b (N, k) и c (N, k) из a (N, k) > b (N, k) и b (N, k) > c (N, k) следует a (N, k) > c (N, k). (Это следует непосредственно из определения сравнения разбиений). Таким образом, все разбиения множества A (N, k) могут быть упорядочены по возрастанию. Говоря формально, примем следующие определения. Определение 2. Разбиение a (N, k) называется минимальным, если любое другое разбиение b (N, k) больше него. Аналогично, если a (N, k) > b

11 (N, k) для любого b (N, k) ≠ a (N, k), то разбиение a (N, k) называется максимальным. Определение 3. Разбиение b (N, k) назовём следующим за разбиением a (N, k) (или для разбиения a (N, k)), если b (N, k) > a (N, k) и не существует разбиения c (N, k), такого, что b (N, k) > c (N, k) > a (N, k). Таким образом, получаем план алгоритма для нахождения и записи всех разбиений множества A (N, k). Он представлен на рис. 1.2. Рис. 1.2. План алгоритма для записи всех разбиений множества A (N, k) Как видно из приведённого плана, для того, чтобы использовать алгоритм, необходимо уметь получать минимальное разбиение при заданных N и k, а также находить следующее разбиение для заданного a (N, k). Нетрудно видеть, что в любом разбиении в силу нечётности, различности и убывания его элементов будет выполняться неравенство ai ≥ 2(k – i) + 1 для всех i = 1, 2, … , k. Поскольку a1 + a2 + … + ak = N, суммируя неравенства по всем i, получаем N ≥ k2. Итак, если N < k2, то разбиений, удовлетворяющих условию, не существует. Обозначим неполное частное и остаток числа (N – k2)/2 при делении на k через q и r соответственно, то есть (N – k2)/2 = qk + r, где числа q, r – целые неотрицательные и r < k. Докажем, что верна следующая лемма.

12 Лемма 1. Минимальное разбиение a (N, k) определяется следующим образом: ai = 2(k – i) + 1 + 2q для i = r + 1, r + 2, … , k и ai = 2(k – i) + 1 + 2(q + 1) для i = 1, 2, … , r. Доказательство. Вначале покажем, что данное разбиение удовлетворяет условию. Очевидно, все его элементы нечётны и ai > aj при i < j. Сумма всех элементов равна +1+2 ) = =1 (2 + +1+2 ) + 2r = =1 (2 +1) + 2qk + 2r = k2 + 2(qk + r) = k2 + 2(N – k2)/2 = N. Итак, данное разбиение действительно входит в множество A (N, k). Теперь предположим, что существует разбиение b (N, k) < a (N, k). Из этого по определению следует, что существует такое 1 ≤ i < k, что bi < ai, а aj = bj при всех j = 1, 2, … , i – 1. Это значит, что j = j j < j. Однако = N, то есть найдётся j > i такое, что bj > aj. Далее, поскольку все элементы разбиения нечётны, то bj ≥ aj + 2 и bi ≤ ai – 2. Отсюда ai ≥ bi + 2 и –aj ≥ –bj + 2. Стало быть, ai – aj ≥ bi – bj + 4. С другой стороны, из определения разбиения a (N, k) следует, что ai – aj равно 2(j – i) или 2(j – i) + 2. Значит, bi – bj + 4 ≤ ai – aj ≤ 2(j – i) + 2, то есть bi – bj ≤ 2(j – i) – 2. Противоречие. Значит, предположение неверно и лемма доказана. Таким образом, используя эту лемму, несложно составить алгоритм для нахождения минимального разбиения числа N на k различных нечётных слагаемых. Определение 4. Назовём элемент ai уменьшаемым, если ai > 1 при i = k или ai > ai+1 + 2 при i ≠ k. Если элемент ai уменьшаемый, а aj при любом j > i не является уменьшаемым, то такой элемент ai назовём правым уменьшаемым. Очевидно, правый уменьшаемый элемент существует в любом разбиении, в котором есть хотя бы один уменьшаемый элемент. В свою очередь, из индукции следует, что при k ≥ 2 уменьшаемый элемент

13 существует в любом разбиении, кроме разбиения, для которого ai = 2*(k – i) + 1 при всех i = 1, 2, … , k, то есть единственного разбиения из множества A (k2, k). Однако в таком множестве это разбиение, в силу своей единственности, является также и максимальным. При k = 1 разбиение также единственно и, стало быть, также является максимальным. Определение 5. Назовём элемент ai увеличиваемым, если ai < N – (k – 1)2 при i = 1 или ai < ai–1 – 2 при i ≠ 1. Увеличиваемый элемент ai назовём правым увеличиваемым, если выполняются два свойства; 1) i < j, где aj – правый уменьшаемый элемент; 2) Не существует такого натурального l, что i < l < j и al также является увеличиваемым элементом. Аналогично, легко заметить, что для любого разбиения, не являющегося максимальным, существует ровно один правый уменьшаемый элемент. Лемма 2. Пусть a (N, k) – разбиение, не являющееся максимальным. Разбиение b (N, k), следующее за разбиением a (N, k), задаётся следующими условиями: 1) bi = ai при всех i = 1, 2, … , l – 1, где al – правый увеличиваемый элемент; 2) bl = al + 2; 3) Разбиение {bl+1, bl+2, … , bk } является минимальным разбиением числа N – i на k – l частей. Доказательство. Докажем вначале, что получаемое таким образом разбиение входит в множество A (N, k). Действительно, все его k частей нечётны, а их сумма равна N. Для того чтобы доказать, что все его части различны, достаточно доказать, что bl > bl+1, поскольку части разбиения с b1 по bl и с bl+1 по bk упорядочены по убыванию. По определению правого увеличиваемого элемента, найдется такое f > l, что элемент af – правый уменьшаемый. Рассмотрим разбиение {d1, d2, … , dk }, такое, что dl = al + 2, df = af – 2, а при всех остальных i соответствующие

14 элементы равны (ai = di). Очевидно, что d1 > d2 > … > dk и это разбиение входит в множество A (N, k). Заметим, что di = bi при всех i = 1, 2, … , l, а значит, разбиение {dl+1, dl+2, … , dk } является разбиением того же числа, что и разбиение {bl+1, bl+2, … , bk }. Стало быть, dl+1 ≥ bl+1, что следует из определения минимального разбиения. Итак, получаем неравенство bl = dl > dl+1 ≥ bl+1, то есть bl > bl+1. Осталось доказать, что не существует такого разбиения c (N, k), что a (N, k) < c (N, k) < b (N, k). Предположим противное; тогда, по определению, ci = bi = ai при i = 1, 2, … , l – 1, а cl равно либо al, либо al + 2. Если cl = al + 2 = bl, то i =N– i =N– i, то есть разбиение {cl+1, cl+2, … , ck } меньше {bl+1, b+2, … , bk } – минимального разбиения числа N – i на k – l частей. Противоречие. Значит, cl = al. Но в таком случае, поскольку c (N, k) > a (N, k), должно найтись такое j > l, что cj > aj и ci = ai при всех i = 1, 2, … , j – 1. Поскольку N– i i = i = и cj > aj, то найдется m > j, такое, что cm < am. Очевидно, что в таком случае либо am – правый уменьшаемый элемент, либо правый уменьшаемый элемент в разбиении a (N, k) имеет номер больше m. С другой стороны, элемент aj по определению является увеличиваемым: j ≠ 1 и aj < aj + 2 ≤ cj < cj-1 = aj-1. Но тогда элемент al не является правым увеличиваемым, поскольку не выполняется свойство 2 из определения 5. Противоречие. Следовательно, исходное предположение неверно и лемма доказана. Теперь, используя леммы 1 и 2, составим алгоритмы для функций MinPart и NextPart. Блок-схема первого из этих алгоритмов представлена на рис. 1.3.

15 Рис. 1.3. Блок-схема функции MinPart Здесь t – массив, в который записывается разбиение, N и k – число и количество частей, на которые оно разбивается, а i – номер элемента массива, с которого начинается запись разбиения (то есть части разбиения хранятся в массиве под номерами с i по i+k–1). Функция MinPart принимает на вход эти 4 значения и ничего не возвращает. Результатом работы функции является присваивание элементам массива t[1], t[2], … , t[k] значений частей минимального разбиения числа N на k частей. Следующая функция принимает на вход числа N и k и массив t, в котором содержится разбиение числа N на k слагаемых. В результате своей работы функция заменяет разбиение следующим за ним, согласно определению 3. Для этого объявляется переменная label, которая находит вначале индекс правого уменьшаемого элемента, а затем – индекс правого увеличиваемого элемента. После этого данный элемент массива

16 увеличивается на 2, а для нахождения оставшихся используется функция MinPart, блок-схема которой представлена на рисунке 1.3. На рис. 1.4. представлена блок-схема функции NextPart. Рис. 1.4. Блок-схема функции NextPart Теперь запишем алгоритм полного перебора и вычисления количества разбиений из множества A (N, k). Он представлен на рис. 1.5.

17 Рис. 1.5. Алгоритм расчёта количества разбиений A (N, k) В этом алгоритме для учёта количества разбиений используется переменная kolic. Чтобы получить алгоритм для всех возможных k, необходимо повторить алгоритм на рис. 1.4 в цикле при изменении k с шагом 4 от минимального значения, равного (N-1) mod 4 + 1, до максимального, не превосходящего N0.5. Последнее утверждение верно, поскольку сумма k различных нечётных слагаемых больше или k2 (что очевидным образом следует из индукции). 1.3. Разработка функции проверки квадратов Полученный алгоритм позволяет перебрать все разбиения числа N, удовлетворяющие условиям 1-3. Для того чтобы получить значения функции sqrs (N), необходимо разработать функцию, которая по заданным частям разбиения определяет, является ли их произведение квадратом натурального числа. Обозначим эту функцию IsSquare.

18 Самый простой способ узнать, является ли произведение натуральных чисел полным квадратом – вычислить его, а затем проверить на истинность условие [sqr(P)] == sqr(P), где P – данное произведение, sqr(P) – квадратный корень из P, а квадратные скобки обозначают целую часть числа, то есть наибольшее целое, не превосходящее P. Однако этот метод в данной задаче не работает ввиду ограниченности максимального значения целочисленных типов данных. Так, максимальное значение типа int равно 2 147 483 648, а для типа long long это число равняется 9 223 372 036 854 775 807 ≈ 9*1019. В то же время произведение даже 20 частей разбиения, больших 40, даст результат, больший, чем 240 * 1020 > 1032. Стало быть, необходимо действовать по-другому. Будем использовать метод факторизации: каждая часть разбиения раскладывается на простые множители, после чего для каждого из этих множителей вычисляется чётность количества раз, которое он встречается. Воспользуемся известной теоремой теории чисел: если n – составное число, то оно имеет простой делитель, не превосходящий sqr(n). Создадим массив, в который занесём несколько первых простых чисел. Поскольку разрабатываемая программа будет вычислять значения для N ≤ 1500, будет достаточно занести в массив 12 простых чисел (13-е простое число равно 41, а 412 > 1500). Обозначим этот массив primes. Для факторизации будем использовать другой массив (обозначим его MainArray). Основная идея такова: вначале запишем все части разбиения в этот массив, начиная с 13-го места (с первого по 12-е места заполним нулями), а затем для всех возможных пар i и j будем нацело делить i-ю часть разбиения (записанную в массив MainArray) на j-й элемент массива primes до тех пор, пока это возможно. При этом всякий раз, когда операция деления проходит успешно и число в массиве уменьшается, будем инкрементировать j-й элемент массива MainArray. Очевидно, любой элемент массива MainArray (начиная с 13-го) после завершения над ним всех операций деления будет равен либо 1, либо простому числу, поскольку он не будет делиться ни на

19 одно из первых 12 простых чисел. Стало быть, после того, когда все операции завершатся, все отличные от 1 элементы массива MainArray, начиная с 13-го, будут являться простыми числами. С другой стороны, при i ≤ 12 в i-м элементе массива будет записан показатель степени, в которой число pi входит в разложение числа N. Если хотя бы одно из этих чисел будет нечётным, то N заведомо не является полным квадратом. Проведём соответствующую проверку, и в случае подтверждения передаём в качестве возвращаемого значения функции false. В противном случае необходимо проверить, чётное ли количество раз встречается каждое из оставшихся чисел, входящих в массив и не равных 1. Если это верно, возвращаем true, иначе – false. Один из способов осуществить эту проверку состоит в следующем. В двойном цикле осуществляется перебор все пар индексов (i, j) для элементов массива, начиная с 13-го, и происходит сравниваем элементов этого массива с соответствующими индексами. В том случае, когда они равны и больше 1, присваиваем каждому из них значение 1. Если по завершении этого цикла в этой части массива нет элементов, отличных от 1, то каждое из чисел, отличных от 1, встречалось чётное количество раз. В противном случае хотя бы одно из простых чисел встречалось нечётное количество раз. Таким образом, был описан план по созданию алгоритма для функции IsSquare. Теперь запишем полный алгоритм этой функции. Он представлен на рис. 1.6.

20 Рис. 1.6. Алгоритм функции IsSquare Поскольку алгоритм функции основан на трудоёмкой операции факторизации, имеет смысл проводить предварительную проверку для отсеивания разбиений, заведомо удовлетворяющих условию 4. Воспользуемся известным свойством полных квадратов: если p – нечётное число, то p2 ≡ 1 (mod 8). Обозначим через q1, q3, q5 и q7 количество частей

21 разбиения, дающих при делении на 8 остатки 1, 3, 5 и 7 соответственно, а через c1, c3, c5 и c7 – соответствующие остатки этих чисел при делении на 2. Тогда, обозначая произведение частей разбиения через P, получаем P ≡ 1q1 * 3q3 * 5q5 * 7q7 ≡ 3c3 * 5c5 * 7c7 ≡ 1 (mod 8) (1.3) Предпоследнее равенство следует из того, что числа 3, 5 и 7 в любой чётной степени дают остаток 1 при делении на 8. В самом деле, пусть r3, r5 и r7 – такие числа, что q3 = 2 * r3 + c3, q5 = 2 * r5 + c5 и q7 = 2 * r7 + c7. Тогда получаем следующее: 1) 3q3 = 3(2 * r3 + c3) = (32)r3 * 3c3 = 9r3 * 3c3 ≡ 1r3 * 3c3 ≡ 3c3 (mod 8). 2) 5q5 = 5(2 * r5 + c5) = (52)r5 * 5c5 = 25r5 * 5c5 ≡ 1r5 * 5c5 ≡ 5c5 (mod 8). 3) 7q7 = 7(2 * r7 + c7) = (72)r7 * 7c7 = 49r7 * 7c7 ≡ 1r7 * 7c7 ≡ 7c7 (mod 8). После перемножения получаем этих трёх сравнений и получаем требуемое. Поскольку числа c3, c5 и c7 могут равняться лишь 0 или 1, то простым перебором убеждаемся, что сравнение (1.3) истинно тогда и только тогда, когда c3 = c5 = c7. В самом деле, рассмотрим все возможные случаи. 1) c3 = c5 = c7 = 0. Тогда 3c3 * 5c5 * 7c7 ≡ 1 (mod 8). 2) c3 = c5 = 0, c7 = 1. Тогда 3c3 * 5c5 * 7c7 ≡ 7 (mod 8). 3) c3 = c7 = 0, c5 = 1. Тогда 3c3 * 5c5 * 7c7 ≡ 5 (mod 8). 4) c5 = c7 = 0, c3 = 1. Тогда 3c3 * 5c5 * 7c7 ≡ 3 (mod 8). 5) c3 = c5 = c7 = 1. Тогда 3c3 * 5c5 * 7c7 ≡ 1 (mod 8). 6) c3 = c5 = 1, c7 = 0. Тогда 3c3 * 5c5 * 7c7 ≡ 15 ≡ 7 (mod 8). 7) c3 = c7 = 1, c5 = 0. Тогда 3c3 * 5c5 * 7c7 ≡ 21 ≡ 5 (mod 8). 8) c5 = c7 = 1, c3 = 0. Тогда 3c3 * 5c5 * 7c7 ≡ 35 ≡ 3 (mod 8). Таким образом, из 3c3 * 5c5 * 7c7 ≡ 1, действительно, следует c3 = c5 = c7. Стало быть, в ходе алгоритма, после получения очередного разбиения, необходимо проверять это равенство и использовать функцию IsSquare

22 только в том случае, когда оно не выполняется. Это позволит получить достаточный выигрыш во времени при больших N. Окончательный последовательный алгоритм приведён на рис. 1.7. Рис. 1.7. Последовательный алгоритм

23 ГЛАВА 2. РЕАЛИЗАЦИОННАЯ ЧАСТЬ 2.1. Разработка параллельного алгоритма Следующим шагом после получения последовательного алгоритма является его распараллеливание. Для этого создадим алгоритм, перебирающий часть разбиений числа N на k натуральных слагаемых, в зависимости от количества частей (size) и номера части (rank). Суть работы алгоритма в следующем. На вход подаются переменные N, k, size и rank. После этого для каждого процесса определяются два числа, которые мы назовём верхней и нижней границами. Алгоритм работает так же, как и последовательный, но каждый процесс перебирает лишь часть разбиений, начиная с минимального из тех, максимальная часть которых не меньше нижней границы, и заканчивая самым большим из тех, максимальная часть которых не превосходит верхней границы. Таким образом, каждый процесс находит значения r4 (n) и sqrs (n) для своей части разбиений, после чего применяется операция редукции для получения окончательного ответа. Основной проблемой при таком подходе является точный подбор верхней и нижней границ. В идеальном случае они должны делить множество разбиений таким образом, чтобы в каждую из частей попадало примерно одинаковое количество разбиений. Пусть min – максимальная часть минимального разбиения, а max – максимальная часть максимального разбиения. Очевидно, верхняя граница каждого процесса, кроме последнего, является нижней границей для следующего процесса. Таким образом, для двух процессов неизвестная граница всего одна. Обозначим её middle. В данной работе опытным путём было установлено, что множество разбиений A(N, k) будет делиться примерно на две равные части, если принять middle = ((min*max)0.5+2*min*max/(min+max))/2, то есть среднее

24 арифметическое между средним геометрическим и средним гармоническим чисел min и max. Обозначим эту функцию через mid (min, max). Таким образом, для двух процессов решение найдено. В целях оптимизации эффективности работы программы было решено создать такой параллельный алгоритм, который будет работать для количества процессов, равных степени двойки (то есть 2n, где n – целое неотрицательное). Для хранения границ будет использоваться массив bound с размерностью, на 1 превышающей количество процессов. В нулевую ячейку массива записывается min, в последнюю (n-ю) – max. Число mid (min, max) записывается в ячейку ровно посередине между ними, то есть в ячейку с номером n/2. На следующем этапе заполняются ячейки ровно посередине между заполненными – то есть ячейки с номерами n/4 и 3n/4. Эти действия продолжаются до тех пор, пока не будут заполнены все ячейки массива. При этом нижняя и верхняя границы для процесса с номером i, очевидно, будут равны bound [i] и bound [i+1] соответственно. Остаётся найти оптимальный алгоритм для заполнения ячеек массива bound, начиная со второго этапа, поскольку функция mid вычисляет эффективную границу только на первом шаге. Для этого была определена функция avg (x, y, a, b) = (a * x + b * y)/(a + b). При этом для установления границы в случае x = min коэффициенты используются коэффициенты a = 1 и b = e, где e ≈ 2.71828459045 – число Эйлера. Если y = max, то коэффициенты принимают значения a = 9 и b = 1 соответственно. Во всех остальных случаях a = b = 1, то есть граница устанавливается посередине. Очевидно, что элементы массива bound зависят лишь от трёх чисел – числа N, количество разбиений которого вычисляется в программе, количества частей разбиений k и количества процессов size. Рассмотрим алгоритм, заполняющий этот массив. Его блок-схема изображена на рис. 2.1.

25 Рис. 2.1. Блок-схема алгоритма для заполнения массива bound Обозначим функцию для заполнения массива bound (то есть для определения всех границ) через fill, а её параметрами являются числа N, k и количество процессов size. Тогда алгоритм, перебирающий часть разбиений числа N на k натуральных слагаемых, в зависимости от количества частей (size) и номера части (rank) работает следующим образом (рис. 2.2):

26 Рис. 2.2. Параллельный алгоритм для перебора части разбиений Здесь ceil – функция, возвращающая число, равное минимальному целому, которое не меньше аргумента функции. Чтобы получить окончательный параллельный алгоритм, необходимо инициализировать k значением (N-1) mod 4 + 1, а затем в цикле при изменении k с шагом 4 до тех пор, пока k2 не превосходит N, использовать алгоритм, описанный выше, в который, по аналогии с алгоритмом на рис. 1.6, нужно добавить функцию проверки квадратов. 2.2. Описание программы Разработку программы было решено проводить на языке программирования C, поскольку к нему существуют стандартные «привязки» MPI, в котором будет реализована параллельная программа. В программе используется несколько пользовательских функций, алгоритм которых описан в части 1 данной работы:

27 - MinPart – функция для получения минимального разбиения; - NextPart – функция для получения следующего разбиения; - IsSquare – функция для проверки данного разбиения на выполнение условия 4 (является ли произведение его всех его частей полным квадратом). Функции MinPart и NextPart имеют тип void, поскольку они не возвращают значений, а лишь формируют необходимые разбиения и вычисляют их количество. Далее представлены листинги функций MinPart и NextPart. Листинг 2.1. Функция MinPart void MinPart(int t[40], int N, int k, int i) { N=(N-k*k)/2; int r=N%k; int q=N/k; for (int j=i; j<k+i; j++) {t[j]=2*(k+i-j+q)-1;} for (int j=i; j<i+r; j++) {t[j]+=2;} } Конец листинга Листинг 2.2. Функция NextPart void NextPart(int t[40], int N,int k) { int metka=k, sum; while (t[metka]==t[metka+1]+2) {metka--;} metka--; while (t[metka]==t[metka-1]-2) {metka--;} sum=2; for (int i=1; i<=metka; i++) {sum+=t[i];} t[metka]+=2; MinPart(t, N-sum,k-metka,metka+1); } Конец листинга

28 В листинге 2.3 приведен код функции IsSquare. Листинг 2.3. Функция IsSquare bool IsSquare (int t[40], int k) { int i, j; bool p=true; for (i=0; i<12; i++) {MainArray[i]=0;} for (i=12; i<12+k; i++) {MainArray[i]=t[i-11];} for (i=0; i<12; i++) { for (j=12; j<k+12; j++) { while (MainArray[j]%primes[i]==0) { MainArray[j]/=primes[i]; MainArray[i]++;} } } for (i=0; i<12; i++) { if (MainArray[i]%2==1) {p=false;}} if (p) { for (i=13; i<12+k; i++) { for (j=12; j<i; j++) { if (MainArray[j]==MainArray[i]) { MainArray[j]=1; MainArray[i]=1; } } } for (i=12; i<12+k; i++) { if (MainArray[i]!=1) {p=false;} } } return p; } Конец листинга Поскольку функция IsSquare даёт информацию о том, является ли произведение всех частей разбиения полным квадратом, и возвращает значения true или false, для неё выбран тип bool. В работе функции также используются массив primes, содержащий первые 12 простых чисел, и массив

29 MainArray, в котором непосредственно и происходит факторизация. Оба массива в данной программе объявлены глобально. С целью упрощения понимания программы также была введена функция GetPart, которая по числам N, k, size и rank перебирает все разбиения N на k частей, удовлетворяющие условиям 1-3, начиная от нижней границы процесса с номером rank и заканчивая верхней границей. Также эта функция вычисляет число всех таких разбиений и количество тех из них, которые не удовлетворяют условию 4. Таким образом, она рассчитывает значения r4 (n) и sqrs (n) и возвращает последнее из них. Код функции GetPart в составе разработанной программы содержится в приложении 1. В главной функции программы – main – происходит инициализация MPI с помощью MPI_Init. Затем устанавливается количество процессов (size) и каждому из них присваивается номер (rank) с помощью функций MPI_Comm_size MPI_Comm_rank соответственно. Функцией MPI_Bcast число N, введённое при запуске программы, пересылается всем процессам, после чего каждый процесс при помощи функций MinPart и NextPart перебирает свою часть разбиений и находит свою часть r4 (n) и sqrs (n). После этого применяется функция MPI_Reduce, которая собирает значения со всех процессов в нулевой и суммирует их, получая окончательный результат. Для ввода и вывода данных используются функции форматированного ввода и вывода – scanf и printf соответственно. Функция int printf (const char *format, arglist) записывает в stdout аргументы из списка arglist под управлением строки, на которую указывает аргумент format. Эта строка включает в себя объекты, выполняющие две цели: символы, которые сами должны быть выведены на экран, и спецификаторы формата, которые определяют вид для вывода аргументов из списка. Функция int scanf (const char *format, arglist), использующаяся для ввода, считывает данные из потока stdin. По форматам она аналогична функции printf.

30 Спецификаторы формата состоят из символа %, за которым следует код формата. Количество аргументов должно точно соответствовать количеству спецификаторов формата, причем следовать они должны в одинаковом порядке. Список спецификаторов форматов для различных типов данных: - %c – символ типа char; - %d, %i – число типа int со знаком; - %f – число типа double; - %o – восьмеричное число без знака; - %u – число типа unsigned int; - %x – 16-ричное целое число без знака (строчные буквы); - %X – 16-ричное целое число без знака (заглавные буквы); - %li – тип длинного целого числа со знаком (long, long int); - %lu – тип длинного целого числа без знака (unsigned long); - %lli – тип двойного длинного целого числа со знаком (long long); - %llu - тип двойного длинного целого числа без знака (unsigned long long). С целью измерения времени в программе используется функция MPI_Wtime. Это функция возвращает астрономическое время в секундах, которое прошло с некоторого фиксированного момента в прошлом. Чтобы получить время работы программы, функция применяется дважды: перед блоком кода, длительность выполнения которого необходимо узнать, и сразу после него. Разность между переменными, в которые сохраняется время (из последней вычитается первая) и даст необходимый результат. Таким образом, в программе используются следующие MPI-функции:  MPI_Init (&argc, &argv) – инициализация MPI;  int MPI_Comm_size (MPI_Comm comm, int * size) – определение количества процессов;  int MPI_Comm_rank (MPI_Comm comm, int * rank) – задаёт каждому процессу номер;

31  int MPI_Bcast (void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm) – функция для широковещательной рассылки данных. Процесс с номером root рассылает сообщение типа datatype из count элементов всем процессам области связи коммуникатора comm. Адресом начала расположения в памяти рассылаемых данных является buffer.  double MPI_Wtime() – возвращает астрономическое время в секундах, прошедшее с некоторого фиксированного момента времени.  int MPI_Reduce (void *sendbuf, type *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) – главный процесс с номером root собирает данные типа datatype из буфера sendbuf размерности count остальных процессов и проводит над ними операцию opp. Результат возвращается в буфер recvbuf, который имеет те же тип данных и размерность, что и sendbuf.  MPI_Finalize() – завершает работу с MPI [8]. Переменные kolic и kolicsqr, использующиеся в программе для хранения количества разбиений r4 (n) и sqrs (n), имеют тип unsigned long long, ввиду того, что они могут принимать значения, превышающие верхнюю границу диапазона int. Функция GetPart, возвращающая значение sqrs (n), имеет этот же тип. Несмотря на то, что основная программа выводит лишь значения функции sqrs (n), её можно использовать для получения информации о функции r4 (n). Для этого достаточно изменить возвращаемое значение в этой функции с kolicsqr на kolic. Для получения значений функции r (n) достаточно изменить инициализацию k на (N-1) mod 2 + 1 и усеньшить шаг с 4 до 2. Поскольку программа предназначена для запуска на кластере, графический интерфейс у неё отсутствует. Перед запуском программу необходимо откомпилировать (рис. 2.3), для чего используется следующая команда: - mpiCC Parts.c

32 Рис. 2.3. Компиляция и запуск программы Здесь Parts.c – название файла программы. Для запуска программы применяется команда mpirun, в число параметров которой входит переменная, равная количеству процессов, на которых будет исполняться программа. Например, для запуска на 4 процессах необходимо ввести следующее: - mpirun –np 4 ./a.out Где a.out – имя выходного файла. На рисунке 2.4 изображён ввод данных в программу.

33 Рис. 2.4. Ввод данных в программу После запуска программы предлагается ввести натуральное число N, являющееся аргументом функции квадратов. В данном примере рассматривается работа программы для случая N = 120. Программа вычисляет и выводит значение функции sqrs (N), а также время в секундах, которое было затрачено для получения результата с момента ввода данных. Результаты её работы представлены на рисунке 2.5. Рис. 2.5. Результаты работы программы при N=120

34 ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 3.1. Тестирование программы и результаты её работы Правильность алгоритма, на основе которого работает программа, была доказана в первой части данной работы. Тем не менее, было решено проверить её работу на достаточно малых значениях аргумента n. Для этого расчёт функций r (n), r4 (n), sqrs (n) при всех n ≤ 32 был произведён вручную. Результаты, полученные программой, прошли проверку на предмет соответствия теоретически рассчитанным значениям. Результаты представлены в таблице 3.1. Таблица 3.1 Тестирование программы при N ≤ 32 N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Теоретически рассчитанные значения r(N) r4 (N) sqrs(N) 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 2 0 0 2 1 1 2 2 1 2 1 0 3 0 0 3 1 0 3 3 0 4 3 0 5 1 0 5 1 0 5 4 0 6 5 0 7 2 0 8 1 0 8 5 0 Результаты работы программы r(N) r4 (N) sqrs(N) 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 0 0 2 0 0 2 1 1 2 2 1 2 1 0 3 0 0 3 1 0 3 3 0 4 3 0 5 1 0 5 1 0 5 4 0 6 5 0 7 2 0 8 1 0 8 5 0

35 Таблица 3.1. Продолжение N 23 24 25 26 27 28 29 30 31 32 Теоретически рассчитанные значения r(N) r4 (N) sqrs(N) 9 8 1 11 5 1 12 2 1 12 6 1 14 12 0 16 9 0 17 3 0 18 7 1 20 16 2 23 15 2 Результаты работы программы r(N) r4 (N) sqrs(N) 9 8 1 11 5 1 12 2 1 12 6 1 14 12 0 16 9 0 17 3 0 18 7 1 20 16 2 23 15 2 Сравнение столбцов таблицы с результатами расчётов вручную и работы программы подтвердили, что на заданном наборе аргументов функций программа даёт верный результат. В ходе исследования были получены значения функций r (n), r4 (n), sqrs (n) для всех n ≤ 600. Результаты вычислений представлены в таблице 3.2 для n = 1 и n, кратных 50. Таблица 3.2 Значения функций N 1 50 100 150 200 250 300 350 400 450 500 550 600 r (N) 1 98 2 574 34 037 312 928 2 257 009 13 663 248 72 267 480 343 112 116 1 490 170 896 6 003 604 571 22 676 522 718 80 974 290 498 r4 (N) 1 26 1 008 17 436 172 441 1 108 211 6 524 506 37 245 270 172 512 720 729 111 366 3 044 709 903 11 338 825 972 40 129 477 067 sqrs (N) 1 2 2 55 453 1 267 2 588 10 410 43 862 112 617 220 569 639 196 2 073 662 Из таблицы видно, что каждая из функций возрастает при изменении n

36 с шагом, равным 50. Кроме того, заметно, что при больших n выполняется приближённое равенство r(n) ≈ 2r4(n), а sqrs (n) много меньше обеих функций. Для того чтобы оценить скорость роста функций r4 (N) и sqrs (N), рассмотрим их значения для каждого n от 1 до 75. Таблица 3.3 Значения функций при всех N ≤ 75 N r (N) r4 (N) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 0 1 1 1 1 1 2 2 2 2 3 3 3 4 5 5 5 6 7 8 8 9 11 12 1 0 0 0 1 1 0 0 1 2 1 0 1 3 3 1 1 4 5 2 1 5 8 5 2 sqrs (N) 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 N r (N) r4 (N) 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 12 14 16 17 18 20 23 25 26 29 33 35 37 41 46 49 52 57 63 68 72 78 87 93 98 6 12 9 3 7 16 15 6 8 21 23 11 10 27 34 19 13 33 47 31 18 40 64 48 26 sqrs (N) 1 0 0 0 1 2 2 1 1 1 0 0 1 2 1 0 0 0 0 0 3 5 3 2 1 N r (N) r4 (N) 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 107 117 125 133 144 157 168 178 192 209 223 236 255 276 294 312 335 361 385 408 437 471 501 530 568 49 84 71 39 59 108 102 58 72 136 142 86 90 170 193 126 113 208 256 180 145 254 334 253 190 sqrs (N) 0 0 0 3 3 7 6 3 2 2 1 0 1 6 6 1 0 0 1 2 5 11 10 4 2 Полученные результаты подробно рассмотрены в 3.3. 3.2. Расчёт ускорения и эффективности В ходе выполнения работы были произведены замеры времени работы последовательной и параллельной программ для различного количества

37 процессов и разных начальных данных. Также в каждом случае было вычислено отношение первой величины – длительности выполнения последовательной программы - ко второй. Для того чтобы избежать большого влияния статистической погрешности на время выполнения программы, были выбраны значения N ≥ 288. С другой стороны, максимальное значение N, которое использовалось для подсчётов, равно 500, поскольку при достаточно больших N время выполнения последовательной программы вызывает затруднения. Результаты измерений помещены в таблицу 3.4. Таблица 3.4 Время выполнения последовательной и параллельной программ N 1 процесс 2 процесса 4 процесса 8 процессов T 1, с T 2, с T1/T2 T4, с T1/T4 T8, с T1/T8 288 2.85 1.45 1.97 0.83 3.43 0.46 6.20 300 3.14 1.65 1.94 0.84 3.74 0.47 6.68 320 8.83 4.46 1.97 2.52 3.50 1.32 6.69 360 33.57 17.18 1.95 9.10 3.69 5.16 6.50 400 122.35 64.50 1.90 34.12 3.59 19.52 6.26 450 544.90 279.80 1.95 142.7 3.82 87.92 6.20 480 1310.56 670.17 1.96 393.4 3.33 219.1 5.98 500 2000.8 1042.1 1.92 564.7 3.54 327.6 6.11 Одним из показателей успешности параллельной программы является её ускорение, то есть отношение времени выполнения последовательной версии к времени выполнения параллельной версии. Другой показатель – эффективность, равный, по определению, отношению ускорения программы к количеству используемых процессов. В таблице 3.4 даны ускорения программы для каждого случая. Рассмотрим среднее ускорение для каждого size, где size – количество

38 процессов, и вычислим среднюю эффективность. Эти данные приведены в таблице 3.5. Таблица 3.5 Ускорение и эффективность программы Количество процессов Ускорение Эффективность 1 1 1 2 1.945 0.972 4 3.58 0.895 8 6.328 0.791 Таким образом, из таблицы видно, что ускорение возрастает с увеличением числа процессов, но максимальная эффективность достигается при size = 2. Это связано с тем, что разбиения множества A (N, k) разделить на две примерно равные группы можно с большей точностью, чем на 4, 8 и более. 3.3. Анализ полученных результатов Из таблицы 3.3 видно, что функция r4 (n) не является монотонной. Однако легко доказать, что при любом натуральном n выполняется неравенство r4 (n + 4) ≥ r4 (n) (3.1) причём равенство достигается только при n = 1, 3, 4, 5, 8, 9, 13, 17, 21. В самом деле, любое разбиение для числа n + 4 можно получить из разбиения числа n увеличением максимальной части разбиения на 4. При этом оно, очевидно, будет также обладать свойствами нечётности и различности частей, а количество частей не поменяется, то есть и остаток при делении на 4 будет тем же, что у числа n + 4. Таким образом, любому

39 разбиению числа n, удовлетворяющему свойствам 1-3, взаимно однозначно соответствует некоторое разбиение числа n + 4 с теми же свойствами, откуда и следует выполнение неравенства. Легко также заметить, что при k ≥ 2 можно установить взаимно однозначное соответствие между всеми нужными разбиениями числа n и некоторыми из нужных разбиений числа n + 4 и другим способом – увеличением первой и второй частей разбиения на 2. При этом будет существовать по крайней мере одно из нужных разбиений числа n + 4, которому ничего не поставлено в соответствие – разбиение, в котором первая часть принимает максимально допустимое значение. Это значит, что неравенство будет строгим. Следовательно, равенство возможно только в тех случаях, когда число n можно разложить только на одну часть (то есть, в силу свойства 3, n ≡ 1 (mod 4)), либо ни одного разбиения не существует (r4 (n) = 0). Число 25 уже можно разложить на 5 частей, поэтому в первом случае получаем n = 1, 5, 9, 13, 17. Во втором случае n заведомо не превосходит 16, поэтому простым перебором с использованием таблицы 3.3 находим оставшиеся значения. Таким образом, функция r4 (n) при изменении n с шагом 4 является монотонной и строго возрастает на всей числовой оси, кроме некоторых достаточно малых значений. Также из таблицы 3.3 следует, что функция r (n) является монотонной при n ≥ 2, причём при n ≥ 26 она строго возрастает. Приведём строгое доказательство этого факта, то есть докажем, что r (n + 1) ≥ r (n) при всех натуральных n ≠ 1. Для этого каждому разбиению числа n из нечётных различных частей будем ставить в соответствие разбиение числа n + 1 с аналогичными свойствами по следующему правилу: - Если минимальная часть разбиения числа n не равна 1, добавляем часть, равную 1; - Если минимальная часть разбиения числа n равна 1, то исключаем её из разбиения, а максимальную часть увеличиваем на 2.

40 Очевидно, что все части нового разбиения будут нечётными и попарно различными. Кроме того, разбиение числа n будет содержать часть, равную 1, тогда и только тогда, когда соответствующее ему разбиение числа n + 1 такой части не содержит. Из этого, в свою очередь, следует, что два разбиения числа n + 1, соответствующие разбиениям числа n, одно из которых содержит часть, равную 1, а другое – нет, не могут быть равными. Из правила, по которому устанавливается соответствие, также следует, что это равенство невозможно также и в случае, когда оба исходных разбиения содержат часть, равную 1, или же оба её не содержат. Стало быть, данное правило различным разбиениям числа n ставит в соответствие различные разбиения числа n + 1. Кроме того, единственным разбиением, для которого не найдётся соответствие, очевидно, является то, в котором лишь одна часть и она равна 1, то есть при n = 1. Это верно, поскольку в остальных случаях часть, равную 1, можно исключить из разбиения, или же исключать части вообще не нужно. Таким образом, если n > 1, то из вышесказанного следует, что каждому разбиению числа n из нечётных различных чисел будет поставлено в соответствие какое-то разбиение числа n + 1 из нечётных различных чисел, причём разных разбиениям соответствуют разные. Это и означает, что r (n + 1) ≥ r (n), что и требовалось. Чтобы лучше понять поведение функций r (n) и r4 (n), в том числе относительно друг друга, рассмотрим их графики в одной системе координат. Они изображены на рис. 3.1.

41 5000 4500 4000 3500 3000 r4(N) 2500 r (N) 2000 1500 1000 500 1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 0 Рис. 3.1. Графики функций r (n) и r4 (n) Из графиков видно, что в среднем функция r4 (n) принимает значения, в два раза меньшие, чем r (n). Перейдём к функции sqrs (n). Как видно из таблицы 3.3, эта функция не является монотонной при изменении n с шагом 1, однако, по аналогии с функцией r4 (n), будем пытаться менять n с определённым шагом для получения монотонности. Детальный анализ показывает, что такой шаг должен быть равным 8. Рассмотрим различные графики функции sqrs (n), соответствующих различным случаям n: i-й график отражает значения функции при n ≡ i – 1 (mod 8).

42 n≡0 (mod 8) 18000 16000 14000 12000 10000 n≡0 (mod 8) 8000 6000 4000 2000 8 24 40 56 72 88 104 120 136 152 168 184 200 216 232 248 264 280 296 312 328 344 0 Рис. 3.2. n ≡ 0 (mod 8) На рис. 3.2 рассмотрен случай, когда n делится на 8. Аргументы функции при этом изменяются в диапазоне от 8 до 352. Теперь обратимся к рассмотрению случая n ≡ 1 (mod 8) (рис. 3.3). n≡1 (mod 8) 18000 16000 14000 12000 10000 n≡1 (mod 8) 8000 6000 4000 2000 0 1 25 49 73 97 121 145 169 193 217 241 265 289 313 337 Рис. 3.3. n ≡ 1 (mod 8) В этом случае максимальное значение, которое принимает n, равно 353. Сравнение этого графика с предыдущим позволяет сделать вывод о том, что при n ≡ 0 (mod 8) и n ≡ 1 (mod 8) функция sqrs (n) принимает близкие друг к другу значения.

43 Обратимся к случаю n ≡ 2 (mod 8) (рис. 3.4). n≡2 (mod 8) 16000 14000 12000 10000 8000 n≡2 (mod 8) 6000 4000 2000 0 2 26 50 74 98 122 146 170 194 218 242 266 290 314 338 Рис. 3.4. n ≡ 2 (mod 8) На этом графике видно, что значения функции стабильно меньше, чем в первых двух случаях, однако она по-прежнему монотонно возрастает, начиная с определённого момента. На рис. 3.5 изображён график для n ≡ 3 (mod 8). n≡3 (mod 8) 14000 12000 10000 8000 n≡3 (mod … 6000 4000 2000 0 3 27 51 75 99 123 147 171 195 219 243 267 291 315 339 Рис. 3.5. n ≡ 3 (mod 8) На этих двух графиках максимальное значение n равно 346 и 347 соответственно.

44 Перейдём к случаю n ≡ 4 (mod 8). Соответствующий график рассмотрен на рис. 3.6. n≡4 (mod 8) 12000 10000 8000 6000 n≡4 (mod 8) 4000 2000 0 4 28 52 76 100 124 148 172 196 220 244 268 292 316 340 Рис. 3.6. n ≡ 4 (mod 8) В этом случае функция принимает наименьшие значения по сравнению со всеми предыдущими ситуациями. На рис. 3.7 приведён график для n ≡ 5 (mod 8). При этом максимальное значение аргумента функции уменьшено до 249. n≡5 (mod 8) 9000 8000 7000 6000 5000 n≡5 (mod 8) 4000 3000 2000 1000 5 21 37 53 69 85 101 117 133 149 165 181 197 213 229 245 261 277 293 309 325 341 0 Рис. 3.7. n ≡ 5 (mod 8)

45 Далее на очереди n ≡ 6 (mod 8). Соответствующий график показан на рис. 3.8. n≡6 (mod 8) 12000 10000 8000 6000 n≡6 (mod 8) 4000 2000 6 22 38 54 70 86 102 118 134 150 166 182 198 214 230 246 262 278 294 310 326 342 0 Рис. 3.8. n ≡ 6 (mod 8) Последний график, для случая n ≡ 7 (mod 8), представлен на рис. 3.9. n≡7 (mod 8) 14000 12000 10000 8000 n≡7 (mod 8) 6000 4000 2000 7 23 39 55 71 87 103 119 135 151 167 183 199 215 231 247 263 279 295 311 327 343 0 Рис. 3.9. n ≡ 7 (mod 8) Из приведённых графиков видно, что, начиная с некоторого момента, функция строго возрастает, причём её возрастание носит экспоненциальный

46 характер. Точнее, функция экспоненциально возрастает при n ≥ 173 при изменении n с шагом 8 для любых n. Рассмотрим теперь все 8 графиков в одной системе координат. Они представлены на рис. 3.10. 18000 16000 14000 n≡1 (mod 8) 12000 n≡2 (mod 8) n≡3 (mod 8) 10000 n≡4 (mod 8) 8000 n≡5 (mod 8) n≡6 (mod 8) 6000 n≡7 (mod 8) n≡0 (mod 8) 4000 2000 1 14 27 40 53 66 79 92 105 118 131 144 157 170 183 196 209 222 235 248 261 274 287 300 313 326 339 0 Рис. 3.10. Графики в общей системе координат Из рисунка видно подтверждение вышесказанному: графики функций для n ≡ i (mod 8) и n ≡ j (mod 8) практически совпадают при таких i и j, что i + j ≡ 1 (mod 8). Максимальные значения функция принимает при i = 0 и j = 1, минимальные – при i = 4 и j = 5, а значения при i = 2 и j = 7 больше значений при i = 3 и j = 6. Теперь выясним, как ведёт себя функция при изменении n с шагом 1. Её график приведён на рисунке 3.11. При этом n меняется в пределах от 1 до 357.

47 Рис. 3.11. График функции sqrs (n) Из графика видно, что отрезки возрастания и отрезки убывания чередуются у функции примерно на равных интервалах. При подробном рассмотрении выясняется, что длина отрезков монотонности функции равна от 3 до 5 для достаточно больших n, причём на отрезках [8k + 1; 8k + 4] функция строго убывает, а на отрезках [8k + 5; 8(k + 1)] – строго возрастает. Таким образом, для функции sqrs (n) были сформулированы гипотезы о её свойствах на основе анализа значений. Для подтверждения или опровержения этих гипотез необходимы дальнейшие исследования.

48 ЗАКЛЮЧЕНИЕ В данной работе была затронута тема разбиения натуральных чисел на различные нечётные слагаемые. Особое внимание уделялось разбиениям, количество частей которых даёт тот же остаток от деления на 4, что и их сумма, а произведение частей является квадратом натурального числа. Были определены функции для количества разбиений, удовлетворяющих всем или некоторым из данных свойств. В первой части данной работы была рассмотрена предметная область, в том числе – алгоритм Липского для порождения всех возможных разбиений натурального числа. Ввиду его непригодности для достижения цели работы возникла необходимость в разработке собственного алгоритма. Этапы разработки с необходимыми доказательствами также содержатся в теоретической части. Во второй части был разобран один из возможных способов распараллеливания данного алгоритма, а также разработана и описана программа по данному алгоритму. В третьей части было произведено тестирование программы и сделан окончательный вывод о правильности её работы, после чего были найдены ускорение и эффективность, в зависимости от количества процессов и аргументов функции. Результатом работы являются разработанный параллельный алгоритм для расчёта количества квадратов в произведениях разбиений натуральных чисел, а также эффективная программа, созданная по этому алгоритму. Таким образом, основная цель работы достигнута. Также выполнены и другие задачи работы:  Изучена предметная область;  Исследованы существующие алгоритмы;

49  Вычислены значения функции для достаточно малых аргументов;  Проанализированные полученные результаты с целью понять характер функции. Несмотря на полное решение всех задач работы, данные о характере поведения функции остаются гипотезами, нуждающимися в строгих математических доказательствах. Также сохраняется возможность найти более быстрый алгоритм вычисления значений функции sqrs (n), путём, например, перебора только тех разбиений, которые удовлетворяют условиям 1-3 и не удовлетворяют условию 4. Таким образом, по итогам данной работы остаются открытые вопросы, которые требуют дальнейшего изучения.

50 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Эндрюс, Г. Теория разбиений. / Эндрюс Г. – М.: Наука, 1982 – 256 с. 2. Липский, В. Комбинаторика для программистов. / Липский, В. – М.: Мир, 1988 – 200 с. 3. Фултон, У. Таблицы Юнга и их приложения к теории представлений и геометрии. / Фултон, У. – МЦНМО, 2006 – 328 с. 4. Джеймс, Г. Теория представлений симметрических групп. / Джеймс, Г. – М.: Мир, 1982 – 214 с. 5. Вайнштейн, Ф. В. Разбиение чисел. / Вайнштейн, Ф. В. // Квант – М.: Наука, 1988 - №11, с. 19-25. 6. Ferraz, R. A. Simple components and central units in group rings. / Ferraz, R. A. // Journal of Algebra, 2004. – No 1, p. 191-203. 7. Макдональд, И. Симметрические функции и многочлены Холла. / Макдональд, И. — М.: Мир, 1985. — 224 с. 8. Корнеев В. Д. Параллельное программирование в MPI. / Корнеев В. Д. – Новосибирск, 2002 – 220 с. 9. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: Вильямс, 2005 – 1296 с. 10. Hardy G. H. An Introduction to the Theory of Numbers, 6th edition. / G. H. Hardy, E. M. Wright. – UK: Oxford University Press, 2008. – 656 p.

51 ПРИЛОЖЕНИЕ 1 Полный код программы #include <mpi.h> #include <stdio.h> #include <math.h> int MainArray[52]; int primes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; #define exp 2.71828459045 void MinPart(int t[40], int N, int k, int i) { N=(N-k*k)/2; int r=N%k; int q=N/k; for (int j=i; j<k+i; j++) {t[j]=2*(k+i-j+q)-1;} for (int j=i; j<i+r; j++) {t[j]+=2;} } void NextPart(int t[40], int N,int k) { int metka=k, sum; while (t[metka]==t[metka+1]+2) {metka--;} metka--; while (t[metka]==t[metka-1]-2) {metka--;} sum=2; for (int i=1; i<=metka; i++) {sum+=t[i];} t[metka]+=2; MinPart(t, N-sum,k-metka,metka+1); } bool IsSquare (int t[40], int k) { int i, j; bool p=true; for (i=0; i<12; i++) {MainArray[i]=0;} for (i=12; i<12+k; i++) {MainArray[i]=t[i-11];} for (i=0; i<12; i++) { for (j=12; j<k+12; j++) { while (MainArray[j]%primes[i]==0) { MainArray[j]/=primes[i]; MainArray[i]++; } } } for (i=0; i<12; i++) { if (MainArray[i]%2==1) {p=false;} } if (p) { for (i=13; i<12+k; i++) { for (j=12; j<i; j++) { if (MainArray[j]==MainArray[i]) { MainArray[j]=1; MainArray[i]=1; } } }

52 for (i=12; i<12+k; i++) { if (MainArray[i]!=1) {p=false;} } } return p; } float mid (float min, float max) { float middle1 = 2*min*max/(min+max); float middle2 = sqrt(min*max); float middle = (middle1 + middle2)/2; return middle; } float avg (float min, float max, float a, float b) { float middle = (a*min + b*max)/(a+b); return middle; } unsigned long long GetPart (int t[40], int N, int k, int rank, int size) { int c3=0, c5=0, c7=0; unsigned long long kolic=0, kolicsqr=0; t[0]=N-(k-1)*(k-1)+2; t[k+1]=-1; MinPart(t, N, k, 1); float bound[17]; bound[0] = t[1]; bound[size] = N-(k-1)*(k-1); bound[size/2]=mid(bound[0], bound[size]); for (int diff=size/4; diff>0; diff/=2) { for (int i=1; i*diff<size; i+=2) { if (i*diff<size/2) { if (i==1) {bound[i*diff]=avg(bound[i*diff-diff], bound [i*diff+diff], 1, exp);} else {bound[i*diff]=avg(bound[i*diff-diff], bound [i*diff+diff], 1, 1);}} else { if (i*diff+diff==size) {bound[i*diff]=avg(bound[i*diff-diff], bound [i*diff+diff], 9, 1);} else {bound[i*diff]=avg(bound[i*diff-diff], bound [i*diff+diff], 1, 1);}} } } int minr=ceil(bound[rank]); if (minr%2==0) {minr++;} if (minr<bound[rank+1]) { t[1]=minr; MinPart(t, N-minr, k-1, 2); if (rank != 0) {NextPart(t, N, k);} c3=0; c5=0; c7=0; kolic++; for (int ind = 1; ind <= k; ind++) { if (t[ind]%8==3) {c3=(c3+1)%2;} if (t[ind]%8==5) {c5=(c5+1)%2;} if (t[ind]%8==7) {c7=(c7+1)%2;} } if (c3==c5 && c5==c7) { if (IsSquare (t, k)) {kolicsqr++;}

53 } while (t[1] < bound[rank+1]) { NextPart(t, N, k); c3=0; c5=0; c7=0; kolic++; for (int ind = 1; ind <= k; ind++) { if (t[ind]%8==3) {c3=(c3+1)%2;} if (t[ind]%8==5) {c5=(c5+1)%2;} if (t[ind]%8==7) {c7=(c7+1)%2;} } if (c3==c5 && c5==c7) { if (IsSquare (t, k)) {kolicsqr++;} } } } return kolicsqr; } int main(int argc, char *argv[]) { int myid, size, rank, N, i; double starttime, endtime; int Part[40]; unsigned long long kolic=0, allkolic; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &size); MPI_Comm_rank(MPI_COMM_WORLD, &rank); if (rank==0) { printf("Enter N:\n"); scanf("%d", &N); } starttime = MPI_Wtime(); MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD); for (i=0; i<size; i++) { if (rank==i) { for (int k=(N-1)%4+1; k*k <= N; k+=4) { kolic += GetPart (Part, N, k, i, size);} } } MPI_Reduce(&kolic, &allkolic, 1, MPI_UNSIGNED_LONG, MPI_SUM, 0, MPI_COMM_WORLD); endtime=MPI_Wtime(); if (rank==0) { printf("sqrs(%d)=%llu, Runtime = %f\n", N, allkolic, endtime-starttime); } MPI_Finalize(); return 0; }

Выпускная квалификационная работа выполнена мной совершенно самостоятельно. Все использованные в работе материалы и концепции из опубликованной научной литературы и других источников имеют ссылки на них. «___» ________________ _____ г. __________________________ (подпись) _____________________ (Ф.И.О.)

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв