-2

I am currently working on an exercise where I have to use the sum in the picture to approximate pi. sum to approximate pi. I have to prompt the user for an integer m which will be the number of terms used to do the calculation. I cannot use any functions from the math library.

I have written the following code so far:

#include <iostream>
using namespace std; 


int factorial (unsigned int f );
double sum2 (unsigned int m );


double sum2 (unsigned int m=1 ){
    double pi_half = 1.0;

    for(int i = 1; i < m ; i++){
        pi_half +=(factorial(i) /factorial(2.0 * i + 1)); /* compiler warning: narrowing conversion from 'double' to 'int' */
    }
    return (2*pi_half + 1 );
}

int factorial (unsigned int f ){
    int fact =1;
    for(int i= f ; i > 0 ; i--){
        fact *= i;
    }
    return fact;
}


int main (){

    unsigned int m{};
    cin >> m;

   cout << sum2(m);
    return 0;
}

my idea was to create two functions: one to calculate the factorial and one to calculate pi. The factorial function on its own is working fine. When I call sum2 to however it is not working and I get a long exit code and the compiler warning I have indicated in the code. Could somebody tell my what my mistakes are?

Thank you in advance for your help!!

Marek R
  • 32,568
  • 6
  • 55
  • 140
lolamay
  • 11
  • 1
    you have integer overflow in `factorial`. There is better way to calculate division of factorials. – Marek R Jul 25 '23 at 08:44
  • 1
    `factorial` returns an `int` and a bigger number for bigger inputs. So ignoring possible overflows, `factorial(i) /factorial(2.0 * i + 1)` will be a smaller `int` divided by a bigger `int`, which is `0`. – mch Jul 25 '23 at 08:45
  • *Could somebody tell my what my mistakes are?* [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – PaulMcKenzie Jul 25 '23 at 08:53
  • 1
    *The factorial function on its own is working fine.* -- It will not work "fine" if the result will be greater than what an `int` can hold. Did you really test it thoroughly? – PaulMcKenzie Jul 25 '23 at 08:55
  • Don't use a factorial or related function. (a) It will rapidly overflow any integer type. (b) It is highly inefficient here, as you are computing partial products already computed. Note that each term is a simple multiple of the previous one, and use that fact (as a double). – lastchance Jul 25 '23 at 08:57
  • 2
    Your mistakes are (1) calculating factorials over and over and over and over again; and (2) using integer division. Re. (1), observe that (1x2x3)/(3x5x7) = (1x2)/(3x5) x (3/7) Given the nth term you can calculate the n+1th term extremely fast without recalculating the same factorials again. Re. (2), use `double` throughout. – n. m. could be an AI Jul 25 '23 at 08:59
  • https://godbolt.org/z/vY1jKdsej – Marek R Jul 25 '23 at 09:00
  • [Your factorial function will not work as you believed it does](https://godbolt.org/z/3a3cbzrvT). Note that after factorial(13), everything falls apart. – PaulMcKenzie Jul 25 '23 at 09:01
  • Yeah and of course the Nth term is most definitely not `n!/(2n+1)!`. – n. m. could be an AI Jul 25 '23 at 09:26
  • Use ```term *= i / ( 2.0 * i + 1.0 ); result += term;``` in a loop, with term and result initialised to 1.0. It doesn't converge all that fast, though: terms are (roughly) halved at each stage. – lastchance Jul 25 '23 at 09:28

1 Answers1

0

Ad already pointed out in comments, your factorial function will overflow fairly quickly.

Another flaw is that you recalculate the whole factorials at each iteration, which would be a huge waste of computational time.

Usually, maths formulas are not to be directly implemented as such. We need to "translate" them in order to take into account the machine rules and limitations.

In this case, we can see that each term is dependent on the previous one. Indeed, (1x2)/(3x5) == (1/3) x (2/5) and (1x2x3) / (3x5x7) == (1x2)/(3x5) x (3/7) and so on...

If we consider the formula like above, we solve both issues at the same time. First, we do not recalculate everything everytime (we only have a multiplication at each iteration), and second, we maintain a stable term (we only multiply divisions with greater denominators than numerators), i.e. no overflow anymore.

A possible implementation would be:

double pi_ne(unsigned int nb_iter)
{
    double sum = 1;      // The resulting sum
    double a = 1;        // The term to add at each iteration
    double n = 1, d = 3; // The n/d term to multiply to a at each iteration

    for(std::size_t i = 0; i < nb_iter; ++i)
    {
        a *= n/d;       // Update a
        sum += a;       // Update the sum

        // Update the n/d term
        ++n;
        d += 2;
    }

    return 2*sum;
}

Live example here

Fareanor
  • 5,900
  • 2
  • 11
  • 37