Thực hiện công thức Bailey – Borwein – Plouffe trong C++?

Question

CHỈNH SỬA: Yêu cầu là mơ hồ và thay vì tính số thứ n của pi, chúng chỉ muốn pi đến chữ số thứ n không vượt quá giới hạn của phao vì vậy lực lượng vũ phu làm việc cho các yêu cầu.

Tôi cần tính PI chữ số thứ n và tôi muốn thử sử dụng BBP formula nhưng gặp khó khăn. Phương trình tôi gõ lên dường như không cho tôi PI một cách chính xác.

(1/pow(16,n))((4/(8 * n + 1)) - (2/(8 * n + 4)) - (1/(8 * n + 5)) - (1/(8 * n + 6))) 

Tôi đã thành công với cách tìm kiếm PI nhưng điều đó rất chính xác và việc tìm số thứ n rất khó.

(4 - (4/3) + (4/5) - (4/7)...) 

Tôi muốn tìm hiểu xem có ai có ý tưởng hay hơn về cách thực hiện điều này hoặc có thể trợ giúp phương trình BBP của tôi về những gì tôi đã làm sai?

Cảm ơn bạn,
LF4

chức năng nhưng không phải là rất chính xác cho đến khi một vài lần lặp và sau đó bạn phải disreguard vài ngoái.

#include <iostream> 

using namespace std; 

int main() 
{ 
    int loop_num = 0; 
    cout << "How many digits of pi do you want?: "; 
    cin >> loop_num; 

    double my_pi = 4.0; 
    bool add_check = false; 
    int den = 3; 
    for (int i = 0; i < loop_num; i++) 
    { 
     if (add_check) 
     { 
      my_pi += (4.0/den); 
      add_check = false; 
      den += 2; 
     } 
     else 
     { 
      my_pi -= (4.0/den); 
      add_check = true; 
      den += 2; 
     } 
    } 
    cout << "Calculated PI is: " << my_pi << endl; 
    system("pause"); 

    return 0; 
} 

Điều tôi hy vọng sẽ là một chương trình tốt hơn.

#include <iostream> 
#include <cmath> 

using namespace std; 

const double PI_BASE = 16.0; 

int main() 
{ 
    int loop_num = 0; 
    cout << "How many digits of pi do you want?: "; 
    cin >> loop_num; 

    double my_pi = 0.0; 
    for (int i = 0; i <= loop_num; i++) 
    { 
     my_pi += (1.0/pow(PI_BASE,i))((4.0/(8.0 * i + 1.0)) - 
              (2.0/(8.0 * i + 4.0)) - 
              (1.0/(8.0 * i + 5.0)) - 
              (1.0/(8.0 * i + 6.0))); 
    } 
    cout << "Calculated PI is: " << my_pi << endl; 
    system("pause"); 

    return 0; 
} 

Answer 1

Bất kể bạn sử dụng công thức nào, bạn sẽ cần số học chính xác tùy ý để nhận được hơn 16 chữ số. (Vì "double" chỉ có 16 chữ số chính xác).

Công thức Chudnovsky là công thức được biết đến nhanh nhất để tính toán Pi và hội tụ ở 14 chữ số cho mỗi cụm từ. Tuy nhiên, rất khó thực hiện hiệu quả.

Do tính phức tạp của công thức này, không có điểm nào trong việc sử dụng để tính Pi đến dưới vài nghìn chữ số. Vì vậy, không sử dụng nó trừ khi bạn đã sẵn sàng để đi tất cả-out với số học chính xác tùy ý.

Một triển khai mã nguồn mở tốt của Formula Chudnovsky sử dụng thư viện GMP là ở đây: http://gmplib.org/pi-with-gmp.html

Answer 2

Dường như bạn đang cố gắng để tính toán các chữ số thập phân của π khi công thức BBP được sử dụng chủ yếu để tính toán hệ thập lục phân tùy ý chữ số π Về cơ bản, công thức BBP có thể được sử dụng để tính toán n^thứ chữ số thập lục phân của π mà không cần tính toán các chữ số trước, hex chữ số 0, 1, ..., n - 1.

David H. Bailey (Bailey của Bailey – Borwein – Plouffe) đã viết C and Fortran code để tính số n^th chữ số thập lục phân của π bằng cách sử dụng công thức BBP. Trên máy có số học kép IEEE 754, chính xác đến n   ≈   1.18   × đếm từ 0; tức là π = (3.243F6A8 ...) nên đầu ra của chương trình khi n = 3 bắt đầu bằng “F”:

 
position = 3 
fraction = 0.963509103793105 
hex digits = F6A8885A30 

