Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Tính số Pi song song

Thành viên nhóm 5-Ca 2

Mục lục

Giới thiệu số Pi

Giới thiệu

Định nghĩa

Định nghĩa

p = 3,141592653589793238462643383279

• Số Pi là tên của chữ thứ 16 của mẫu tự Hy lạp. Nó được định nghĩa như một hằng số, là tỷ số giữa chu vi vòng tròn với đường kính của nó.

• Tên pi do chữ peripheria (perijeria) có nghĩa là chu vi của vòng tròn.

• Nhưng nó không có tên chính xác, thường người ta gọi là p, c, hay pi

• Chữ p được dùng vào khoảng giữa thế kỷ thứ 18, sau khi Euler xuất bản cuốn chuyên luận phân tích năm 1748. Ý định dùng ký hiệu p là để tưởng nhớ đến những nhà Toán học Hy Lạp là những người tìm ra đầu tiên con số gần đúng của pi

• Cuối thế kỷ thứ 20 số p đã tính với độ chính xác tới con số thứ 200 tỉ (200 000 000 000)

• 11 tháng 9 năm 2000: con số lẻ thứ một triệu tỉ (1.000.000.000.000.000) là số không

Định nghĩa đơn giản nhất mà người ta cho con số nổi tiếng này là: nó là tỷ số giữa diện tích dĩa tròn và bình phương bán kính

Các phương pháp tính số Pi

Các phương pháp tính số Pi

- Thời kì của phép xấp xỉ đa giác

- Các chuỗi số vô hạn

  • Pháp François Viète năm 1593:

  • Công thức Madhava được khám phá lại bởi nhà toán học Scotland James Gregory năm 1671, và bởi Leibniz năm 1674

  • Năm 1706 John Machin sử dụng chuỗi Gregory-Leibniz để tạo nên một thuật toán hội tụ nhanh hơn nhiều

Tốc độ hội tụ

- Một chuỗi vô hạn cho π là chuỗi Gregory-Leibniz

- Một chuỗi vô hạn cho π được công bố bởi Nilakantha vào thế kỷ XV hội tụ nhanh hơn nhiều chuỗi Gregory-Leibniz

- So sánh 2 chuỗi vô hạn trên:

Tính vô tỉ và tính siêu việt

- Khi Euler giải Bài toán Basel vào năm 1735, tìm ra giá trị chính xác của tổng các căn bậc hai, ông đã thiết lập một mối liên hệ giữa π và các số nguyên tố mà về sau góp phần vào sự phát triển và nghiên cứu hàm Riemann zeta

Hình học và lượng giác

- Chu vi của một đường tròn với bán kính r là

- Diện tích của một hình tròn với bán kính r là

- Thể tích của một hình cầu với bán kính r là

- Diện tích mặt cầu với bán kính r là

- π xuất hiện trong các tích phân xác định mô tả chu vi, diện tích, hoặc thể tích các hình tạo ra từ đường tròn. Chẳng hạn, một tích phân xác định nửa diện tích của một đường tròn với bán kính bằng 1 được cho bởi

Tính số Pi tuần tự

Tính số Pi theo hướng tuần tự

Bài toán theo hướng tuần tự

Giải bài toán theo hướng tuần tự

- Được chạy trên máy tính đơn với một bộ xử lý trung tâm (CPU)

- Bài toán sẽ được chia thành môt chuỗi câu lệnh rời rạc

- Các câu lệnh được thực hiện một cách tuần tự

- Tại một thời điểm chỉ thực hiện được một câu lệnh

Thuật toán

Giải bài toán theo hướng tuần tự

Bài toán

Có rất nhiều công thức để tính số Pi, và công thức giản dị nhất được Leibniz tìm ra năm 1674 là:

p/4 = 1 – 1/3 + 1/5 – 1/7 + …

được chúng em áp dụng để tính số pi tuần tự

Giải bài toán theo hướng tuần tự

Mã giả

begin

pi=1;

i=1;

cin>>epsilon

while(1.0/(2*i+1)>=epsilon)

