Pi in Base 16 - special formula

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

    In other words you could ask for the 812th digit of [tex] \pi [/tex] 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 [tex] \pi [/tex]?
     
  2. jcsd
  3. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    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 [itex]\frac{1}{2^n}[/itex] is rougly proportional to [itex]n[/itex] it doesn't readily convert to base 10.
     

  4. 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
    [tex] 5 \times 16^{(-10,000)} [/tex] 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.
     
    Last edited: Jul 28, 2005
  5. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  6. shmoe

    shmoe 1,994
    Science Advisor
    Homework Helper

    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/
     
  7. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

    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?
     
  8. I think NateTG was refering 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.
     
  9. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    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.
     
  10. ohwilleke

    ohwilleke 689
    Gold Member

    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.
     
    Last edited: Jul 29, 2005
  11. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

    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.
     
  12. 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.
     
  13. What do you mean by "normal nuber?" Would pi be a rational number in a different base?
     
  14. lurflurf

    lurflurf 2,327
    Homework Helper

    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
     
  15. Zurtex

    Zurtex 1,123
    Science Advisor
    Homework Helper

  16. 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.
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?