Daily Archives: 3/6/2007

Hex Digits of π

The 10 hex digits of π starting at the 10 millionth place after the decimal point (is it really a decimal point if you are writing numbers base 16?) are 7AF58 63EFF. How do I know? Why, courtesy of my own implementation
of the Bailey-Borwein-Plouffe formula for computing hex digits of pi. This remarkable discovery allows you to compute hex digits of pi without computing all the digits to the left of it. My program is probably accurate out until 107 decimal places and runs reasonably fast. When compiled with -ffast-math and -O3 on my AMD box, it computes the 10 millionth place in about 21.3 seconds. Not bad.

Addendum: Incidently, this program was written largely because I tried downloading this program from the LiteratePrograms wiki, and found that the “Basic Implementation” simply didn’t work for any n > 0.

Addendum2: The final digit is actually off in the above example. It should be 7AF58 63EFE. If you run the program to find the 10000001 digits, you get AF586 3EFEE (again, the final digit is off). We are operating at the limits of precision right around there. (Oddly, I seem to get the proper result on my Intel Xeon box at work. Not sure what’s going on there.) Whether I get the final digit right or not appears to depend on whether I compile with -ffast-math. With, it gets the final digit right. Without, it gets it wrong. Interesting.

Addendum3: You might want to read this paper for more information. The examples seem to differ in one position than the results I got, probably because my program addresses digit 0 as the first digit to the right of the decimal. No biggie.

Addendum4: If you replace “double” in the code with “long double”, apparently you can get 128 bit math, at least on my AMD64. It seems to work, I ran it out to 10^8th, and I’m getting the right digits:

bbp (using long double arithmetic)
CB840 E2192
421.034u 2.256s 8:20.93 84.4%   0+0k 0+0io 0pf+0w