 |
 | Article for review
ssnirgudkar | 16:15 21 Dec '09 |
|
|
Hello Chris,
This is Shailesh. Recently I came across your 'pi' article as I was also interested in the same problem. I did go through your code and faq and implemented my own code. It is very, very similar to yours ( I am not ashamed ). I also wrote one article related to the subject. Would you like to review the article and give your comments ? Only if you permit me, I plan to post the article and the code on opensource.
Please let me know.
regards,
shailesh nirgudkar
|
|
|
|
|
|
|
Please let me know your email so that I can send the article.
-shailesh
|
|
|
|
|
| Enough with the term "million million"!
prom 1976 | 1:03 16 May '08 |
|
|
The term "a million million" is easily quantified by a 2nd-grader as a "trillion"...For christ's sake, we don't say, "a thousand thousand" to describe "a million", unless I am 14 centuries ahead of my time and I didn't know it...
Let me quantify numerics by name:
Number of zeros/U.S. & scientific community
3/thousand
6/million
9/billion
12/trillion
15/quadrillion
18/quintillion
21/sextillion
24/septillion
27/octillion
30/nonillion
33/decillion
36/undecillion
39/duodecillion
42/tredecillion
45/quattuordecillion
48/quindecillion
51/sexdecillion
54/septendecillion
57/octodecillion
60/novemdecillion
63/vigintillion
66/undecillion
303/centillion
etc...
Those who even speak "million million" are simply retarded and do not know how to quantify numbers higher than a million...The same applies for those who say "billion billion", who cannot quantify a quintillion. To salvage any intelligence, at least describe it to the tenth power, instead of thinking that saying the same word twice somehow multiplies it's meaning.
This is what lack of funding does to american education (now a contradiction in terms).
|
|
|
|
|
|
|
Wow! I must have really annoyed you by what I wrote. But you're making some assumptions:
- That I am from the USA.
- That all the people who read CodeProject are from the USA or the scientific community.
Both assumptions are incorrect. I was concerned that if I wrote "billion" or "trillion" then some readers might be unsure as to whether I was using British or American nomenclature. http://en.wikipedia.org/wiki/Billion[^] says that "Billion may refer to ... one thousand million [or] one million million". So I wrote "million million" to be unambiguous. Your implication that saying the same word twice does not multiply "it's meaning" is incorrect (and you mean "its meaning", BTW). "Ten million" is well understood, so are "hundred million" and "thousand million", so "million million" is perfectly acceptable. It is generally considered impolite to impugn the intelligence of people simply because one disagrees with them. I'm sure that this indiscretion was simply because you are new to CodeProject.
|
|
|
|
|
|
|
I agree; in spanish, a billion means "One million of millions" but in english it means different, however, thanks for the advice for writing big numbers.
Bye
|
|
|
|
|
| Radians or Degrees?
Thmath1776 | 11:06 3 May '08 |
|
|
I am pretty sure it is in Radians, but you may want to say so because the answer comes out to be 45 in degrees. 
|
|
|
|
|
 | Optimization to the death
