Редактирование: Вычисление числа Пи. Мирошник Глеб. 6 курс

==Цель==
Оценить число π при помощи знакочередующегося ряда Лейбница двумя способами: суммированием и интегрированием. Разработать программу для параллельных вычислений. Оценить скорость вычислений в зависимости от количества задействованных процессоров.
 
==Постановка задачи==

Лейбниц доказал, что ряд 
:<math>1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\frac{1}{13}-\cdot\cdot\cdot=\sum^{\infty}_{n=1} {\frac{(-1)^{n}}{2n+1}}</math>
равен
:<math>\frac{\pi}{4}</math>.
Также данный ряд можно получить разложением арктангенса 1 в ряд Тейлора, что даёт нам возможность оценить число π вычислением определённого интеграла
:<math>\int\limits_0^1 \frac{1}{1+x^{2}}\,dx = \frac{\pi}{4}</math>

==Предлагаемое решение==
===Суммированием элементов ряда===
После объявления переменных и инициализации MPI запускается счётчик времени.
Предлагается при фиксированном количестве элементов ряда n считать элементы последовательно каждым процессором, "перепрыгивая" через количество процессов, занятых в расчёте. Начальный рассчитываемый номер ряда определяется порядковым номером процесса. Рассчитанный элемент добавляется к сумме внутри процесса. После окончания расчёта предварительные суммы "скидываются" в нулевой процесс и суммируются между собой. Таймер останавливается. Происходит вычисление ошибки по эталонному значению числа π и вывод информации о расчёте.
===Численным вычислением определённого интеграла===
Численное вычисление интеграла предлагается проводить методом прямоугольников. Сам же процесс будет аналогичен решению суммированием элементов ряда.

==Листинг программ==
===Для суммирования ряда===
<code>
&#35;include "stdafx.h"
&#35;include <iostream>
&#35;include "mpi.h"
&#35;include <math.h>
&#35;include <time.h>
using namespace std;
&#35;define Iterations 10000000 //количество итераций


int main() {

	int ProcNum, ProcRank, i;

	double x, MyPi = 0;

	double Sum = 0;

	double TotalTime;

	clock_t StartClock, EndClock; // объявляем стартовую и конечную переменную таймера и инициализируем стартовую переменную

	StartClock = clock();

	MPI_Init(NULL, NULL); // инициализируем MPI 

	MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); // записываем количество процессов с переменную ProcNum

	MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); // записываем номер процесса в переменную ProcRank

	for (i = ProcRank; i < Iterations; i += ProcNum)  

	{

		x = pow(-1,ProcRank)*4/(2*i + 1);

Sum += x;

	}

	MPI_Reduce(&Sum, &MyPi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); // пердварительные суммы Sum в переменную MyPi

	MPI_Finalize(); // завершаем работу MPI

	if (ProcRank == 0)

	{


		EndClock = clock(); // останавливаем таймер и переходим к выводу результатов на экран

		printf("Number of iterations = %i\n", Iterations);

		printf("Obtained value of Pi = %3.20f\n", MyPi);

		double pi = 3.1415926535897932384626433832795;

		printf("Refrence value of Pi = %3.20f\n", pi);

		printf("Error = %3.20f\n", abs(MyPi - pi));

		TotalTime = (double)(EndClock - StartClock) / CLOCKS_PER_SEC;

		printf("Computing time = %f sec\n", TotalTime);

	}
}

</code>

===Для вычисления интеграла===
<code>
&#35;include "stdafx.h"
&#35;include <iostream>
&#35;include "mpi.h"
&#35;include <math.h>
&#35;include <time.h>
using namespace std;
&#35;define Iterations 10000000 //количество итераций


int main() {

	int ProcNum, ProcRank, i;

	double x, MyPi = 0;

	double Sum = 0;

	double TotalTime;

	clock_t StartClock, EndClock; // объявляем стартовую и конечную переменную таймера и инициализируем стартовую переменную

	StartClock = clock();

	MPI_Init(NULL, NULL); // инициализируем MPI 

	MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); // записываем количество процессов с переменную ProcNum

	MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); // записываем номер процесса в переменную ProcRank

	double h = 1.0 / Iterations;

	for (i = ProcRank; i < Iterations; i += ProcNum) // вычисляем численно интеграл по методу прямоугольников 

	{

		x = (i + 0.5) * h;

		Sum += 4.0 / (1 + x*x); // (после общего суммирования надо будет разделить на количество итераций)

	}

	MPI_Reduce(&Sum, &MyPi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD); // пердварительные суммы Sum в переменную MyPi

	MPI_Finalize(); // завершаем работу MPI

	if (ProcRank == 0)

	{

		MyPi *= h; //делим сумму на количество итераций

		EndClock = clock(); // останавливаем таймер и переходим к выводу результатов на экран

		printf("Number of iterations = %i\n", Iterations);

		printf("Obtained value of Pi = %3.20f\n", MyPi);

		double pi = 3.1415926535897932384626433832795;

		printf("Refrence value of Pi = %3.20f\n", pi);

		printf("Error = %3.20f\n", abs(MyPi - pi));

		TotalTime = (double)(EndClock - StartClock) / CLOCKS_PER_SEC;

		printf("Computing time = %f sec\n", TotalTime);

	}
}

</code>

==Компьютерная реализация==
[[:File:CompTech.rar|Оценка числа π]]

==Результаты==
{| class="wikitable" width="300" floating="center"
!Количество процессов
!Время рассчета (сек)
|-
|1 
|184.2
|-
|2
|91.6
|-
|5
|39.4
|-
|10
|19.2
|-
|20
|9.9
|-
|30
|8.1
|-
|40
|7.5
|}

==Выводы==
* При увеличении количества процессов сокращается время выполнения программы, но относительный выигрыш по времени уменьшается.
* Интегрирование при одинаковом количестве итераций даёт более точный результат, а так же результат интегрирующей программы не зависит от количества процессов (при запуске программы с чётным количеством процессов появляется ошибка больше 100%).
* Ошибка вычисления при интегрировании связана с ограниченным количеством символов типа double; ошибка вычисления при суммировании может быть уменьшена увеличением количества элементов ряда.
@@ Строка 167: / Строка 167: @@
 [[:File:CompTech.rar|Оценка числа π]]
-==Результаты (при 10млн итераций)==
+==Результаты==
-===Для суммирования ряда===
 {| class="wikitable" width="300" floating="center"
 !Количество процессов
-!Ошибка вычисления
+!Время рассчета (сек)
-!Время расчёта (сек)
 |-
 |1
-|33.02161870037517132914
+|184.2
-|1.757
 |-
 |2
-|0.00000010000398731336
+|91.6
-|0.979
 |-
-|3
+|5
-|10.37762764928963399313
+|39.4
-|0.750
 |-
-|4
+|10
-|0.00000009999904815317
+|19.2
-|0.727
-|}
-===Для интегрирования===
-{| class="wikitable" width="300" floating="center"
-!Количество процессов
-!Ошибка вычисления
-!Время расчёта (сек)
 |-
-|1
+|20
-|0.00000000000006217249
+|9.9
-|0.246
-|-
-|2
-|0.00000000000019184654
-|0.144
 |-
-|3
+|30
-|0.00000000000011946000
+|8.1
-|0.128
 |-
-|4
+|40
-|0.00000000000010702550
+|7.5
-|0.112
 |}