Jump to content
  • Advertisement
Sign in to follow this  

Help improve my pi calcuation program

This topic is 3851 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was wondering if anyone can give me any optimization tips for my pi calculation program in C++? I know the series I'm using is slow to converge but is there any extra calculations I can get rid of or optimize since using trying to get anything more than 9 digits of pi takes several minutes even on my dualcore 2.4 machine! Thanks!

/* Calculate the value of pi from the infinite series:

pi = 4 - 4/3 + 4/5 - 4/7 + 4/9 - 4/11 + ...

Print a table that shows the approximate value of pi after each of the
first 1,000 terms of this series.

Allow for user defined accuracy (double). 
Do not just simply ask for the number of terms to be added!  
I want PI to be accurate to say the ten-thousandths place or delta = .0001 
or whatever I choose. Hint: loop until the difference between successive
calculations for PI is within the user's tolerance.  Provide output as to how
many terms in the series it took to reach the desired accuracy. Since any 
digits beyond the appropriate accuracy are extraneous find a way to format the value of PI to display only the accurate digits to the right of the decimal point. )
NOTE: a double data type is limited to 15 digits of accuracy at most
so any delta value smaller than 1x10^-15 shouldn't be used or allowed
Also even on my superfast dualcore computer any delta or epsilons smaller
than 1 x 10^-9 will take several minutes to complete since each smaller value
seems to take 10x as many loops to compute. I came up with the following table
to give you an idea so there is definitely room for speed improvement:
epsilon value setprecisionvalue number of loops to calculate pi
.1		2		21	
.01		3		210
.001	4		2100
.0001	5		21000
.00001	6		210000
.000001	7		2100000
.0000001 8		21000000
.00000001 9		210000000
.000000001 10	2100000000
etc
This is a very slow converging series so you have been warned!
Don't bother going over 12 digits since even on my 2.4GHZ dualcore
it takes more than 1 hour to run so it'd probably run all day on any other computer!
*/

#include <iostream>
#include <cmath> // need for absolute value
#include <iomanip> // for setting precision

using namespace std;

// the following function is necessary when comparing 2 floating point
// numbers for equality especially small ones
// without it my if/else doesn't catch small epsilon/delta number entered
bool isEqual(double x, double y) 
 {
   const double epsilon = .00001;
   return abs(x - y) <= epsilon * abs(x);
   // see Knuth book section 4.2.2 pages 217-218
 } 

