Pi in Base 16 - special formula

[Antiphon]

About 20 years ago I caught an article about a graduate student
who had found an algorithm which would return the n-th digit of
\pi without needing to compute the preceding digits.

In other words you could ask for the 812th digit of \pi and
it would spit it out without computing the prior 811 digits. There was
a computer program in the work written in Fortran.

The rub is that it only worked in base 16.

Is anyone familiar with a special connection between base 16 and an
easier way to compute digits of \pi?

 

[NateTG]

The rub is that it only worked in base 16.

Is anyone familiar with a special connection between base 16 and an
easier way to compute digits of \pi?

Hmm, are you sure that it only works in base 16? It's quite easy to translate between power-of-two bases to generate, for example, a base-2 spigot algorithm instead.

However, since the number of decimal digits for \frac{1}{2^n} is rougly proportional to n it doesn't readily convert to base 10.

 

[Antiphon]

Hmm, are you sure that it only works in base 16? It's quite easy to translate between power-of-two bases to generate, for example, a base-2 spigot algorithm instead.

However, since the number of decimal digits for \frac{1}{2^n} is rougly proportional to n it doesn't readily convert to base 10.

Yes, base translation is easy to do, but if you look at what's involved
you'd end up doing arithemtic on the full string during base conversion
so you'd gain nothing.

In other words, this algorithm would quickly compute the 10,000th hex
digit of Pi and suppose that digit was "5". The base conversion of
5 \times 16^{(-10,000)} would put you back in the position
of doing arithmetic on 10,000+ digit strings.

Edit: Yes, I'm quite sure it is a hexadecimal algorithm. That's one of the
few details that stuck with me for the last 20 years.

 

[Hurkyl]

I know of the BPP formula, but that's not 20 years old... I was under the impression that it was rather novel when it was found.

 

[shmoe]

I've never heard of the algorithm matching your description (~20 years old, by a graduate student) but the BBP one Hurkyl mentions is more recent (~10 years old by Bailey, Borwein, and Plouffe) and works in hex. I haven't read it thoroughly, but it also seems to work for binary as well. Plouffe also seems to have an algorithm for the nth digit of pi in any base. Both can be found on Plouffe's web page:

http://www.lacim.uqam.ca/~plouffe/

 

[Zurtex]

I don't suppose there is a way of looking at this formulae and its general properties to see if Pi is a normal number in base 16?

 

[master_coda]

Yes, base translation is easy to do, but if you look at what's involved
you'd end up doing arithemtic on the full string during base conversion
so you'd gain nothing.

In other words, this algorithm would quickly compute the 10,000th hex
digit of Pi and suppose that digit was "5". The base conversion of
5 \times 16^{(-10,000)} would put you back in the position
of doing arithmetic on 10,000+ digit strings.

Edit: Yes, I'm quite sure it is a hexadecimal algorithm. That's one of the
few details that stuck with me for the last 20 years.

I think NateTG was referring to the fact that you don't need to use arithmetic to convert between power-of-2 bases. If you know the 10,000th hex digit of Pi is 5, then bits 39,997 through 40,000 are 0101. So it would be quite straightforward to convert a base-16 algorithm to a base-2 algorithm, and it's similarly easy to convert from a base-2 algorithm to a base-2^n algorithm.

 

[NateTG]

I don't suppose there is a way of looking at this formulae and its general properties to see if Pi is a normal number in base 16?

Somewhat. It can be used to relate chaotic attractors (or something like that) to normality. No proof that π is normal in hexadecimal that I know of though.

 

[ohwilleke]

Hexadecimal was very big with computer programmers when computers were first coming out (and also popular with gamers, an RPG called Traveller I used to play used lots of Hexidecimals). I suspect that was because a hexidecimal base allows you to put two numbers in every byte (eight binary bits) that the computer processes, which is a big deal when you are short on processing power. Programming in a decimal base would allow you only one number per byte if your interface was primative enough not to allow easy coding of numbers in more than one byte.

Thus, a two hexidecimal code could put anything two digit number with a value from 1-256 in a byte, while a single decimal code would be limited to values from 1-10 for a byte. This is a huge deal when you are working with 10,000 digit numbers on a routine basis.

Put another way, the attraction of hexidecimal probably comes from the limitations of the computer rather than the mathematics itself.

I rather suspect that lots of source code still converts decimal to hexidecimal, but does so transparently.

At any rate, processors are so much faster, and RAM memory is so much greater, that absolute efficiency isn't a priority in the same way that it used to be, so most programmers don't worry so much about these issues.

 

[Zurtex]

All computer code effectively works in binary, it was all original designed as 8 bits, but looking at 8 bits isn't nice, look at the same code where 8 bits is represented as 2 hexadecimal numbers is much easier. That's it really, it's still all binary but much nicer on the human eye.

 

[Antiphon]

My memory of this being 20 years old is probably wrong.

But the reasons for it being in Hex were not computer related.

Also, base 10 is not a power of two so that's why the conversion back to
3.14159... is not trivial.

Thanks for the reference, that's probably it.

 

[GravitatisVis]

I don't suppose there is a way of looking at this formulae and its general properties to see if Pi is a normal number in base 16?

What do you mean by "normal nuber?" Would pi be a rational number in a different base?

 

[lurflurf]

What do you mean by "normal nuber?" Would pi be a rational number in a different base?

Yes pi is rational in some bases.
For example
pi=10 (base pi)
pi=1.11111111... (base 1+1/pi)
pi=0.1 base 1/pi
Pi is not rational for any integer base
This has nothing to do with normnal numbers.
A number is normal in a base if every seqence appears with the frequency of other seqences of the same length.
That is the frequency of a sequence of length n is ^-n that is the integer part of the base to the nth power.
So in a base 10 normal number
0129 has frequency 1/1000
223 has frequency 1/100
7 has freqency 1/10
3141592653 has freqency 1/10000000000
and so on
1/3=.3333333333...
is not normal base 10 as 229 has frequency 0

 

[Zurtex]

What do you mean by "normal nuber?" Would pi be a rational number in a different base?

http://mathworld.wolfram.com/NormalNumber.html

 

[Mothershed]

My senior research

Last year I completed my senior research on pi... yes pi. I actually have a 30 page paper on the BBP theorem, using it, developing it... Also included are pages of pi in binary form, hexidecimal form, and pi in base 32. Pi in base 32, if you arent familiar, is symbolized using the alphabet and some other symbols. I suggest taking a look at it, Included in the paper is statistics on words that were founf inside pi using various patterns. Such as taking every other hexidecimal, lining them up, and searching for words. Also, frequencies in each case are also documented. I have this for every 2nd, 3rd, 4th.. etc. I do not have the link committed to memory, but, you can go to yahoo and search "Mothershed Pi" and a link for a microsoft word document should be the first thing on the list. If you do take a look at it, go ahead and shoot me an email at cmothershed@sualum.com with questions, comments, or just to let me know someone is looking at the hours of my life I put into this.