Arctangent formulas for PI

What is a reasonable way to compute Pi? Methods that have been chosen for
many of the groundbreaking digitstorms in the past have been based on
arctangent formulae.

First it should be made clear that we are trying to compute to thousands or
millions of decimal places, so we cannot simply "ask the computer" for a
function evaluation like arccos(-1). It cannot supply that to a million
places of decimals, and if it can, it is by methods such as those outlined
here.

Arithmetic at the million-decimal level of accuracy is actually just like
the stuff you learned in grade school. You store a number by storing its
digits in an array of integers, doing things like "carry" explicitly. The
only difference is using base 10000 or so rather than base 10.

We may start with the power series expansion for arctangent:

     arctan x = x - x**3/3 + x**5/5 - x**7/7 - ...

This series converges for x less than or equal to 1. For x = 1 in
particular, we get the series that nobody except a mathematician really
believes to converge. Thus the formula

     pi/4 = arctan 1

while true, is not much use for computation (try it).

In the arctangent expansion, the terms reduce by a factor x**2 each time, so
for fastest convergence we want x small. For easy computation we want x to
be the reciprocal of an integer so that we only need to do 'short' division
(by an integer) rather than the curse of grade-school, 'long' division?

Thus an example of a more useful formula is Machin's formula:

     pi/4 = 4*arctan 1/5 - arctan 1/239

Exercise: Why is this is equivalent to the statement about complex numbers:

     (5 + i)**8 * (239 - i)**2 is a pure imaginary number

With this formula, the longest computation is the arctan 1/5 term, where the
error reduces by a factor 25 for each additional term. The arctan 1/239
calculation is of course much easier since the terms decrease by 239**2 each
time.

More such formulae can be constructed using concepts of prime numbers, but
in a space of complex integers, or Gaussian integers, rather than the usual
natural numbers. With the natural numbers, there is a unique expression of
number as a product of primes, but there are many such expressions for
Gaussian integers. The upshot is that we can generate many arctangent
formulae for PI, as explained (in French) in this reference:

     Carl Stormer,
     Sur l'Application de la Theorie des Nombres Entiers Complexes a la
Solution en Nombres Rationels x1, x2, .., c1, c2, ..., k de l'Equation...
     Archiv for Mathematik og Naturvidenskab, B XIX, Nr 3 (1896), pp 75 -
85.

Here are some of the results: Each line in the list below represents a
formula for pi:

     k pi/4 = a1 arctan 1/b1 + a2 arctan 1/b2 + ...

expressed as

     k :: a1:b1 a2:b2 ...

The first column is the efficiency of the formula, proportional to the time
it takes to calculate pi with the power series for arctangent, and it is
1/ln b1 + 1/ln b2 + ... normalized to the value for Machin's Formula.

(Take me away from here)

