Yêu cầu làm việc chính xác cho thuật toán BBP?

Question

Tôi đang tìm cách tính số n chữ số thứ Pi trong môi trường bộ nhớ thấp. Vì tôi không có số thập phân có sẵn cho tôi, điều này integer-only BBP algorithm in Python đã là một điểm khởi đầu tuyệt vời. Tôi chỉ cần tính một chữ số Pi mỗi lần. Làm cách nào để xác định mức thấp nhất tôi có thể đặt D, "số chữ số của độ chính xác làm việc"?

D = 4 cho tôi nhiều chữ số chính xác, nhưng một vài chữ số sẽ bị tắt một. Ví dụ, số máy tính 393 với độ chính xác 4 cho tôi 0xafda, từ đó tôi trích xuất số 0xa. Tuy nhiên, chữ số chính xác là 0xb.

Bất kể tôi đặt D cao đến mức nào, có vẻ như việc kiểm tra đủ số chữ số sẽ tìm thấy một số mà công thức trả về giá trị không chính xác.

Tôi đã thử tăng độ chính xác khi chữ số "đóng" với chữ số khác, ví dụ: 0x3fff hoặc 0x1000, nhưng không thể tìm thấy bất kỳ định nghĩa tốt nào về "đóng"; ví dụ: tính ở số 9798 cho tôi 0x c de6, không quá gần 0xd000, nhưng chữ số chính xác là 0xd.

Bất kỳ ai cũng có thể giúp tôi tìm ra độ chính xác cần thiết để tính toán một chữ số đã cho bằng thuật toán này không?

Cảm ơn bạn,

chỉnh sửa
để tham khảo:

 
precision (D) first wrong digit 
------------- ------------------ 
3    27 
4    161 
5    733 
6    4329 
7    21139 
8+    ??? 

Lưu ý rằng tôi đang tính toán một chữ số tại một thời điểm, ví dụ:

for i in range(1,n): 
    D = 3 # or whatever precision I'm testing 
    digit = pi(i) # extracts most significant digit from integer-only BBP result 
    if(digit != HARDCODED_PI[i]): 
     print("non matching digit #%d, got %x instead of %x" % (i,digit,HARDCODED_PI[i])) 

Answer 1

Không vấn đề tôi đặt D cao đến mức nào, có vẻ như thử nghiệm đủ số lượng chữ số sẽ tìm thấy một số có công thức trả về giá trị không chính xác.

Bạn sẽ luôn gặp lỗi nếu bạn đang thử nghiệm đủ số chữ số - thuật toán không sử dụng độ chính xác tùy ý, do đó lỗi làm tròn sẽ hiển thị cuối cùng.

Lặp lại vô biên bằng ngắt khi chữ số không thay đổi sẽ khó xác định độ chính xác tối thiểu cần thiết cho một số chữ số nhất định. Đặt cược tốt nhất của bạn là xác định nó theo kinh nghiệm, lý tưởng bằng cách so sánh với một nguồn chính xác đã biết, và tăng số chữ số chính xác cho đến khi bạn nhận được kết quả phù hợp, hoặc nếu không có nguồn chính xác, hãy bắt đầu với độ chính xác tối đa của bạn Tôi đoán là 14, vì chữ số thứ 15 hầu như luôn chứa lỗi làm tròn.)

EDIT: Để chính xác hơn, thuật toán bao gồm vòng lặp - từ 0..n, trong đó n là chữ số để tính toán. Mỗi lần lặp của vòng lặp sẽ giới thiệu một số lượng lỗi nhất định. Sau khi lặp lại đủ số lần, lỗi sẽ xâm phạm vào chữ số quan trọng nhất mà bạn đang tính toán, và do đó kết quả sẽ sai.

Bài viết wikipedia sử dụng 14 chữ số chính xác và điều này là đủ để tính đúng 10 ** 8 chữ số. Như bạn đã thấy, ít chữ số chính xác hơn dẫn đến lỗi xảy ra trước đó, vì có ít độ chính xác và lỗi hiển thị hơn với ít lần lặp hơn.Kết quả thực là giá trị của n mà chúng ta có thể tính toán một chữ số chính xác trở nên thấp hơn với ít chữ số chính xác hơn.

Nếu bạn có D chữ số thập phân chính xác, đó là D * 4 bit. Với mỗi lần lặp lại, một lỗi 0.5bits được giới thiệu trong bit ít quan trọng nhất, do đó, với 2 lần lặp lại có khả năng LSB là sai. Trong quá trình tổng kết, các lỗi này được thêm vào và do đó được tích lũy. Nếu số lỗi tổng hợp đạt đến LSB trong chữ số quan trọng nhất, thì số duy nhất bạn trích xuất sẽ sai. Nói đúng ra, đó là khi N> 2 ** (D-0.75). (Đúng với một số cơ sở lôgarít.)

Thực nghiệm ngoại suy dữ liệu của bạn, có vẻ như khớp đúng là N = ~ (2 ** (2.05 * D)), mặc dù có ít datapoints nên đây có thể không phải là dự đoán chính xác .

Thuật toán BBP bạn đã chọn lặp lại và do đó sẽ mất nhiều thời gian hơn để tính toán các chữ số trong chuỗi. Để tính các chữ số 0..n, sẽ mất O(n^2) bước.

Bài viết wikipedia đưa ra một công thức để tính chữ số thứ hai không yêu cầu lặp lại, chỉ là số mũ và số hợp lý. Điều này sẽ không bị mất chính xác như thuật toán lặp và bạn có thể tính toán bất kỳ số pi nào khi cần trong thời gian không đổi (hoặc ở kiểu logarit tệ nhất, tùy thuộc vào việc thực hiện lũy thừa với mô đun), do đó, tính toán n chữ số sẽ mất O(n) thời gian có thể O (n log n).