{

pi=pi+pow(-1/i)/(2*i+1);

i++;

}

end

Source code

Source code

#include<math.h>

#include<iomanip>

#include<iostream>

using namespace std;

int main()

{

double pi=1,epsilon;

double i=1;

cout<<”nhap sai so: “;

cin>>epsilon;

while (1.0/(2*i+1)>=epsilon)

{

pi=pi+pow(-1,i)/(2*i+1);

i++;

}

cout<<”so pi: “<<std::setprecision(9)<<pi*4;

cout<<"\nSo lan thuc hien vong lap: "<<i-1;

}

}

Tính số Pi Song song

Tính số Pi theo hướng song song

Tính toán song song

Tính toán song song

Quá trình tính toán gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia tính toán giải quyết cùng một công việc và thực hiện trên các hệ thống đa bộ ủ lý

OpenMP trong C++

- OpenMP bao gồm một tập các chỉ dẫn biên dịch #pragma nhằm chỉ dẫn cho chương trình hoạt động. Các pragma được thiết kế nhằm mục đích nếu các trình biên dịch không hỗ trợ thì chương trình vẫn có thể hoạt động bình thường, nhưng sẽ không có bất kỳ tác vụ song song nào được thực hiện như khi sử dụng OpenMP

- Chỉ khi trình biên dịch được biên dịch với #pragma, nó trở thành một chương trình chạy song song. Nó có thể thực hiện tính toán N giá trị đồng thời với N là số thread thực hiện.

- Tất cả các chỉ dẫn OpenMP trong C/C++ đều được dùng thông qua #pragma omp theo sau là các thông số và kết thúc bằng một ký hiệu xuống dòng. #pragma chỉ được áp dụng vào đoạn chương trình ngay sau nó, ngoại trừ lệnh barrier và flush

- Chỉ dẫn parrallel bắt đầu một đoạn code thực hiện song song. Nó tạo ra một team bao gồm N threads (N được chỉ định tại thời điểm chạy chương trình, thông thường bằng số nhân CPU, nhưng có thể bị ảnh hưởng bởi một số lý do khác), các lệnh xử lý tiếp theo ngay sau #pragma hoặc block tiêp theo (trong giới hạn {}) sẽ được thực hiện song song. Sau đoạn xử lý này, các thread sẽ được join lại về một

Thuật toán

Thuật toán

Mã giả

begin

input stepcounter

decralations i, pi

for i=0 to stepcounter

pi=pi+1.0/(i*4.0+1.0)

pi=pi-1.0/(i*4.0+1.0)

end for

pi=pi*4.0

output pi

end

Source code

Source code

// ConsoleApplication1.cpp : Defines the entry point for the console application.

//

/*pi_openmp.c (OpenMP version)*/

#

#include "stdafx.h"

#include<omp.h>

#include<iostream>

#include<conio.h>

#include<stdio.h>

#include<math.h>

#include<iomanip>

#define numscount 10000

using namespace std;

int main()

{

clock_t start = clock();

long i;

double pi = 0;

omp_set_num_threads(2);

#pragma omp parallel for reduction(+: pi)

for (i = 0; i < numscount; i++) {

cout << "\n" << omp_get_thread_num();

pi += 1.0 / (i*4.0 + 1.0);

pi -= 1.0 / (i*4.0 + 3.0);

/*cout << omp_get_num_threads();*/

cout << "\n" << omp_get_thread_num();

}

pi = pi*4.0;

cout << "\nPi = " <<std::setprecision(10)<<pi;

clock_t finish = clock();

cout << "\n Thoi gian chay: " << (double)finish - start;

getch();

return 0;

}

Bài học

After

Bài học

- Áp dụng được kiến thức đã học áp dụng vào bài toán tính sô pi

- Tìm hiểu thêm về những kiến thức để tính số Pi bằng OpenMP trong C++

A

Q

&

Để lại câu hỏi nếu bạn còn thắc mắc về bà thuyết trình của nhóm mình nhé

Q&A

Thank you

Learn more about creating dynamic, engaging presentations with Prezi