int main(){

        bool toggle = false;        // needed to flip signs
	// need to use unsigned long long for counter since at over 11 digits 
	// of precision even unsigned int will overflow.
	// could use double but then output looks retarted having iterations in 
	// scientific notation
	// unsigned long long should be good for even more than 10 digits of precision
	// if anyone is willing to wait for the program to run that long since it can
	// hold a big big number(0 to 18,446,744,073,709,551,615)
	unsigned long long i = 0;	// number of iterations or loops
	double counter = 1.0;	
        double pi = 4.0;			// series starts at 4
        double epsilon = 0.001;		// stated as delta in original question
        double lastpi = 0.0;		// store secondary value of pi for comparison
        double diff = 1.0;			// difference in value of pi calculated
	double piaverage = 0.0;		// needed to average out last 2 value of pi
	int precisionfactor = 1;	// needed to output correct number or places

	cout << "*** Mathematical pi calculator ***\n";


	cout << "Type in your epsilon value or level of accuracy you want\n";
	cout << "For example an epsilon value of 0.1 will return 3.1 for pi:\n"; 
	cout << "Be aware that anything greater 8 digits of accuracy may take a while:\n";
	cin >> epsilon;

	//  find out value for setprecision based on epsilon entered

	if(isEqual(epsilon, 0.1))
		precisionfactor = 2;
	else if(isEqual(epsilon,0.01))
		precisionfactor = 3;
	else if(isEqual(epsilon,0.001))
		precisionfactor = 4;
	else if(isEqual(epsilon,0.0001))
		precisionfactor = 5;
	else if(isEqual(epsilon,0.00001))
		precisionfactor = 6;
	else if(isEqual(epsilon,0.000001))
		precisionfactor = 7;
	else if(isEqual(epsilon,0.0000001))
		precisionfactor = 8;
	else if(isEqual(epsilon,0.00000001)) // insane to use anything above this!
		precisionfactor = 9;
	else if(isEqual(epsilon,0.000000001))
		precisionfactor = 10;
	else if(isEqual(epsilon,0.0000000001))
		precisionfactor = 11;
	else if(isEqual(epsilon,0.00000000001))
		precisionfactor = 12;
	else if(isEqual(epsilon,0.000000000001))
		precisionfactor = 13;
	else if(isEqual(epsilon,0.0000000000001))
		precisionfactor = 14;
	else if(isEqual(epsilon,0.00000000000001))
		precisionfactor = 15;

		// or in table form

		// cout << "\tTerm\tValue" << endl; // for debugging uncomment
		
		do // keep looping while diff is greater than delta
		{	
			++i;	
			// need to figure out way to alternate sign here
			// the key is to use a toggle switch so there is a use for the ! operator after all!
			// uncomment cout in follwing if for debugging
			if(toggle){	 // keep adding terms here until we meet accuracy
				pi = lastpi - 4/counter;
				diff = abs(pi - lastpi);
				piaverage = pi+lastpi;
				lastpi = pi;
				//cout << "\t" << i << "\t" << setprecision(15) << pi << "\t"<< diff << endl;				
			}
			else {
				pi = lastpi + 4/counter;
				diff = abs(pi - lastpi);
                piaverage = pi+lastpi;
				lastpi = pi;
				//cout << "\t" << i << "\t" << pi << "\t"<< diff << endl;
			}
			
			counter+=2;
			toggle = !toggle; // flip signs
			
		}while(diff > epsilon); // keep lopping until difference between pi's is small enough

		// note the value of pi we display is actually the average of the last 2 best calculations for it
		// due to computer being unable to hold an infinite amount of digits of accuracy

		cout << "\nTook " << i << " iterations to compute pi = "  << setprecision(precisionfactor)<< (piaverage)/2 << " to " << precisionfactor << " digits!" << endl;

	return 0;
}





Share this post


Link to post
Share on other sites
Advertisement
Removing that conditional statement from your main loop might speed things up quite a bit (the 'toggle' if/else block) - you can replace it with a multiplication instead (hopefully the multiplication is faster than the conditional!)

[-]bool toggle = false;
[+]double sign = 1.0;
...
[-] The whole if/else thing...
[+] pi = lastpi + 4/counter*sign;
...
[-]toggle = !toggle; // flip signs
[+]sign *= -1.0; // flip signs

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
Removing that conditional statement from your main loop might speed things up quite a bit (the 'toggle' if/else block) - you can replace it with a multiplication instead (hopefully the multiplication is faster than the conditional!)

[-]bool toggle = false;
[+]double sign = 1.0;
...
[-] The whole if/else thing...
[+] pi = lastpi + 4/counter*sign;
...
[-]toggle = !toggle; // flip signs
[+]sign *= -1.0; // flip signs

Thanks Hodgman that what I was looking for ways to clean up my code and I was able to get rid of that inner if/else and replace everything in my main loop with this:
pi = lastpi + 4/counter*sign;
diff = abs(pi - lastpi);
piaverage = pi + lastpi;
lastpi = pi;
toggle = !toggle; // flip signs
sign *= -1.0; // flip signs
counter+=2;

I didn't think of using sign *= -1 to flip my signs before and that helped me get rid of my extra loop and repetitive code unfortunately it didn't speed up my times much since it still takes roughly 200 million loops to calculate just 9 digits of pi!
I believe that's about as fast as this particular series for pi is going to run though.
Makes for a great new benchmark for my dualcore too!

Share this post


Link to post
Share on other sites
Quote:
Original post by Nypyren
FLDPI

Also, having a dualcore machine does not make one iota of difference for the code you posted.