pouyaebad | 2:01 9 Mar '08 |
|
|
I was surfing the 'code project' site, while I see your article about calculating PI number. I liked it so much and since my hobby is optimization I tried to write a C code to calculate it by implementing the algorithm you mentioned.
Although my program is a small one (about 350 SLOC in C) but it took me a week to write it.
My optimizations in the code include:
1- Coding the division function in assembly to get the quotient and remainder with just an instruction.
2- Converting the entire numbers to Hex base in the beginning and doing the whole calculation in Hex (which is much faster), in the end I converted result to Decimal base again.
3- Manipulating process and thread properties a bit to eat the whole CPU power.
By these tricks, I got the following result for calculating PI to the 100,000th digit:
(All ran on P4 2.6 GHz)
1- Original program written by Chris : 239 seconds
2- Optimized program by Todd : 84 seconds (see notes below)
3- My Optimized program : 52 seconds
4- My Optimized program (multi threaded): 36 seconds
5- My Optimized program (multi threaded): 24 seconds
*note: the last experiment ran on a quad core Intel CPU (3GHz) to get the advantages of multi threading feature.
Total calculation time to the 1,000,000th digit is less than 52 minutes on quad core Intel processor.
I am sure with a few changes to this code; it can run faster on 64 bit CPUs (I used 64 bit integers in my calculations)
I am also interested if there could be any further optimizations to algorithms or implementation techniques which make this program run even faster.
BTW, thank you for your state of the art article.
Pouya
|
|
|
|
|
|
|
This is me again. Something surprising happened, I incresed threads number from 3 to 4 and surpisengly I found that even on my P4 machine, performance of the program increased by %14. It is very strange to me. because even by hyperthreading technology, my CPU acts as 2 processors, so there shouldn't be any differences between 3 and 4 threads (each thread is running by the highest priority) but my experiance shows that there is a performance boost ??? why?
Pouya
|
|
|
|
|
|
|
|
|
|
Hello! How did you get it to become multithreaded? Did you just parallel multiprecision arithmetic operations? Or there is a better scheme? Thanks.
|
|
|
|
|
 | Why is this important?
