Pages, some stolen, some original
▼
Monday, March 16, 2009
More π
So I was thinking about that program for calculating the value of π that I posted yesterday, and I realized that the algorithm was quite capable of calculating the value of pi to an indefinite number of digits. The code would take some work, quit a bit of work actually, but feasible. The algorithm calculates a new value of x with every iteration. This new value of x starts 4 bits to the right of the place of the last value of x. So you could keep adding these new values of x to this string of bits for however long you wanted to. Eventually you would get tired or bored, or run out of disk space, but you could go quite a while.
The problem you would run into is that each value of x would be an infinitely repeating pattern, so you would have to keep replicating this pattern as you went, and with each iteration, the pattern would get longer. It might be necessary, or even easier to keep a separate pattern for each new value of x. Then when you get a new value of x, you add the appropriate section of each pattern to it and append that value to your infinitely extending value of pi.
There is going to be some point where the addition of the new x is not going to propagate any farther towards the binary point. Then you can say you know the value of pi to that point and can safely store it away.
Recognizing how many bits go into each pattern is going to be another trick. I imagine someone has already figured out how to do that.
The algorithm is linear in time and logarithmic in space.
ReplyDeleteStu
PS: happy st.patrick's day!