Archived

This topic is now archived and is closed to further replies.

TerranFury

Pi

Recommended Posts

I understand that this is more of a theoretical math topic than a pragmatic game-development one, but I think it's interesting nevertheless. The Bailey-Borwein-Plouffe formula for Pi is as follows: It had been said that it can "calculate the dth digit of pi without being forced to calculate all the preceding d-1 digits."(Note: They mean hexadecimal digits. That should call them hexits) After hearing that claim, I figured I'd try to write a function pi(n) which would return the nth hexit of pi. I am not having very much success. I successfully used the above equation to calculate PI and store it in a double. This is not my goal, however. The thing that is confusing me is this: When you look at the equation, you see that the inner part: 4/(8*n+1)-2/(8*n+4)-1(8*n+5)-1/(8*n+6) should be the individual hexit. However, all these numbers do is approach zero! It seems to me that I must be missing something. Can anyone clarify things for me? Any help would be much apreciated. Edited by - TerranFury on December 14, 2001 7:10:49 PM

Share this post


Link to post
Share on other sites
An infinite sum of numbers becoming infinitely small can be finite. That''s a whole domain of mathematics and cannot fully be explained within the frame of these forums.

Share this post


Link to post
Share on other sites
Thanks for your reply. However - correct me if I''m wrong - all the "infinite" sum part of that formula does is combine all the individual hexits into a single number: pi.

It''s a lot like the standard C atol function. That string-to-number conversion function could be expressed:



strlen(string)-1
____
/
/
\ (string[strlen(string)-i-1]-''0'') * 10i
___\
i = 0



This is because the quantity (string[strlen(string)-i-1]-''0'') is a decimal digit.

The Bailey-Borwein-Plouffe formula shows the same pattern. Each hexadecimal digit is multiplied by (1/16)n because it is in base-16 and will be moving successively to the right side of the decimal point instead of the left; and n approaches infinity because there are an infinite many hexits. However, you can see that it''s essentially the same concept. The 4/(8*n+1)-2/(8*n+4)-1(8*n+5)-1/(8*n+6) part in the middle should represent an individual hexit, right? What I don''t understand is why, although the cumulative sum does equal pi, the middle part doesn''t work out to be one hexit. It looks like it should.

Share this post


Link to post
Share on other sites
The problem is that you are assuming that each of the fractions that are summed here can be represented with a finite number of bits (or hexits, or whatever). Which is not necessarily the case.

Share this post


Link to post
Share on other sites
Check out this link: http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf/c20-6.pdf

Its from Numerical Recipes in C, an awesome book if you are really interested in higher level (mostly concrete, not theoretical) mathematics.

Hope this helps.

-Vic

Share this post


Link to post
Share on other sites
Thanks krs-one. That really is a great all-around math/programming site.

Anyway, about the "digit-extraction" formula: What is there to the claim that it can "calculate the dth digit of pi without being forced to calculate all the preceding d-1 digits" then?

Share this post


Link to post
Share on other sites
I have an old QBasic program lying around on my harddrive which I downloaded in my early days as a programmer. You type in the number of decimal digits you want and then it starts spitting out Pi.

I uploaded the source for you, maybe it''ll help. It''s only 5kb, so you might as well look at it. http://httpd.chello.nl/~d.gerrits/pi.bas.txt

Share this post


Link to post
Share on other sites
I think you are reading too much into it. Just because you don''t have to calculate all of the preceeding terms doesn''t mean you don''t have to calculate any of them. Just because this sum is a starting point for an algorithm that generates the ith hexit of pi doesn''t mean the terms of this sum are the hexits of pi. Also nothing says that you can simply start at any digit you please. Rather it may be that the terms always generate repeating, non-terminating hex numbers that every so often cancel one another out. As an example 1/3+1/3+1/3=1. It may take a rather complex calculation just to figure out where you can start at and where you can''t.

Share this post


Link to post
Share on other sites
quote:
Original post by krs-one
Its from Numerical Recipes in C, an awesome book if you are really interested in higher level (mostly concrete, not theoretical) mathematics.



Just a word of warning: while Numerical Recipes in C is a good starting point for algorithms for solving various problems, it shouldn''t really be relied upon if efficiency and accuracy are what you are looking for. Many of the algorithms in the book are sub-standard and there exist much better (read ''more efficient, more accurate'') algorithms that are easily sourced on the web.

Regards,

Timkin

Share this post


Link to post
Share on other sites