Member Avatar for bigwillis234

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

  • 7 Contributors
  • 7 Replies
  • 327 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by Rashakil Fol

Dani AI

Generated

The slow run time comes from scanning many numerators per denominator. For a fixed denominator D the numerator N that minimizes |N/D − pi| is the integer closest to piD, so there is no need to loop from 3.1D to 3.2D. As suggested, loop D from 1 to 1,000,000 and test only the nearest integer(s) to piD — that turns the inner loop into constant work and drops run time from hours to seconds on normal hardware.

#include <cstdio>
#include <cmath>
#include <cstdint>

int main() {
    const long double PI = acosl(-1.L);
    long long bestN = 0, bestD = 1;
    long double bestErr = 1e9L;
    for (long long d = 1; d < 1000000; ++d) {
        long long n = (long long)floor(PI * d);
        for (long long cand = n; cand <= n + 1; ++cand) {
            long double err = fabsl((long double)cand / d - PI);
            if (err < bestErr) { bestErr = err; bestN = cand; bestD = d; }
        }
    }
    std::printf("%lld / %lld\n", bestN, bestD);
}

For a mathematically minimal and instantaneous solution, use continued fractions (the convergents and semiconvergents) as hinted: continued-fraction convergents give the best rational approximations for a denominator bound, and you only need to expand the continued fraction of pi until denominators exceed 1,000,000.

Practical notes: use long double (or higher) for safety, avoid printing or heavy work inside the loop, compile with optimizations (e.g. -O2), and optionally skip reducible candidates with a gcd test as recommended to avoid duplicates. The nearest-n per-D method is simple, correct, and should meet the instructor’s two-minute requirement on modern compilers; continued fractions are the preferred route if the goal is a mathematically provable minimal approximation.

Recommended Answers

All 7 Replies

Member Avatar for Lerner

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?".

Member Avatar for Daishi

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

Member Avatar for Ancient Dragon

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.

Post your program and I'm certain someone will help you with it.

Member Avatar for bigwillis234

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);
Edited by happygeek because: fixed formatting
Member Avatar for Puckdropper

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

Member Avatar for Dave Sinkula

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

Member Avatar for Rashakil Fol

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.