2

I want to write a simple distributed software for the calculation of $\pi$. I want to use a formula which is as easy to distribute as possible. I'm thinking of the BBP formula, or something similar (a digit extraction algorithm), since I can distribute specific digits to the clients, and there is no need to perform a centralized summation in the server. Is there a better approach? The requirement is that I want to minimize the job that is needed to be done by the server, and, if possible, I would like not to need arbitrary precision arithmetic.

Alejandro Piad
  • 217
  • 1
    Just to clarify, are you satisfied with a binary expansion of $\pi$? Because there is no decimal extraction algorithm. –  Nov 15 '13 at 21:15
  • 1
    I'm aware, but I think I can turn a binary expansion into a decimal, with enough digits, right? – Alejandro Piad Nov 15 '13 at 21:16
  • 1
    Yes - but then unfortunately your distributed computing project needs to get recentralized, since the only way to calculate the $n$th decimal digit from a binary expansion is to have all the necessary binary digits from the start! If the ultimate goal is decimal, you probably don't want to use BPP. –  Nov 15 '13 at 21:18
  • 1
    Is that so? Well, in that case, I would like to see a comparison of the possible methods, so I can decide if I want to trade the decimal expansion for a faster or easier algorithm. In either case (requiring the decimal expansion, or not) what would be the best approach? Remember that I would like not to depend on arbitrary precision arithmetic. – Alejandro Piad Nov 15 '13 at 21:22
  • 1
    @Mike: There is a decimal digit extraction algorithm, although I don't know anything about it; Fabrice Bellard has a page "Computation of the $n$th digit of pi in any base in $O(n^2)$", which improves on an $O(n^3 \log n)$ result of Simon Plouffe's (of BBP). – Antal Spector-Zabusky Nov 15 '13 at 21:26
  • 1
    @AntalS-Z It would be nice to have a simple (algorithmic) explanation, since the explanation in the link is rather obscure, at least for me, with little background on number theory, and I cannot easily dig out an algorithm from Bellard's web page. – Alejandro Piad Nov 15 '13 at 21:30
  • 1
    Oh! I was completely unaware. Thanks, I'll have to look at that. @Alejandro, ignore my comments; I was thinking of a result that there is no BPP-like algorithm for bases that are not powers of $2$, though I appear unable to find the actual paper... –  Nov 15 '13 at 21:33
  • 1
    @AlejandroPiad: Yes, it would be nice, wouldn't it? :-) Unfortunately, as I said, "I don't know anything about it"; I saw a reference to the algorithm a while back, and digit extraction algorithms have been sitting in my "I want to try to understand this pile" ever since. – Antal Spector-Zabusky Nov 15 '13 at 21:35

1 Answers1

2

I'm sorry if I burst your bubble, but here's the truth.

  • It really would be awesome if there was at least 1 algorithm that allowed you to get any digit of pi while skipping the previous digits, but unfortunately, there are no such algorithms.
  • To realistically calculate a noticeable/practical more digits than have already been discovered, you would have to have an INCREDIBLY big beefy powerful computer because the first 12.1 trillion have already been discovered (see here).
  • I would suggest you try an already near perfect pi generator that was used to generate the 12.1 trillion digits of pi: y-cruncher
  • If you really do want to look in to creating your own pi generator AND you do meet the astounding cpu requirements, then I heavily respect your persperation and also you might want to start your trek here at binary-splitting and here at Chudnovsky, and with that, I hope the the best of luck to you (since it will be hard) .



Also another thing to get you going is I have a theory you might want to think about:


Why not use the Gauss–Legendre algorithm, but instead of caching the bulk of the temporary stuff from the calculations on the RAM, why not temporarily move it over to the hard disk after that specific section has been computated, and move it back to the RAM for the duration of being used again before moving it back to the hard drive again? At first, you may think that this would actually decrease the speed, but its the Gauss algorithm! It converges so incredibly quickly that the time it takes to go the extra mile by using the hard drive for cache could actually probably be well overcompensated by the incredibly quick convergence of the Gauss algorithm, thus resulting in an actual overall increase in performance and a super duper fastly calculated pi in an incredibly small amount of RAM. (Also, you'll need to look at this page for info on speeding up not just your usb, but it also works very well for hard-disks)


Another post to check out: Calculating custom bits of PI in hex or binary without calculating previous bits

Community
  • 1
Jack G
  • 224
  • 2
  • 17
  • 1
    To quote the entry on the Bailey-Borwein-Plouffe formula: "...The formula can directly calculate the value of any given digit of π without calculating the preceding digits." So I think you need to clarify your first bullet point where you claim there is no such algorithm. – Tito Piezas III Oct 17 '15 at 03:43
  • 1
    as said here http://math.stackexchange.com/questions/624435/calculating-custom-bits-of-pi-in-hex-or-binary-without-calculating-previous-bits/1482395#comment3020889_624435 it needs same precision calculation and this mean same iterations and same complex calculations. – Serg Kryvonos Nov 04 '15 at 22:17