Статья: Вычисление числа Пи с использованием технологии параллельного программирования OpenMP

Национальный исследовательский Мордовский государственный университет имени Н. П. Огарева, Саранск, Россия

Вычисление числа пи с использованием технологии параллельного программирования OpenMP

О.А. Бакаева

Аннотация

Актуальность и цели. Цель исследования - провести анализ различных методов вычисления числа Пи с использованием языка программирования C++ и сравнить сходимость, точность и скорость вычисления для этих методов с использованием технологии параллельного программирования и без нее. Материалы и методы. На основе известных математических выражений, которые являются качественной аппроксимацией числа Пи: ряды Грегори-Лейбница, Мадхавы, Нилаканта, формулы Эйлера и Валлиса - вычисляется приближенное значение числа Пи с точностью до 10-10 и количеством слагаемых до 106. Расчеты производятся в среде Visual Studio на языке программирования C++ стандартным способом и с использованием технологии параллельных вычислений OpenMP. Результаты. Для каждой из расчетных формул найдены абсолютная и относительная ошибки вычисления числа Пи. Проведен сравнительный анализ результатов, полученных в среде Free Pascal, С++ и С++ с использованием технологии OpenMP. Выводы. Выявлен самый эффективный способ вычисления числа Пи, учитывая сходимость ряда, точность и время вычислений.

Ключевые слова: число Пи, технологии параллельного программирования, OpenMP, Visual Studio, язык программирования C++, ряд Грегори-Лейбница, ряд Мадхавы, ряд Нилаканта, формула Эйлера, формула Валлиса

Abstract

CALCULATING THE NUMBER PI USING DATA PARALLEL PROGRAMMING OpenMP

O.A. Bakaeva

National Research Ogarev Mordovia State University, Saransk, Russia

Background. To analyze various methods for calculating the number Pi using the C ++ programming language and compare the convergence, accuracy and computation speed for these methods with and without data parallel programming. Materials and methods. Based on the well-known mathematical expressions that are a qualitative approximation of the number Pi: the Gregory-Leibniz, Madhava, Nilakant series, Euler and Wallis formulas, the approximate value of Pi is calculated with an accuracy of 10-10 and the number of terms up to 106. The calculations are performed in the Visual Studio environment on the C ++ programming language in a standard way and using the OpenMP parallel computing technology. Results. For each of the calculation formulas, the absolute and relative error in calculating the number Pi is found. A comparative analysis of the results obtained in Free Pascal, C ++ and C ++ using OpenMP technology is carried out. Conclusions. The most efficient way of calculating the number Pi was revealed, taking into account the convergence of the series, the accuracy and time of calculations.

Keywords: number Pi, data parallel programming, OpenMP, Visual Studio, C ++ programming language, Gregory-Leibniz series, Madhava series, Nilakant series, Euler's formula, Wallis's formula

Введение

Вопрос о величине, природе, способах вычисления и точности числа Пи интересовал ученых в различные времена. Эта тематика остается актуальной и в настоящее время. О том, как далеко продвинулась вычислительная наука, можно судить по количеству знаков в дробной части числа Пи, которое уже удалось определить на текущий момент времени.

Число Пи - фундаментальная математическая константа, равная отношению длины окружности к ее диаметру. Значение 3,14 является достаточно приблизительным и используется для обучения и простоты расчетов [1].

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

Число Пи настолько многогранно, что существует много подходов к его вычислению. Наиболее часто встречается геометрический подход к исследованию числа Пи. Так, в работах С. П. Коростелева описывается коррекция значения числа Пи на основании абсолютно точных решений задач квадратуры круга и удвоения куба [2, 3]. А коллектив авторов В. И. Чепасов, М. А. Токарева, О. В. Буреш вычисляет число Пи методом касательных в длинной арифметике [4].

В работе В. С. Сенашова, И. Л. Савостьянова [5] отражен геометрический и вероятностный смысл числа Пи, в [6] представлен информационный подход и АСК-анализ, а В. А. Андросенко исследует иррациональность выражения --т= с помощью новой интегральной конструкции [7]. Достаточно часто число Пи пересекается с физикой [8].

