RC Schroeppel: Possible minimum-memory method for computing pi to N bits, albeit extremely slowly: For K = 0 to N, use the BBP formula for the Kth bit. This will require O(logN) storage: several registers of size logN to hold the state of the BBP calculation. You'll also need to be aware of the Chudnovsky result, which, IIRC, is that |pi - p/q| > q^-13. That is, you can't get too many consecutive 0s or 1s before a round-up-or-down situation is resolved. However, if you want the answer in decimal, you may need space to hold most of the .301 N digits, which would bump the space to O(N). --WDS: lovely [if useless] observation. However, I think the story may be a little deeper than you realized, in the following sense. The "irrationality measure" you had in mind is |pi - p/q| > q^(-u) in all but a finite number of cases, The current record apparently is u = 7.6063 by V.Kh.Salikhov: On the Irrationality Measure of pi, Usp. Mat. Nauk 63 (2008) 163-164; English transl. in Russian Math. Surveys 63 (2008) 570-572. But here is the thing: I think "in all but a finite number of cases" is NOT an effective, i.e. not an algorithmic, result -- there is no known algorithm to find the last exception. (Or am I wrong about that?) If so, you actually have not got an algorithm here -- although "God" knows (but you do not know) the relevant constant, hence an algorithm EXISTS, but you do not know what that algorithm is. So you've actually got an NONCONSTRUCTIVE existence proof for an O(logN)-memory algorithm to compute N bits of pi !! Now if instead of PI you asked about other numbers... for certain numbers like e and quadratic irrationals, the full continued fraction expansion is known, hence the irrationality measure and the "last exception" both are fully understood. If any such number happens to have a BBP formula, then you'd be fully golden. Hmmm. It seems that "Baker's theorem" http://en.wikipedia.org/wiki/Baker's_theorem nowadays has fully effective/explicit formulas e.g. due to Baker & Wustholz. Therefore, it is possible to produce explicit irrationality measure statements for pi (albeit perhaps requiring far larger u than Salikhov's!), having no exceptions. A.Baker & G.W"ustholz: Logarithmic forms and group varieties, Journal f"ur die Reine und Angewandte Mathematik 442 (1993) 19-62 Therefore, I think RCS's algorithm really can be made into an algorithm.