hi. new here. Im a freshman at UCSB and im taking my first c++ class. I got this assignment in class and i was hoping for some tips.

The value of pi to 15 decimal places is PI = 3.141592653589793 . . . Your job is to write a
program that can be used to find decent approximations to PI. More specifically, your program must find
integers N and D such that the fraction N/D is the best possible approximation to PI and such that D <
1,000,000.

I have already set up nested while loops to chug through the fractions and limited the numerator to n <= 3145926. I also set a if condition right in between the while to reduce the numer of times it goest through the calculations by narrowing the numbers between 3 and 4( like pi). such that if( 3*d < n && 4*d > n){

Now the thing works but it takes about 6 hrs to run and for this project the instructor wants us to make one that runs in 2 min or less. I was wondering if anyone has any tips that may help.
thank you
bw

## All 7 Replies

If you post code (using code tags) someone may be willing to take a stab at helping you. Without posting code it's like asking "how can I reduce the time it takes me to file out my tax return?".

Well, try all numbers from D to 1,000,000. I was able to write a program that calculates this in under 20 seconds.

BestPi: 3.141592653588651 3126535/995207

I used one loop that went from D equals 1 to 1,000,000, the interior loop is where it gets tricky. Like you said, the ratio of N/D has to be between 3 and 4...

3 < N/D < 4
3*D < N < 4*D

That's all you get without posting your code.

-Fredric

Now the thing works but it takes about 6 hrs to run

LMAO :lol: :lol: :lol: Sorry for laughing so much! But the last time I heard something like that was way back in 1987 on an old Unix computer -- the program (no, I didn't write it) took 48 hours to run. I rewrite it in C and got it to run in under 10 minutes.

this is what i got now. it still takes a long time. like an hour

``````int n, d=1, n2, d2;
double pie= 3.141592643563118, guess, piguess = 3.15;

int main()
{

while(d <= 1000000) {     /* d goes to 1000000 */
n=3.1*d;               /* started n at 3.1 * to get right to pi area*/
while(n <= 3.2*d ){    /*shortened loop for values */

guess = fabs(((double)n/d) - pie); /*abs value to compare guess*/
if( guess < piguess ){
n2= n;
d2= d;
piguess= guess;

}n++;
}d++;
}

printf( "%d / %d", n2, d2);
``````

Algorithm efficiency is dependant upon eliminating fluff. For example, eliminate reducable fractions. (You've already tested it before... 1/3 ======= 2/6)

And you may want to break out of the loop when you find an answer.

A method based on continued fractions will get you the answer in less than a millisecond.

(Ooh I'm being so unhelpful :twisted: )

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.