Tôi muốn thay đổi phiên bản C hơi để n (tên id trong mã) có thể bị ghi đè bởi đối số dòng lệnh:

 
--- piqpr8.c.orig 2011-10-08 14:54:46.840423000 -0400 
+++ piqpr8.c 2011-10-08 15:04:41.524437000 -0400 
@@ -14,14 +14,18 @@ 
/* David H. Bailey  2006-09-08 */ 

#include <stdio.h> 
+#include <stdlib.h> 
#include <math.h> 

-main() 
+int main(int argc, char *argv[]) 
{ 
    double pid, s1, s2, s3, s4; 
    double series (int m, int n); 
    void ihex (double x, int m, char c[]); 
    int id = 1000000; 
+ if (argc == 2) { 
+ id = atoi(argv[1]); 
+ } 
#define NHX 16 
    char chx[NHX]; 

@@ -36,6 +40,8 @@ 
    ihex (pid, NHX, chx); 
    printf (" position = %i\n fraction = %.15f \n hex digits = %10.10s\n", 
    id, pid, chx); 
+ 
+ return EXIT_SUCCESS; 
} 

void ihex (double x, int nhx, char chx[]) 

Answer 3

Công thức BBP không phù hợp để dễ dàng tìm chữ số thập phân thứ n vì nó dễ dàng trả về hex và chỉ có chữ số hex. Vì vậy, để tính toán lại thành số thập phân, bạn sẽ cần phải thu thập tất cả các chữ số hex.

Nó là tốt hơn để sử dụng Newton công thức:

Pi/2 = 1 + 1/3 + 1 * 2/3 * 5 + 1 * 2 * 3/3 * 5 * 7 + ... n!/(2n + 1) !! + ....

Nó sụp đổ để chương trình Horner:

Pi/2 = 1 + 1/3 * (1 + 2/5 * (1 + 3/7 * (1 + .... .. n/(2n + 1) * (1) .....)))

Vì vậy, bạn có Pi được viết như một chuỗi vị trí trong đó trên mỗi vị trí phân đoạn bạn có cơ sở khác nhau được sử dụng (n/(2n + 1)), và tất cả các chữ số bằng 2. Nó rõ ràng hội tụ, như cơ sở đó là ít hơn 1/2, vì vậy để tính toán Pi lên đến n số thập phân đáng kể dgits bạn không cần nhiều hơn log_2 (10) * n điều khoản (N = 10 * n/3 + 1 là công cụ hoàn hảo).

Bạn bắt đầu với các mảng của các yếu tố số nguyên N, tất cả bằng 2, và lặp đi lặp lại, n lần, làm như sau:

1.) Nhân tất cả các yếu tố của 10

2.) Tính toán lại mỗi phần tử [k] (từ N xuống 1) để có "chữ số" ít hơn thì mẫu số (2 * k + 1),
nhưng đồng thời bạn cần di chuyển qoutient sang vị trí bên trái, như vậy:
q = phần tử [k]/(2 * k + 1);
phần tử [k]% = (2 * k + 1);
phần tử [k-1] + = q * k; // k là bộ đếm, vì vậy đừng để nhân lên.

3.) lấy phần tử [0]. Nó bằng 10 * chữ số đầu tiên, vì vậy bạn cần xuất phần tử [0]/10 và lưu trữ
phần tử [0]% = 10;

NHƯNG có một đầu mối: tổng tối đa cho các chữ số tối đa có thể (2 * n) của công thức Newton là 2. Vì vậy, bạn có thể nhận được nhiều nhất là 19/10 từ phần tử [1]. Khi thêm vào phần tử [0] (nhân với 10 ở bước 1.), bạn có thể nhận được 90 + 19 = 109. Vì vậy, đôi khi nó xảy ra số đầu ra sẽ là [10]. Trong trường hợp này bạn biết, chữ số đúng là 0 và số 1 phải được thêm vào số đã xuất trước đó.

Có hai cách để giải quyết vấn đề này:

1.) Không xuất số cuối cùng cho đến khi số tiếp theo được tính. Hơn nữa, lưu trữ số lượng nines liên tiếp và xuất chúng dưới dạng nines hoặc 1 theo sau bởi số không phụ thuộc vào số không 9 chữ số đầu tiên.

2.) Đặt số đã nhập vào mảng kết quả, vì vậy bạn có thể dễ dàng thêm 1 nếu xảy ra [10].

Trên PC của tôi, tôi có thể tính toán (bằng Java) 10.000 chữ số thập phân trong 10 giây. Độ phức tạp là O (n^2).

Giá trị của phần tử [k] không bao giờ vượt quá 12 * k, do đó, sử dụng loại dài 64 bit trên máy nhanh, bạn có thể tính toán hơn 10^15 chữ số (khoảng rất mạnh).