I had no idea what you were trying to say but once I googled it I came up with the following program that shows how pathetically slow my program is in comparision.
I never knew pi was built into the cpu--cool?

#include <iostream>
#include <iomanip>

using namespace std;

class CPi
{
public:
operator double () const
{
static double x; // the "static" is necessary for DMC!
// otherwise, the asm block seems to do nothing.
_asm
{
fldpi; // push the constant pi to the x87 stack
fst x; // store to x
}
return x;
}
};

static CPi PI;

int main()
{
double x;
cout << "Hello \n";

x = PI; // cool. Looks like a constant, but it's a function call.
cout << "Pi = " << setprecision(15) << x << endl;
}


Share this post


Link to post
Share on other sites
Alternatively you could do this:
#include <iostream>
#include <iomanip>

using namespace std;

class CPi
{
private:
static double m_PI;

public:
// constructor
CPi (void) {
// static member variable, otherwise the asm block seems to do nothing.
_asm {
fldpi; // push the constant pi to the x87 stack
fst m_PI; // store to m_PI
}
}

// return constant
inline operator double () const
{
return m_PI;
}
};

static CPi PI;

int main()
{
double x;
cout << "Hello \n";

x = PI; // cool. Looks like a constant, but it's a function call.
cout << "Pi = " << setprecision(15) << x << endl;
}

Share this post


Link to post
Share on other sites
You're attempting optimisation on too low of a level. Your compiler can do that for you. What it can't do are algorithmic optimisations.

I suggest looking into a faster-converging series. Almost anything would be faster than what you're currently using.

Share this post


Link to post
Share on other sites
Quote:
Original post by thre3dee
Alternatively you could do this:
*** Source Snippet Removed ***

Thanks but my C++ compiler doesn't seem to like something about your code since it won't compile for me?

Share this post


Link to post
Share on other sites
Uh, if you're going to avoid actually calculating pi, you might as well just do it the simple way, by using the M_PI constant defined in <cmath>.

But anyway, your computer is a lot faster than mine but it still isn't exactly bleeding-edge; I wouldn't subtly brag about it like that. And no, nothing is going to help anywhere near as much as using a faster-converging series, which is to say basically any other series. (If it's actually surprising to you that this one takes ten times as long for each additional digit, you really need to review the underlying math. Not to mention that adding up a large number of terms like that allows for a significant amount of error propagation.) Oh, and asking the user for the precision like that is quite strange. Ask for a number of digits, and take 0.1 ** that as your epsilon. ~30 lines of rather annoying-looking code gone, and a more intuitive interface for free.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Uh, if you're going to avoid actually calculating pi, you might as well just do it the simple way, by using the M_PI constant defined in <cmath>.

But anyway, your computer is a lot faster than mine but it still isn't exactly bleeding-edge; I wouldn't subtly brag about it like that. And no, nothing is going to help anywhere near as much as using a faster-converging series, which is to say basically any other series. (If it's actually surprising to you that this one takes ten times as long for each additional digit, you really need to review the underlying math. Not to mention that adding up a large number of terms like that allows for a significant amount of error propagation.) Oh, and asking the user for the precision like that is quite strange. Ask for a number of digits, and take 0.1 ** that as your epsilon. ~30 lines of rather annoying-looking code gone, and a more intuitive interface for free.

Yeah I tried looking for some math constants a while back but they didn't seem to be part of the C++ standard library when I did a quick look a while back.
Okay it looks like you gotta do this to get them to work with VS2005 which is what I use:
The "Math Constants" are not defined in Standard C/C++. Therefore, in order to use them, you have to first define _USE_MATH_DEFINES and then include cmath or math.h as below.

If compiling as C++:

#define _USE_MATH_DEFINES

#include <cmath>

But yeah if it was up to me(not really since it has specific guidelines I had to follow) I would've just asked for the number of digits instead of an epsilon value.
It did help me give me practice with comparing floating point numbers and the problems you can run into when doing it so it was a good learning experience.


[Edited by - daviangel on November 3, 2007 8:52:08 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!