0.856797 1 :: 44:57 7:239 -12:682 24:12943
0.882893 1 :: 22:28 2:443 -5:1393 -10:11018
0.924166 1 :: 17:23 8:182 10:5118 5:6072
0.935657 1 :: 88:172 51:239 32:682 44:5357 68:12943
0.963820 2 :: 100:73 54:239 -12:2072 -52:2943 -24:16432
0.965146 1 :: 12:18 8:57 -5:239
0.966551 1 :: 8:10 -1:239 -4:515
0.970997 1 :: 44:53 -20:443 -5:1393 22:4443 -10:11018
0.979566 1 :: 17:22 3:172 -2:682 -7:5357
0.991396 1 :: 16:20 -1:239 -4:515 -8:4030
0.991405 2 :: 61:38 -14:557 -3:1068 -17:3458 -34:27493
0.993251 1 :: 227:255 -100:682 44:2072 51:2943 -27:12943 88:16432
0.996187 1 :: 24:53 20:57 -5:239 12:4443
0.999285 1 :: 127:241 100:437 44:2072 24:2943 -12:16432 27:28800
1.000000 1 :: 4:5 -1:239
1.005359 1 :: 16:21 3:239 4:421 4:1985
1.005554 1 :: 24:36 8:57 -5:239 -12:23382
1.010113 1 :: 227:255 -56:682 -88:2059 51:2943 44:5357 -71:12943
1.010713 1 :: 127:239 200:606 -56:2072 -76:2943 -100:6118 -112:16432
1.012465 1 :: 88:111 7:239 -44:515 32:682 24:12943
1.028171 1 :: 95:239 176:660 76:682 44:2621 24:12943 -132:14942
1.031253 1 :: 56:91 15:239 44:515 32:1303 -8:2943
1.031800 1 :: 44:60 7:239 -12:682 44:1048 -20:12943
1.036348 1 :: 24:29 -4:57 7:239 -12:12238
1.036952 1 :: 56:99 27:239 20:307 24:568 -12:19703
1.037413 1 :: 139:241 88:437 -12:682 44:2072 24:12943 51:28800
1.038546 1 :: 34:53 20:172 15:682 17:4443 10:5357
1.039028 1 :: 183:255 88:606 -56:682 51:2943 -44:6118 -71:12943
1.039694 1 :: 122:162 -7:557 29:1068 22:3458 61:5087 -17:27493
1.042340 1 :: 200:187 -73:239 44:2072 24:2943 -100:13637 -12:16432
1.043526 1 :: 16:21 3:239 4:251 -4:905
1.045543 1 :: 105:172 66:682 51:882 85:4193 10:5357 -17:9466
1.046534 1 :: 127:239 100:515 200:1303 -56:2072 -176:2943 -112:16432
1.048525 1 :: 100:268 127:378 27:1526 71:2072 51:2943 115:16432
1.049039 1 :: 12:15 -1:239 -4:580 -4:1710
1.060050 1 :: 122:183 54:557 -32:1068 61:1393 22:3458 44:27493
1.060336 1 :: 139:239 88:307 -56:682 -88:4193 44:5357 156:12943
1.062471 1 :: 44:72 7:239 44:268 -12:682 -20:12943
1.065319 1 :: 44:57 -5:239 24:443 -24:1071 12:4443
1.065596 1 :: 44:68 22:117 -20:443 -5:1393 -10:11018
1.067640 1 :: 56:99 39:239 8:307 12:515 24:3323
1.068258 1 :: 44:82 56:187 -17:239 24:1068 -12:6105
1.069193 1 :: 44:82 44:187 7:239 -12:682 24:12943
1.069657 1 :: 44:83 44:182 7:239 -12:682 24:12943
1.070914 1 :: 29:68 32:117 25:327 10:1067 -10:27493
1.073428 1 :: 39:68 27:117 -10:418 5:882 -10:16693
1.074057 1 :: 51:239 132:268 32:682 44:1432 -20:12943 44:13043
1.074258 1 :: 44:107 44:122 7:239 -12:682 24:12943
1.074797 1 :: 122:319 61:378 115:557 29:1068 22:3458 44:27493
1.074850 1 :: 183:255 44:515 -56:682 88:1303 7:2943 -71:12943
1.076669 1 :: 61:64 -68:557 -32:1068 -39:3458 -61:16452 -17:27493
1.076704 1 :: 44:99 24:193 27:239 32:307 -12:20457
1.077060 1 :: 88:177 51:239 32:682 44:5357 88:6089 68:12943
1.077723 1 :: -27493:378 -173:1526 -29:2072 151:2943 -100:14318 115:16432
-100:27493
1.078021 1 :: 95:239 132:307 -56:682 44:1607 44:5928 68:12943
1.078892 1 :: 44:57 -17:239 24:343 12:1068 12:3458
1.079532 1 :: 188:187 -61:239 24:1068 44:2072 -12:6105 -88:13637
1.079620 1 :: 12:26 20:57 -5:239 -12:2057
1.080468 1 :: 176:187 -37:239 -12:682 44:2072 24:12943 -88:13637
1.080712 1 :: 127:241 100:437 -12:776 24:1068 44:2072 39:28800
1.080949 1 :: -28800:437 254:1032 -83:2072 151:2943 127:15179 -12:16432
27:28800
1.082333 1 :: -20457:327 -51:882 -10:1893 171:6898 103:18432 122:18543
-39:20457
1.084775 1 :: 83:239 132:268 -64:1458 -20:1568 -32:4443 44:4662
1.085008 1 :: 61:268 122:343 115:557 -32:1068 83:3458 44:27493
1.086637 1 :: 56:83 32:182 -17:239 12:1068 -12:2309
1.086753 1 :: 88:172 68:443 66:682 17:1393 44:5357 34:11018
1.087540 1 :: 144:187 -17:239 68:1068 44:2309 -56:6105 88:6807
1.087900 1 :: 61:82 -7:557 29:1068 61:2877 22:3458 -17:27493
1.087934 1 :: 51:239 132:268 32:682 44:1568 44:4662 -64:12943
1.088261 1 :: 139:239 132:307 -88:568 -56:682 112:12943 44:19703
1.089745 1 :: -12943:682 366:1068 139:2436 271:5357 315:5507 227:6962
-71:12943
1.090267 1 :: 51:239 132:268 32:682 44:1087 -44:6898 -20:12943
1.090315 1 :: -14942:660 171:682 139:2621 -95:5357 -190:5507 -71:12943
-227:14942
1.090327 1 :: 22:38 44:183 -20:443 17:1393 -10:11018
1.090574 1 :: 12:27 20:57 -5:239 12:1068
1.090786 1 :: 20:57 24:68 12:117 -5:239
1.091231 1 :: -28322:239 68:993 -20:2943 56:4443 -44:13252 -112:17088
156:28322
1.092533 1 :: 44:73 12:173 27:239 12:1068 -32:2943
1.093650 1 :: 100:173 27:239 100:1068 44:2072 -76:2943 88:16432
1.094472 1 :: 17:27 5:38 10:557 7:1068
1.094503 1 :: -28800:437 127:682 44:2072 278:2943 -254:12943 -139:16432
-227:28800
1.098284 1 :: 105:133 -10:418 -39:682 71:882 -27:9466 -10:16693
1.099319 1 :: 100:268 83:378 44:905 115:1057 51:2943 71:3957
1.100266 1 :: 100:177 -5:239 76:305 -32:2621 44:14942 24:16693
1.100624 1 :: 5:7 4:53 2:4443
1.101091 1 :: 61:93 54:557 -32:1068 61:1118 22:3458 44:27493
1.103478 1 :: 14942:660 266:682 -190:1432 -51:2621 -71:12943 95:13043
-132:14942
1.103627 1 :: 22:33 22:185 2:443 -5:1393 -10:11018
1.103682 1 :: 61:81 54:557 -32:1068 -61:1432 22:3458 44:27493
1.104556 1 :: 10:14 4:53 -5:1393 2:4443
1.104685 1 :: 44:57 -5:239 12:437 -12:776 24:1068
1.105132 2 :: 88:68 44:117 -30:239 20:682 -40:12943
1.105586 1 :: 16432:606 127:682 -183:2072 51:2943 -227:6118 -254:12943
-366:16432
1.106540 1 :: 28322:239 -100:993 -56:2072 -76:2943 -100:13252 -112:16432
100:28322
1.108267 1 :: 24:31 -1:239 8:580 -4:1710 12:2855
1.110847 3 :: 122:53 40:557 -35:1068 5:3458 61:4443 10:27493
1.111018 1 :: -19703:682 190:746 271:882 315:2917 -132:9466 295:12943
-95:19703
1.111617 1 :: 12943:606 127:682 234:2943 183:3740 183:5052 -44:6118
-71:12943
1.111619 1 :: 28322:682 183:788 227:843 95:2943 44:6613 -115:12943 88:28322
1.111759 1 :: 100:117 -29:239 24:993 44:2621 24:2943 44:14942
1.112213 1 :: 12:28 20:57 -5:239 12:443
1.114240 1 :: 44:73 12:117 15:239 24:993 -20:2943
1.115175 2 :: -16432:307 27:682 -139:2072 329:2943 -54:12943 227:15179
-51:16432
1.115356 1 :: 100:117 -73:239 200:993 44:2072 24:2943 88:16432
1.116305 1 :: 95:239 132:437 44:580 -12:682 44:1710 24:12943
1.116609 1 :: 16432:447 200:606 -56:2072 -76:2943 -227:6118 -127:15179
-239:16432
1.118950 1 :: 95:239 176:307 -44:515 -56:682 -88:3323 112:12943
1.118972 1 :: -28322:378 100:1407 27:1526 71:2072 151:2943 115:16432
100:28322
1.119150 1 :: 51:239 88:268 88:463 32:682 44:5357 -20:12943
1.119566 1 :: -16432:606 254:1526 127:1772 71:2072 51:2943 -227:6118
-112:16432
1.120109 1 :: -27493:378 144:606 86:1772 122:2943 -115:6118 -71:14318
-71:27493
1.121663 1 :: 66:117 44:253 24:443 -5:1393 -10:11018 -44:19283
1.122448 1 :: 12943:606 -56:682 366:2059 51:2943 -183:5357 -227:6118
-71:12943
1.123057 1 :: 71:239 100:268 24:327 52:1432 20:2621 -32:14942
1.123144 1 :: 28322:239 -100:788 -56:2072 -76:2943 100:6613 -112:16432
200:28322
1.124091 1 :: 144:192 -17:239 44:515 24:1068 -56:6105 56:7181
1.125624 1 :: 16432:239 400:1068 44:2072 -376:2943 -200:6105 100:13637
188:16432
1.126452 1 :: 28322:239 -100:785 -56:2072 24:2943 -100:5443 -112:16432
200:28322
1.127659 1 :: 22:38 34:183 10:557 -10:1068 17:1393
1.127928 1 :: 112:193 27:239 76:307 -88:568 44:19703 -56:20457
1.128424 1 :: 132:233 51:239 -44:500 76:682 -88:3793 68:12943
1.128516 1 :: -27493:378 144:905 115:1057 151:2943 -29:3957 -100:14318
-100:27493
1.129422 1 :: 27493:418 237:557 29:1068 144:3458 -61:5087 122:16452
105:27493
1.129449 1 :: 28322:239 68:788 -56:1744 36:2943 44:6613 -112:13603 144:28322
1.130886 1 :: 10:19 7:27 2:1068 -5:3458
1.130903 1 :: -21907:616 151:693 103:1032 132:3141 144:3323 39:9703
215:21907
1.131210 1 :: -16693:418 171:682 176:882 315:2917 -132:9466 105:12943
95:16693
1.131632 1 :: 95:239 88:294 44:515 32:682 -88:1929 24:12943
1.132323 1 :: 56:83 32:182 -17:239 -12:515 24:818
1.132380 1 :: 44:57 -5:239 12:268 -12:557 12:1068
1.133145 1 :: 34:68 17:117 20:172 15:682 10:5357
1.133169 1 :: -12943:682 271:882 95:993 315:2917 95:2943 -227:9466 200:12943
1.133501 1 :: 22:38 17:81 10:1407 -7:1432 -10:1818
1.134001 1 :: 54:53 -40:183 -25:1393 22:4443 -10:7078 -10:27493
1.134143 1 :: 88:182 39:239 44:515 24:818 56:4443 112:9888
1.134357 1 :: 32:57 12:193 7:239 36:268 -12:6898
1.134442 1 :: -13637:538 127:682 -37:1068 44:2072 176:6105 61:12943
-88:13637
1.134855 1 :: 28322:255 -56:682 -44:993 95:2943 -115:12943 -44:13252
44:28322
1.134957 1 :: 13043:378 215:682 44:1432 51:2943 -315:5257 -71:12943 44:13043
1.135076 1 :: -28800:437 127:580 127:1710 -83:2072 24:2943 -12:16432
154:28800
1.136246 1 :: -16432:577 -100:682 227:1393 44:2072 -176:2943 200:12943
88:16432
1.137027 1 :: -14942:660 171:682 95:993 44:2621 95:2943 -71:12943 -227:14942
1.137804 1 :: 100:112 27:239 -100:498 -56:2072 24:2943 -12:16432
1.138012 1 :: 16432:616 327:1303 254:1526 71:2072 -176:2943 100:3141
-112:16432
1.138789 2 :: 176:122 14:239 -24:682 88:1252 88:2855 48:12943
1.138921 1 :: -14942:660 171:682 95:1068 95:2436 44:2621 -71:12943
-227:14942
1.139913 1 :: 16432:682 227:788 227:843 44:2072 51:2943 -27:12943 88:16432
1.139968 1 :: -28800:437 254:577 127:1393 44:2072 24:2943 -12:16432
-100:28800
1.140434 1 :: 32:57 24:93 -5:239 -12:785 12:5443
1.141015 1 :: -12943:606 127:682 183:993 51:2943 -183:4952 -44:6118
-71:12943
1.141408 1 :: 16432:515 127:682 454:1303 -183:2072 -176:2943 -254:12943
-366:16432
1.142043 1 :: -19534:447 68:693 115:1032 95:1143 51:9703 -12:13545 144:19534
1.142373 1 :: 27493:183 108:1177 29:1393 22:4443 54:5087 -64:7078 -10:27493
1.142451 1 :: -12943:538 127:682 51:1068 44:2309 88:6105 88:6807 17:12943
1.142556 1 :: -27493:557 244:757 90:1068 61:1393 22:3458 122:11018 44:27493
1.142578 1 :: -30027:162 22:568 -29:1432 83:5087 -7:6107 -10:27493 -29:30027
1.142821 1 :: 28800:437 -12:682 278:1032 -95:2072 139:3405 163:12943
190:28800
1.143298 1 :: -13637:239 212:1068 -144:2072 188:2309 -200:6105 376:6807
288:13637
1.143328 1 :: 51:239 132:268 44:599 32:682 -44:1118 -20:12943
1.143897 1 :: 88:112 7:239 -44:515 32:682 88:12433 24:12943
1.144762 1 :: 27493:378 115:557 29:1068 122:2943 144:3458 -244:14318
44:27493
1.144861 1 :: -11018:577 200:606 127:1393 -20:2943 112:3740 -44:6118
56:11018
1.144885 1 :: -12943:307 -56:682 139:1607 190:4193 -95:5357 139:5928
-122:12943
1.144888 1 :: -17557:378 215:682 -44:829 7:2943 -359:5257 -115:12943
-44:17557
1.144969 1 :: -16432:538 127:682 227:1068 44:2072 -176:2943 -27:12943
88:16432
1.145937 1 :: 39:68 22:117 5:327 10:557 -10:1068
1.146231 1 :: -28322:239 124:993 -56:1252 56:2855 -76:2943 -100:13252
100:28322
1.146755 1 :: -28322:239 100:343 -56:2072 -76:2943 100:7983 -12:16432
100:28322
1.146961 1 :: 22:27 -10:211 10:776 2:1068 5:1393
1.147036 1 :: 83:239 144:268 -12:557 -32:1068 -44:1118 -44:5283
1.147298 1 :: 71:239 100:268 24:327 20:1252 32:2855 52:3557
1.147330 1 :: 51:239 80:268 64:307 20:343 32:5087 12:27493
1.147999 1 :: 54:172 68:183 32:682 51:1393 34:2350 10:5357
1.148963 1 :: 56:57 -24:192 -17:239 -12:515 24:1068
1.149685 1 :: -19703:538 -88:568 215:682 139:1068 -27:12943 -132:14773
44:19703