[RC5] Re: rc5-digest V1 #261

Jason Stratos Papadopoulos jasonp at Glue.umd.edu
Sun Jan 24 23:06:25 EST 1999

On Sun, 24 Jan 1999, Kai Rode wrote:

> On Sat, 23 Jan 1999 15:32:58 -0500, you wrote:
> >The other one I think that could gain publicity is the search for
> >Pi..ie..PiHex that Colin Percivel(sp?) wrote.  Just about everyone knows
> >what Pi is and they also know that it (so far) is an endless number.
> Is PiHex suited for distributed computing?
> The best known algorithm for calculating digits of pi is as far as I
> know the binsplit algorithm. Calculating pi to 1 billion places (that's
> one trillion in American English) using distributed computing would be
> feasible, but:

The critical idea in PiHex is that as long as you work in hex and not in
decimal, you can figure out what the n_th digit of pi is *without*
computing the n-1 digits behind it. This is because 

 pi = Sum ( 4 fractions that vary as 1/n ) / (16^n)

This, and some 64-bit (or even 48-bit) modular math lets you compute the
n_th hex digit in O(n) time and constant memory. One program I heard about
can find the millionth "hexit" in six seconds on a fast Pentium. Even
better, the computation is embarassingly parallel (you just hand out
blocks of terms to add up, and no particular block takes longer than
any other).

For more info, look up a document on the Web somehwere called 
"Pi: a 2000 Year Old Search Changes Direction" (forgot the URL).


To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list