Вычисление числа Пи. Мирошник Глеб. 6 курс — различия между версиями

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск
(Для суммирования ряда)
 
(не показано 5 промежуточных версий этого же участника)
Строка 9: Строка 9:
 
:<math>\frac{\pi}{4}</math>.
 
:<math>\frac{\pi}{4}</math>.
 
Также данный ряд можно получить разложением арктангенса 1 в ряд Тейлора, что даёт нам возможность оценить число π вычислением определённого интеграла
 
Также данный ряд можно получить разложением арктангенса 1 в ряд Тейлора, что даёт нам возможность оценить число π вычислением определённого интеграла
:<math>\int\limits_0^1 \frac{1}{1+x^{2}}\,dx = frac{\pi}{4}</math>
+
:<math>\int\limits_0^1 \frac{1}{1+x^{2}}\,dx = \frac{\pi}{4}</math>
 
 
  
 
==Предлагаемое решение==
 
==Предлагаемое решение==
Строка 166: Строка 165:
  
 
==Компьютерная реализация==
 
==Компьютерная реализация==
 +
[[:File:CompTech.rar|Оценка числа π]]
  
 
+
==Результаты (при 10млн итераций)==
==Результаты==
+
===Для суммирования ряда===
 
{| class="wikitable" width="300" floating="center"
 
{| class="wikitable" width="300" floating="center"
 
!Количество процессов
 
!Количество процессов
!Время рассчета (сек)
+
!Ошибка вычисления
 +
!Время расчёта (сек)
 
|-
 
|-
 
|1  
 
|1  
|184.2
+
|33.02161870037517132914
 +
|1.757
 
|-
 
|-
 
|2
 
|2
|91.6
+
|0.00000010000398731336
 +
|0.979
 
|-
 
|-
|5
+
|3
|39.4
+
|10.37762764928963399313
 +
|0.750
 +
|-
 +
|4
 +
|0.00000009999904815317
 +
|0.727
 +
|}
 +
===Для интегрирования===
 +
{| class="wikitable" width="300" floating="center"
 +
!Количество процессов
 +
!Ошибка вычисления
 +
!Время расчёта (сек)
 
|-
 
|-
|10
+
|1
|19.2
+
|0.00000000000006217249
 +
|0.246
 
|-
 
|-
|20
+
|2
|9.9
+
|0.00000000000019184654
 +
|0.144
 
|-
 
|-
|30
+
|3
|8.1
+
|0.00000000000011946000
 +
|0.128
 
|-
 
|-
|40
+
|4
|7.5
+
|0.00000000000010702550
 +
|0.112
 
|}
 
|}
  
 
==Выводы==
 
==Выводы==
* Для малого числа узлов в сетке использовать многопроцессорные вычисления не выгодно: время работы программы увеличивается.
+
* При увеличении количества процессов сокращается время выполнения программы, но относительный выигрыш по времени уменьшается.
* При увеличении числа процессоров относительный выигрыш во времени уменьшается.
+
* Интегрирование при одинаковом количестве итераций даёт более точный результат, а так же результат интегрирующей программы не зависит от количества процессов (при запуске программы с чётным количеством процессов появляется ошибка больше 100%).
 
+
* Ошибка вычисления при интегрировании связана с ограниченным количеством символов типа double; ошибка вычисления при суммировании может быть уменьшена увеличением количества элементов ряда.
==Полезные ссылки==
 
[https://ru.wikipedia.org/wiki/%D0%A3%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D1%82%D0%B5%D0%BF%D0%BB%D0%BE%D0%BF%D1%80%D0%BE%D0%B2%D0%BE%D0%B4%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Уравнение теплопроводности]
 

Текущая версия на 16:07, 19 января 2017

Цель[править]

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

Постановка задачи[править]

Лейбниц доказал, что ряд

[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 считать элементы последовательно каждым процессором, "перепрыгивая" через количество процессов, занятых в расчёте. Начальный рассчитываемый номер ряда определяется порядковым номером процесса. Рассчитанный элемент добавляется к сумме внутри процесса. После окончания расчёта предварительные суммы "скидываются" в нулевой процесс и суммируются между собой. Таймер останавливается. Происходит вычисление ошибки по эталонному значению числа π и вывод информации о расчёте.

Численным вычислением определённого интеграла[править]

Численное вычисление интеграла предлагается проводить методом прямоугольников. Сам же процесс будет аналогичен решению суммированием элементов ряда.

Листинг программ[править]

Для суммирования ряда[править]

#include "stdafx.h" #include <iostream> #include "mpi.h" #include <math.h> #include <time.h> using namespace std; #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);

} }

Для вычисления интеграла[править]

#include "stdafx.h" #include <iostream> #include "mpi.h" #include <math.h> #include <time.h> using namespace std; #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);

} }

Компьютерная реализация[править]

Оценка числа π

Результаты (при 10млн итераций)[править]

Для суммирования ряда[править]

Количество процессов Ошибка вычисления Время расчёта (сек)
1 33.02161870037517132914 1.757
2 0.00000010000398731336 0.979
3 10.37762764928963399313 0.750
4 0.00000009999904815317 0.727

Для интегрирования[править]

Количество процессов Ошибка вычисления Время расчёта (сек)
1 0.00000000000006217249 0.246
2 0.00000000000019184654 0.144
3 0.00000000000011946000 0.128
4 0.00000000000010702550 0.112

Выводы[править]

  • При увеличении количества процессов сокращается время выполнения программы, но относительный выигрыш по времени уменьшается.
  • Интегрирование при одинаковом количестве итераций даёт более точный результат, а так же результат интегрирующей программы не зависит от количества процессов (при запуске программы с чётным количеством процессов появляется ошибка больше 100%).
  • Ошибка вычисления при интегрировании связана с ограниченным количеством символов типа double; ошибка вычисления при суммировании может быть уменьшена увеличением количества элементов ряда.