curiousone | 10:31 11 Jun '07 |
|
|
Will solving it to a billion or trillion decimals help with anything? Will it solve some all-consuming problem?
|
|
|
|
|
|
|
<1> pseudo random number generators
<2> predictable encryption schemes
<3> transmission error correction
<4> system/cpu performance testing
<5> geek and programmers toys
and if you have to ask, you don't belong here 
|
|
|
|
|
|
|
It will help us understand the power of math besides, pi helps us calculate important stuff.
* Life would be so much easier if we just had the sourcecode *
|
|
|
|
|
| Multilength arit.
diegusaldus | 0:05 3 Apr '07 |
|
|
Hello I'm very interested in some explanation regarding the multilength aritm and what is the flow that led you to this slender piece of code. I'm studying the topic for get rid of floating point numbers as i'm developing a voice rec in a symbiam env.
would you be so kind to address me on the trajectory of your pi calculation.
I'm very fond of mfc and I'have just finished some piece of work.
thanks in advance.
my email is diegoburlando@hotmail.com.
Diego from Italy
Hello!
|
|
|
|
|
|
|
To write some code to do multilength arithmetic you just have to think about how you were taught addition, subtraction, multiplication and division at primary school. So to add two numbers you start at the right, add the units digits, write down the units digit in the answer, take any carry over into the tens column, etc. With a 32-bit OS you don't have to limit yourself to using base 10, you could use base 2**32 = 4294967296. The only problem then is converting your input data from base 10 to base 4294967296, and converting the answers from base 4294967296 back to base 10 if you need to. I compromised and used base 1000000.
You say you're "developing a voice rec in a symbiam env" - are you sure that double length floating point arithmetic isn't good enough?
|
|
|
|
|
| It's not Exact
Zmurf | 0:55 8 May '06 |
|
|
This is not exact because sine cosine an tangeant functions are not exact. They are calculated using series which must run for an infinite peried of time to generate an exact answer. Thus PI is not exect. However, the decimals displayed are axact for a finite number of decimal places until the lack of accuracy on the series kicks in.
Mark Schad
|
|
|
|
|
|
|
I think you haven't read the article.
Or if you have there is something you don't understand, for exemple: of course it's not exact: no computer could ever give the exact value of PI (except in symbolic form) but the approximation could be as good as desired by taking some time to compute enough series member....
|
|
|
|
|
|
|
No matter how long you compute PI using this method, even if you were to do it for an infinite period of time, your answer would not be exact. Graphing the result of each iteration of this method to find PI where the SUM of the iteration was graphed on the y-axis and the iteration number was graphed on the x-axis, you would find there would be a neat little assimtope along PI paralell to y = 0.
|
|
|
|
|
|
|
Are you a kind of Troll?
Why do you contradict yourself and take it as a proof you are right?
Let me be sure I'm understanding you correctly, I will repeat what I understood you saying:
"The result will never be PI, if you graph the will find it follow a curve which tends asymptotically toward PI"?
Is it what you said?
One of us is very confused here ...
There is one more thing which puzzle me greatly, what do you means by: "No matter how long you compute PI using this method, even if you were to do it for an infinite period of time, your answer would not be exact"
While it is completely wrong, do you know of any method which compute "exact the decimal value" of pi in a finite amount of time?
(if you do: patent it, you will be the greates Mathematician of the 10 next milleniums!)
Because there many methods which compute the decimal value of PI, this is one them, and they all take an infinite amount of time....
The key is: name your error, that gives you the number of iteration.... (the smaller, the more iteration...)
|
|
|
|
|
| Bailey-Borwein-Plouffe formula (this is amazing)
Don Clugston | 0:28 17 Oct '05 |
|
|
infinity 1 { 4 2 1 1 }
PI = SUM --- { ---- - ---- - ---- - ------ }
n=0 16^n { 8n+1 8n-4 8n+5 8n + 6 }
This amazing formula, discovered in 1995, allows you to calculate (say) the millionth digit of PI without calculating the intermediate ones first.
Only works for hexadecimal. Another consequence is that it allows you to calculate PI without multi-precision arithmetic (although you still need multi-precision if you want results in decimal!)
You should definitely mention it in your 'points of interest'.
For more info, see
http://www.sciencenews.org/pages/sn_arc98/2_28_98/mathland.htm
or look at the original papers:
http://www.cecm.sfu.ca/personal/pborwein/PISTUFF/Apistuff.html
Enjoy!
|
|
|
|
|
| simple optimizations
cub4bear | 6:32 28 Sep '05 |
|
|
I liked your PI program so much that I added a few simple optimizations to reduce the compute time by about a factor of 4.
1) Use 9 digits rather than 6 for each int (reduces the total number of operations).
2) Keep track of first non-zero int in each MultiLengthInteger, so as the dividends get smaller and smaller, we aren't traversing a bunch of zeros for the divide, add, subtract, and assign operations.
3) Use one divide and two multiplies (rather than one divide, one modulo, and one multiply) in the divide routine (since divide is more expensive than multiply).
4) Added function .iszero rather than compare against a MultiLengthInteger that has a value of zero.
5) Preallocate the CString when building the final result.
My total time for 100000 digits went from 239 seconds originally down to 83.
The time for a 1-million digit run was 8575 seconds (2 hours, 22 minutes, 55 seconds) -- I didn't do a non-optimized run here, but in theory that would have been about 9 hours 28 minutes.
2.4Mhz Pentium
Cool stuff!!
-Todd
|
|
|
|
|
|
|
Perhaps you get better results if you use the following formula:
pi / 4 = 44 * arctan(1 / 57) + 7 * arctan(1 / 239) - 12 * arctan(1 / 682) + 24 * arctan(1 / 12943)
|
|
|
|
|
|
|
I tried the 4 series, as you suggested, and it was actually slower. Even though the 4 terms probably each converge more quickly than the two terms [4*arctan(1/5) - arctan(1/239)], having four terms seems to take longer.
Pi @ 100,000 digits:
2 arctan series = 84 seconds
4 arctan series = 97 seconds
|
|
|
|
|
| my results
manuelpg | 22:41 26 Sep '05 |
|
|
6 hrs 40 mins on my 1GB AMD Senprom 3200+. I run on release mode and compiled with speed optimizations on. My computer is benchmarked at 7500 MIPS by SiSoft Sandra.
|
|
|
|
|
| How long did it take?
WREY | 12:49 19 Sep '05 |
|
|
How long did it take your computer to do the calculations?
It being the only application running at the time, after 15 solid minutes of running on a dual (2.5 MHz) Pentium processor with 1 Gb of memory, I killed it.
William
Fortes in fide et opere!
-- modified at 18:05 Monday 19th September, 2005
|
|
|
|
|
in this article, because some browsers might show it incorrectly.