# Leibniz formula for π

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");
}

}
}}

• 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. – spektr Feb 14 '17 at 4:37
• 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. – Pseudonym Feb 14 '17 at 4:45
• 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. – Yuval Filmus Feb 14 '17 at 8:15
• If your int is indeed a 32 bit signed integer, then your loop will never finish, since MAX_INT+1=MIN_INT. – Yuval Filmus Feb 14 '17 at 8:15
• @gnasher729 This is just bad coding style anyway. Note that pow is a floating point operation. – Yuval Filmus Feb 14 '17 at 10:54

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.