首页 » Math » 最简单的任意精度Pi程序

最简单的任意精度Pi程序

作者: lesca 分类: Math 发布时间: 2011-10-05 18:11 ė浏览 2,833 次 6Comments Off on 最简单的任意精度Pi程序

一、公式

二、代码

[cpp]
#include <iostream>
#include <stdlib.h>
#define TAIL 10

using namespace std;

void output(int *num, int len) {
cout << num[0] << ‘.’ << endl;
for (int i = 1; i < len; i++) {
cout << num[i];
if (!(i % 50)) cout << " : " << i << endl;
if (!(i % 500)) cout << endl;
if (!(i % 10) && (i % 50)) cout << ‘ ‘;
}
cout << endl;
}

int main(int argc, char *argv[]) {
int a = 1, len, reg, carry;
int decimal;
int *t, *pi;
int eps = 0; // precision

if (argc != 2) {
cout << "Usage: " << argv[0] << " num_of_digits" << endl;
exit(EXIT_FAILURE);
}
decimal = atoi(argv[1]);
len = decimal + TAIL;

t = new int[len];
pi = new int[len];

cout << "Now we start calculate the value of Pi, please wait…" << endl;

for (int i = 0; i < len; i++) {
pi[i] = 0;
t[i] = 0;
}

pi[0] = 2;
t[0] = 2;

while (eps < len – 1) {
carry = 0;
for (int i = len – 1; i >= 0; i–) // t = t * a;
{
reg = t[i] * a + carry;
t[i] = reg % 10;
carry = reg / 10;
}

carry = 0;
for (int i = 0; i < len; i++) // t = t / (2a + 1)
{
reg = t[i] + carry * 10;
t[i] = reg / (2 * a + 1);
carry = reg % (2 * a + 1);
}

carry = 0;
for (int i = len – 1; i >= 0; i–) // pi = pi + t;
{
reg = pi[i] + t[i] + carry;
pi[i] = reg % 10;
carry = reg / 10;
}

// check precision
for (int i = 1; i < len; i++) {
if (t[i]) {
eps = i;
break;
}
}
a++;

}

output(pi, decimal);

delete[] t;
delete[] pi;
return 0;
}

[/cpp]

三、测试

$ time ./pi 1000
Now we start calculate the value of Pi, please wait...
Pi = 3.
1415926535 8979323846 2643383279 5028841971 6939937510 : 50
5820974944 5923078164 0628620899 8628034825 3421170679 : 100
8214808651 3282306647 0938446095 5058223172 5359408128 : 150
4811174502 8410270193 8521105559 6446229489 5493038196 : 200
4428810975 6659334461 2847564823 3786783165 2712019091 : 250
4564856692 3460348610 4543266482 1339360726 0249141273 : 300
7245870066 0631558817 4881520920 9628292540 9171536436 : 350
7892590360 0113305305 4882046652 1384146951 9415116094 : 400
3305727036 5759591953 0921861173 8193261179 3105118548 : 450
0744623799 6274956735 1885752724 8912279381 8301194912 : 500

9833673362 4406566430 8602139494 6395224737 1907021798 : 550
6094370277 0539217176 2931767523 8467481846 7669405132 : 600
0005681271 4526356082 7785771342 7577896091 7363717872 : 650
1468440901 2249534301 4654958537 1050792279 6892589235 : 700
4201995611 2129021960 8640344181 5981362977 4771309960 : 750
5187072113 4999999837 2978049951 0597317328 1609631859 : 800
5024459455 3469083026 4252230825 3344685035 2619311881 : 850
7101000313 7838752886 5875332083 8142061717 7669147303 : 900
5982534904 2875546873 1159562863 8823537875 9375195778 : 950
1857780532 1712268066 1300192787 6611195909 216420198

real	0m5.230s
user	0m0.184s  //用户空间的CPU时间
sys	0m0.000s

四、分析

1.逼近过程

下表展示了临时变量t以及待求变量pi随自变量a的迭代变化过程。
可见,随着t越来越小,pi也越来越精确。

