0
$\begingroup$

So in my APCS class today we played around with generating pi, and approximating to a user defined number of places. We used the Leibniz formula for π. As we began playing around with it we tried throwing in 2147483647, the largest value for an int, but noticed it wasn't going to finish anytime soon. I googled runtime analysis a bit and am wondering how I would graph the complexity of the program. The function appears to be logarithmic, but I figure that as the complexity increases with each calculation, so would the complexity, but when i graphed it as a Riemann sum, it was a negative value with a slope of 0. Why would that be? I attached my code.

public class pi_calculator
{

public static void main(String [] args) {
Scanner scan = new Scanner (System.in);
int numberOfTerms = 0; {
numberOfTerms += scan.nextInt();
double startTime = System.nanoTime();
double piSum = 0;

if ( numberOfTerms > 0 && numberOfTerms <= 2147483647 ) {
   for( int i = 0; i <= numberOfTerms; i++ ){
        piSum += 4.0 * (Math.pow(-1, i)/(2*i+1));
   }
   double endTime = System.nanoTime();
   double duration = (endTime - startTime)/1000000;
   System.out.print( "Your pi estimate: " + piSum +"\n in: " + duration + "ms" );
}
else {

 System.out.print("ERROR");
}


}
}}
$\endgroup$
  • 1
    $\begingroup$ This algorithm should be $O(n)$, where $n$ is the number of series terms you compute, and that is due to the fact you're computing a sum using a simple for loop. I am confused what plot you're saying you created that had a negative slope? You should add that to your post to help explain your confusion and maybe help me see what I might be missing when I read this problem over. $\endgroup$ – spektr Feb 14 '17 at 4:37
  • 3
    $\begingroup$ By the way... en.wikipedia.org/wiki/Shanks_transformation It's an odd thing about numerical analysis that one of the worst things you can do with a series is sum it. $\endgroup$ – Pseudonym Feb 14 '17 at 4:45
  • 1
    $\begingroup$ The complexity of each iteration should be exactly the same. Each floating point operation takes $O(1)$, regardless of the values involved. If that's what you plotted, it's no surprise that you didn't see any difference. $\endgroup$ – Yuval Filmus Feb 14 '17 at 8:15
  • 1
    $\begingroup$ If your int is indeed a 32 bit signed integer, then your loop will never finish, since MAX_INT+1=MIN_INT. $\endgroup$ – Yuval Filmus Feb 14 '17 at 8:15
  • 1
    $\begingroup$ @gnasher729 This is just bad coding style anyway. Note that pow is a floating point operation. $\endgroup$ – Yuval Filmus Feb 14 '17 at 10:54
2
$\begingroup$

This should really go in codereview.stackexchange.

In many languages, increasing the maximum possible int value either invokes undefined behaviour or produces the minimum possible value or both. If numberOfTerms == 2147483647 your code is most likely to never finish.

The execution time will be awful because you call a very expensive function Math.pow just to get a sequence that alternates between +1 and -1. Don't translate formulas literally, use your brain first. If numberOfTerms == 2147483646 then your code is quite likely not to finish before you give up.

The Leibniz formula is just awful to calculate π. To find n significant digits, you need to add $O (10^n)$ terms. Your function will never be as precise as the 3.141592653589 that I can quote from memory.

You have significant numerical problems because you will have rounding errors that are adding up badly, so I doubt you will get more than 8 digits correct ever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.