В зарубежных работах тоже отмечается важность использования числа Пи в инженерии и науке и приводятся классические способы его вычисления. Например, в [9] представлен исторический обзор методов вычисления данной константы: от Архимеда, использовавшего правильные многоугольники, китайского математика Цзу Чунчжи (вычислил 6 знаков в дробной части), малоизвестных рядов Грегори-Лейбница и Нилаканта до компьютерных вычислений с точностью до 13 300 000 000 000 знаков после запятой.

Число Пи нашло свое применение в архитектуре, искусстве и предметах культуры древних народов [10]. По размерам древних украшений в виде дисков, спиралей и пр. можно найти значение Пи и получить представление о знаниях геометрии в доисторические времена.

Начиная с середины ХХ в. для вычисления числа Пи использовались компьютеры и их вычислительные мощности. Огромный вклад в нахождение максимального количества знаков в дробной части числа Пи внесли Дж. фон Нейман (1949 г.), Ф. Женюи (1959 г.), Дж. Гийу и М. Буйе (1973 г.), Братья Чудновские (1989 г.), Я. Канада (2002 г.), А. Йи и С. Кондо [11]. Перспективной стала формула Бэйли-Боруэйна-Плаффа, открытая С. Плаффом [12].

Самый полный и детальный хронологический обзор методов нахождения числа Пи на английском языке представлен в работе R. P. Agarwal, H. Agarwal, S. K. Sen [13].

Причем с прогрессом вычислительной техники и увеличением мощностей современных компьютеров открываются новые возможности изучения самой константы, способов ее вычисления и ее практического применения [14].

Материалы и методы

С развитием техники и внедрением персональных компьютеров математическую природу числа Пи можно исследовать, используя мощные и быстрые вычислительные средства [15, 16].

В современном мире начали быстро развиваться и уже достигли определенного уровня технологии параллельного программирования. Благодаря присущим им преимуществам были решены некоторые классы задач, которые до внедрения данных методов оставались нерешенными или имели приближенное решение, или, что случалось чаще всего, требовали больших временных и вычислительных затрат. С использованием технологии параллельного программирования стало возможным решение задач с большими объемами данных и многочисленными операциями.

В настоящее время одной из самых используемых технологий параллельного программирования является OpenMP [17].

OpenMP (Open Multi-Processing) - это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью (SMP-системах).

При использовании технологии OpenMP разработчик не создает новую параллельную программу, а просто добавляет в текст последовательной программы OpenMP-директивы. При этом система программирования OpenMP предоставляет разработчику большие возможности по контролю над поведением параллельного приложения. Вся программа разбивается на последовательные и параллельные области. Все последовательные области выполняет главная нить, возникающая при запуске программы, а при входе в параллельную область главная нить порождает дополнительные нити [18].

Данная технология может быть эффективно реализована с помощью среды Visual Studio и языка программирования С++. Для обеспечения работоспособности OpenMP необходимо включить поддержку OpenMP в свойстве проекта и подключить одноименную библиотеку через #include <omp.h>.

Вычисление числа Пи можно проводить с помощью различных вычислительных инструментов [19]. Для этого подходят языки программирования Pascal, C++, математические пакеты Mathcad, MATLAB и др. Даже широко используемый табличный процессор MS Excel позволяет вычислить данную константу с вполне приемлемой точностью. Но данные методы и инструменты стандартны и известны [20]. В данной статье для вычисления числа Пи через сумму ряда предлагается использовать технологию параллельного программирования OpenMP. Благодаря распараллеливанию действий в циклах появляется возможность увеличивать скорость вычислений. А увеличивая количество слагаемых и число итераций в программе, можно получить любое количество знаков в дробной части числа и тем самым необходимую точность. Существует достаточно много последовательностей и рядов, которые сходятся к числу Пи или приближенно равны данной константе. Это ряд Грегори-Лейбница, ряд Мадхавы, ряд Нилаканта, формулы Эйлера и Валлиса и др. [19, 20].

1. Ряд Грегори-Лейбница имеет вид

