[Cryptography] Ah, The Circles of Life

[Jerry Leichter]

On Nov 6, 2013, at 9:38 AM, Kent Borg <kentborg at borg.org> wrote:
> ...And that for makes me wonder about pi, but in hex.  (Can't remember the question before, but all things are new to me at least once.)  So I google "pi in hex".
I'm surprised you didn't come across:  http://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml

It turns out that it's possible to compute the n'th digit of pi in hex directly, without computing all the preceding ones.  The calculation is essentially O(n) time, O(log n) space!

(Hex is not unique - obviously, if you can do hex, you can do any base of the form 2^k where either k < 4 or k is a multiple of 4.  I forget what other bases are possible, but 10 is not.)

I think one of the authors of the algorithm used to have a site that would compute the n'th hex digit of pi for you on request, but it seems to have disappeared over the years.  You can readily find source code for this, however.

Which provides another way to "cheat" at choosing constants:  Use the digits of pi starting at position k, where k is chosen in some unspecified way.  Sounds really good - after all, who can muck with the digits of pi? - but of course one can search for a k such that pi starting at k has some desired property....

                                                        -- Jerry