pi 与 t 在20位精度下随变量a的变化
a pi t pi + t
1 2.0000000000 000000000 0.6666666666 666666666 2.6666666666 666666666
2 2.6666666666 666666666 0.2666666666 666666666 2.9333333333 333333333
3 2.9333333333 333333333 0.1142857142 857142857 3.0476190476 190476190
4 3.0476190476 190476190 0.0507936507 936507936 3.0984126984 126984126
5 3.0984126984 126984126 0.0230880230 880230880 3.1215007215 007215007
6 3.1215007215 007215007 0.0106560106 560106560 3.1321567321 567321567
7 3.1321567321 567321567 0.0049728049 728049728 3.1371295371 295371295
8 3.1371295371 295371295 0.0023401435 166141048 3.1394696806 461512343
9 3.1394696806 461512343 0.0011084890 341856286 3.1405781696 803368629
10 3.1405781696 803368629 0.0005278519 210407755 3.1411060216 013776385
11 3.1411060216 013776385 0.0002524509 187586317 3.1413584725 201362703
12 3.1413584725 201362703 0.0001211764 410041432 3.1414796489 611404135
13 3.1414796489 611404135 0.0000583442 123353282 3.1415379931 734757417
14 3.1415379931 734757417 0.0000281661 714722274 3.1415661593 449479692
15 3.1415661593 449479692 0.0000136287 926478519 3.1415797881 375958211
16 3.1415797881 375958211 0.0000066078 994656252 3.1415863960 370614463
17 3.1415863960 370614463 0.0000032095 511690179 3.1415896055 882304643
18 3.1415896055 882304643 0.0000015614 032714141 3.1415911669 915018784
19 3.1415911669 915018784 0.0000007606 836450479 3.1415919276 751469264
20 3.1415919276 751469264 0.0000003710 651927062 3.1415922987 403396327
21 3.1415922987 403396327 0.0000001812 178848100 3.1415924799 582244427
22 3.1415924799 582244427 0.0000000885 954103515 3.1415925685 536347943
23 3.1415925685 536347943 0.0000000433 552008103 3.1415926119 088356046
24 3.1415926119 088356046 0.0000000212 352003969 3.1415926331 440360015
25 3.1415926331 440360015 0.0000000104 094119592 3.1415926435 534479608
26 3.1415926435 534479608 0.0000000051 065039800 3.1415926486 599519408
27 3.1415926486 599519408 0.0000000025 068292265 3.1415926511 667811674
28 3.1415926511 667811674 0.0000000012 314248832 3.1415926523 982060506
29 3.1415926523 982060506 0.0000000006 052766375 3.1415926530 034826881
30 3.1415926530 034826881 0.0000000002 976770348 3.1415926533 011597230
31 3.1415926533 011597230 0.0000000001 464760012 3.1415926534 476357242
32 3.1415926534 476357242 0.0000000000 721112621 3.1415926535 197469864
33 3.1415926535 197469864 0.0000000000 355174873 3.1415926535 552644737
34 3.1415926535 552644737 0.0000000000 175013705 3.1415926535 727658443
35 3.1415926535 727658443 0.0000000000 086274361 3.1415926535 813932805
36 3.1415926535 813932805 0.0000000000 042546260 3.1415926535 856479066
37 3.1415926535 856479066 0.0000000000 020989488 3.1415926535 877468554
38 3.1415926535 877468554 0.0000000000 010358448 3.1415926535 887827003
39 3.1415926535 887827003 0.0000000000 005113664 3.1415926535 892940668
40 3.1415926535 892940668 0.0000000000 002525266 3.1415926535 895465934

2.时间复杂度

由以下图表可以看出,时间复杂度为O(n^2)
n<1000

n>1000

本文出自 Lesca技术宅,转载时请注明出处及相应链接。

本文永久链接: https://lesca.me/archives/arbitrary-precision-pi-program.html

Ɣ回顶部