Необходимо выяснить, какой из указанных рядов быстрее будет сходиться к числу Пи и сколько слагаемых (множителей для формулы Валлиса) необходимо вычислить, чтобы точность была больше 10-10, а также определить и сравнить время вычислений при обычном программировании и использовании технологии OpenMP.

Для решения данной задачи проведем расчеты в среде Visual Studio с помощью языка программирования С++ и технологии параллельного программирования OpenMP. Далее сравним полученные результаты по нескольким характеристикам. Во-первых, определим, получились ли одинаковые результаты вычисления числа Пи при решении в данном случае и в работе, когда для расчетов использовалась среда Free Pascal [20]. Во-вторых, если значения суммы ряда различны, сделаем вывод об изменении скорости сходимости. И, в-третьих, сравним результаты вычислений и время работы программы для вычисления числа Пи в С++ без использования технологии параллельного программирования и с применением ее (в частности использованием технологии OpenMP).

Результаты

После разработки алгоритмов вычисления числа Пи по формулам (1)-(5) был написан код, позволяющий реализовать технологию OpenMP.

Листинг кода вычисления числа Пи с помощью технологии OpenMP (метод Грегори-Лейбница)

#include "stdafx.h"

#include <iostream>

#include <omp.h> void task_1(int n)

{

double pi = 0; double start, end; start = omp_get_wtime();

#pragma omp parallel reduction(+:pi)

{

#pragma omp for

for (int i = 0; i < n; i++)

{

pi = pi + 4.0 * pow(-1, i) / (2.0 * i + 1.0);

}

}

end = omp_get_wtime();

printf("Значение pi для первых %d слагаемых по формуле Грегори- Лейбница: %.10f\n",

n , pi);

printf("Время по формуле Грегори-Лейбница: %.6f \n", endstart);

}

int main()

{

setlocale(LC_ALL, "Russian");

for (int i = 10; i <= 1000000; i = i * 10)

{

task_1(i);

}

return 0;

}

1. Проведем расчеты и вычислим число Пи в С++ с точностью до 10-10 методом Грегори-Лейбница, найдем и сравним абсолютную и относительную ошибки (табл. 1).

Таблица 1 Вычисление числа Пи методом Грегори-Лейбница в С++

Примечание. * - здесь и далее результаты вычислений взяты из работы [20].

Как видно, метод Грегори-Лейбница даже при п = 106 слагаемых не дает результат, верный с точностью 10-1 . Абсолютная ошибка >10 , относительная ~ 0,0001 %.

Значения числа Пи, полученные по данной формуле, без использования технологии параллельного программирования и с ее использованием получились одинаковыми. Такое будет наблюдаться и при вычислениях по другим формулам (2)-(5).

Значение времени при обычных вычислениях, начиная со значения п = 100, непрерывно растет, что объясняется увеличением числа слагаемых (табл. 2).

При параллельных вычислениях наблюдается та же тенденция. Так как значение числа Пи не достигло требуемой точности, в дальнейшем анализировать время, затраченное на вычисления, нет смысла: результат не удовлетворяет заявленной точности.

Таблица 2 Сравнение времени вычисления числа Пи методом Грегори-Лейбница

Можно только заметить, что вычисления с использованием технологии параллельного программирования до п = 106 занимают больше времени, чем обычные методы. А видимый эффект достигается при п = 106 и составляет - 0,03 с.

2. Рассмотрим результаты вычислений, полученные с использованием ряда Мадхавы (табл. 3). Фрагмент листинга кода, реализующий вычисление числа Пи, через ряд Мадхавы

void task_2(int n)

{

double pi = 0; double start, end; start = omp_get_wtime();

#pragma omp parallel reduction(+:pi)

{

#pragma omp for

for (int i = 0; i < n; i++)

{

pi = pi + sqrt(12) * pow(-1, i) / ((2.0 * i + 1) *

pow(3, i));

}

}

end = omp_get_wtime();

printf("Значение pi для первых %d слагаемых,используя ряд Мадхавы :%.10f\n",n, pi);

printf("Время: %.6f \n", end - start);

}

Таблица 3 Вычисление числа Пи с помощью ряда Мадхавы в C++