[148057] in cryptography@c2.net mail archive
Re: [Cryptography] Ah, The Circles of Life
daemon@ATHENA.MIT.EDU (Jerry Leichter)
Wed Nov 6 17:37:39 2013
X-Original-To: cryptography@metzdowd.com
From: Jerry Leichter <leichter@lrw.com>
In-Reply-To: <527A546B.80307@borg.org>
Date: Wed, 6 Nov 2013 16:45:39 -0500
To: Kent Borg <kentborg@borg.org>
Cc: cryptography@metzdowd.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On Nov 6, 2013, at 9:38 AM, Kent Borg <kentborg@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
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
