The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/doc/pi.txt
security/nss/lib/freebl/mpi/doc/pi.txt
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:e66bc823e1e9 |
|---|---|
| 1 This file describes how pi is computed by the program in 'pi.c' (see | |
| 2 the utils subdirectory). | |
| 3 | |
| 4 Basically, we use Machin's formula, which is what everyone in the | |
| 5 world uses as a simple method for computing approximations to pi. | |
| 6 This works for up to a few thousand digits without too much effort. | |
| 7 Beyond that, though, it gets too slow. | |
| 8 | |
| 9 Machin's formula states: | |
| 10 | |
| 11 pi := 16 * arctan(1/5) - 4 * arctan(1/239) | |
| 12 | |
| 13 We compute this in integer arithmetic by first multiplying everything | |
| 14 through by 10^d, where 'd' is the number of digits of pi we wanted to | |
| 15 compute. It turns out, the last few digits will be wrong, but the | |
| 16 number that are wrong is usually very small (ordinarly only 2-3). | |
| 17 Having done this, we compute the arctan() function using the formula: | |
| 18 | |
| 19 1 1 1 1 1 | |
| 20 arctan(1/x) := --- - ----- + ----- - ----- + ----- - ... | |
| 21 x 3 x^3 5 x^5 7 x^7 9 x^9 | |
| 22 | |
| 23 This is done iteratively by computing the first term manually, and | |
| 24 then iteratively dividing x^2 and k, where k = 3, 5, 7, ... out of the | |
| 25 current figure. This is then added to (or subtracted from) a running | |
| 26 sum, as appropriate. The iteration continues until we overflow our | |
| 27 available precision and the current figure goes to zero under integer | |
| 28 division. At that point, we're finished. | |
| 29 | |
| 30 Actually, we get a couple extra bits of precision out of the fact that | |
| 31 we know we're computing y * arctan(1/x), by setting up the multiplier | |
| 32 as: | |
| 33 | |
| 34 y * 10^d | |
| 35 | |
| 36 ... instead of just 10^d. There is also a bit of cleverness in how | |
| 37 the loop is constructed, to avoid special-casing the first term. | |
| 38 Check out the code for arctan() in 'pi.c', if you are interested in | |
| 39 seeing how it is set up. | |
| 40 | |
| 41 Thanks to Jason P. for this algorithm, which I assembled from notes | |
| 42 and programs found on his cool "Pile of Pi Programs" page, at: | |
| 43 | |
| 44 http://www.isr.umd.edu/~jasonp/pipage.html | |
| 45 | |
| 46 Thanks also to Henrik Johansson <Henrik.Johansson@Nexus.Comm.SE>, from | |
| 47 whose pi program I borrowed the clever idea of pre-multiplying by x in | |
| 48 order to avoid a special case on the loop iteration. | |
| 49 | |
| 50 ------------------------------------------------------------------ | |
| 51 This Source Code Form is subject to the terms of the Mozilla Public | |
| 52 # License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 53 # file, You can obtain one at http://mozilla.org/MPL/2.0/. |
