# Calculating Pi by Leibniz formular

By | May 17, 2016

## Problem

This is to calculate an approximation to the constant Pi (π).

## Solution

### 1.1. Computation

fomular will take O(m) steps –linear algorithm or time complexity is O(m) .

The Leibniz series converges very slowly if m approaches infinity.  To calculate pi to one million decimal places would require 106 terms.

### 1.2 Calculate the nth digit of accuracy for π,

Now we need to find an m with absolute of   (1)

First of all, we solve the in-equation with two cases to find out an m

• If k is odd number, then (1) is always true with any n ≥0.
• If k is even number: time. The following table will illustrate correlation of nth digit of accuracy and k number.
n th digit of accuracy π example k >=
3 3.14 500
5 3.1415 50,000
8 3.1415926 50,000,000
10 3.141592653 5,000,000,000

Table 1: Correlation of n th digit of accuracy and its input data (k).

### 1.3 Efficiency:

Suppose that we use many threads to implement the calculation instead of processes. There are some cases in which performing tasks in parallel can be used in this example.

• Tasks are independent of each other, but calculate the same thing.
• Tasks are limited by slow operations. For example, network access or disk access. It means we will divide the big number into smaller number and then assign to multi PCs to process it throughout a network.

To regard with the first case, some scenarios will be carefully considered as the following:

• Multi-threads and a single processor. If the code running on multiple threads is accessing the same memory, then the CPUs will have to synchronize memory access which could reduce the actual performance improvement.

• Multi-threads and multi-processors: Idea that the calculation can be solved faster with more CPUs concurrently. If we want to have parallel speed up and know p as the fraction of the programing’s code that can be made parallel (p ≤ 1.0).

Refer to Amdahl’s Law: Speedup (n) Given p

## Implementation

### Class implementation detail

1. Main class

```package com.example;

import java.util.Scanner;
import org.springframework.context.ApplicationContext;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;
import com.example.config.AppConfig;
import com.example.service.CalculationService;

/**
* Main application shows execution of getting PI.
*/
public class Main {
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
ApplicationContext context;
final CalculationService&lt;Double&gt; calculationService;
context = new AnnotationConfigApplicationContext(AppConfig.class);
calculationService = context.getBean(CalculationService.class);

// Thread to listen enter key press
public void run() {
System.out.println("\nStart calculating... Press Enter if you want to cancel");
Scanner s = new Scanner(System.in);
s.nextLine();
calculationService.cancel();
}
};
t.setDaemon(true);
t.start();

//start to input n
String[] parameters = args;
try {
Double result = calculationService.execute(parameters);
System.out.println("Result: " + result.toString());

} catch (Exception e) {
System.out.println(e.getMessage());
System.out.println("Usage: java -jar examplePi-jar-with-dependencies.jar n");
System.out.println("Example: java -jar examplePi-jar-with-dependencies.jar 100000");
}
}
}
```

2. Job Interface: A job needs to be execute

```package com.example.service;

import java.util.concurrent.Callable;
/**
* Interface of job.
* @param &lt;T&gt;
*/
public interface Job&lt;T extends Number&gt; extends Callable&lt;T&gt;{
}
```

3. JobProvider Interface: Provide methods to process jobs.

```package com.example.service;

import java.util.List;
import org.springframework.stereotype.Service;
/**
* interface of JobProvider
* @param &lt;T&gt;
*/
@Service
public interface JobProvider&lt;T extends Number&gt; {
boolean hasNext();
Job&lt;T&gt; get();
List&lt;Job&lt;T&gt;&gt; get(int count);
}
```

4. JobProviderImpl : Implement jobProvider.

```package com.example.service.pi;

import java.util.ArrayList;
import java.util.List;

import com.example.service.Job;
import com.example.service.JobProvider;
import com.example.utils.Constants;
/**
* Implement Job Provider.
*
*/
public class JobProviderImpl implements JobProvider&lt;Double&gt; {
private long n;
private JobImpl currentJob = new JobImpl(-1, -1);

public JobProviderImpl(long n) {
this.n = n;
}
/**
* Get a new job
*/
public JobImpl get() {

//Check whether there is a new job or not
if (currentJob.getLast() &gt;= n) {
return null;
}

//Update last job by adding a constants of job size
long last = currentJob.getLast() + Constants.JOB_SIZE;

//check last job if incremental last is greater than n, assign n to last
if (last &gt; n) {
last = n;
}

//Create a new job
currentJob = new JobImpl(currentJob.getLast() + 1, last);
return currentJob;
}
/**
* Get list of job by adding each job arrayList
* @return list of jobs
*/
public List&lt;Job&lt;Double&gt;&gt; get(int count) {
List&lt;Job&lt;Double&gt;&gt; jobs = new ArrayList&lt;Job&lt;Double&gt;&gt;(count);
for (int i = 0; i &lt; count; i++) {
JobImpl j = get();
if (j == null) {
return jobs;
}
}

return jobs;
}

/**
* Check whether there is a new job or not
* @return true if having a new job, false otherwise
*/
public boolean hasNext() {
return currentJob.getLast() &lt; n;
}

}
```

5. CalculationService interface: Provide execute and cancel services

```package com.example.service;

/**
* Interface for calculation service
*
*/
public interface CalculationService&lt;T extends Number&gt; {

/**
* execute a list of jobs basing on batch size which are provided by job.
* provider.
* @param parameters string input
* @return result
* @throws Exception
*/
T execute(String[] parameters) throws Exception;
/**
* Cancel execute the job.
*/
void cancel();
}

```

6. BaseCalculationServiceImpl class: Implement Calculation services

```package com.example.service;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
* Implement calculation services
*
*/
public abstract class BaseCalculationServiceImpl&lt;T extends Number&gt; implements
CalculationService&lt;T&gt; {

private JobProvider&lt;T&gt; jobProvider;
private int batchSize = Runtime.getRuntime().availableProcessors();
private boolean cancelled = false;

public BaseCalculationServiceImpl() {

}

/**
* Cancel executing once pressing the key
*
*/
public void cancel() {
cancelled = true;
}

/**
* execute a list of jobs basing on batch size which are provided by job
* provider.
* @param parameters user input n
* @throws Exception
* @return T result of pi
*/
public T execute(String[] parameters) throws Exception {

// parse a parameter for Pi
parseParameters(parameters);

// create job provider
jobProvider = createJobProvider();

// Executing until jobProvider runs out of jobs or being cancelled.
while (jobProvider.hasNext() &amp;&amp; !cancelled) {
List&lt;Job&lt;T&gt;&gt; jobs = jobProvider.get(batchSize);
execute(jobs);
}

// Shutdown executor
executor.shutdown();
return getResult();
}

/**
* Execute jobs of batch size.
* @param jobs a list of jobs need to be executed
* @throws InterruptedException
* @throws Exception
*/
private void execute(List&lt;Job&lt;T&gt;&gt; jobs) throws InterruptedException,
Exception {
List&lt;Future&lt;T&gt;&gt; futures = new ArrayList&lt;Future&lt;T&gt;&gt;(jobs.size());

// for loop to submit job to executor
for (Job&lt;T&gt; j : jobs) {
Future&lt;T&gt; f = executor.submit(j);
}

for (Future&lt;T&gt; f : futures) {
}
System.out.println("Current job:"
+ jobs.get(jobs.size() - 1).toString());
System.out.println("Current result:" + getResult());
}

protected abstract JobProvider&lt;T&gt; createJobProvider();

protected abstract T getResult();

protected abstract void parseParameters(String[] parameters)
throws IllegalArgumentException;
}
```

7. CalculationServiceImpl class: Implement calculation services for Pi

```package com.example.service.pi;

import com.example.service.BaseCalculationServiceImpl;
import com.example.service.JobProvider;
import com.example.utils.Constants;

/**
* Implement calculation services for Pi.
*
*/
public class CalculationServiceImpl extends BaseCalculationServiceImpl&lt;Double&gt; {
private Double result = 0D;
private long n = 0;

/**
* Parse parameters for Pi.
*
* @throws IllegalArgumentException
*/
protected void parseParameters(String[] parameters) throws IllegalArgumentException {
long temp = 0;
if (parameters.length &lt; 1) {
}
try {
temp = Long.parseLong(parameters[0]);
if(temp &lt; 0 || temp &gt; Constants.MAX_N) {
throw new IllegalArgumentException("N must be in range 0.." + Constants.MAX_N);
}
n = temp;

} catch (Exception e) {
throw new IllegalArgumentException("N must be in range 0.." + Constants.MAX_N);
}
}
/**
* Create JobProvider.
*/
protected JobProvider&lt;Double&gt; createJobProvider() {
return new JobProviderImpl(n);
}
/**
* Add current pi to result.
* @return result of pi
*/
@Override
result += t;
return result;
}

/**
* Get final result of pi.
* @return result of pi
*/
@Override
protected Double getResult() {
return result;
}
}
```

8. LeibnizFormula: Implement Leibniz Formula

```package com.gbst.example.service.pi;
/**
* Calculate Leibniz formular.
* @author tdinhkhiem
*/
public class LeibnizFormula {
/**
* No instance is needed.
*/
private LeibnizFormula() {
}
public static double calculate(long start, long end) {
double result = 0.0;
int sign = start % 2 == 0 ? 1 : -1;

for (long i = start; i &lt;= end; i++) {
result += sign / (2.0 * i + 1);
sign = -sign;
}
return result * 4;
}
}
```

### Testing

```package com.example;

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;
import org.springframework.context.ApplicationContext;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;

import com.example.config.AppConfig;
import com.example.service.CalculationService;
/**
*
*/
public class MainTest {

private CalculationService&lt;?&gt; calculationService;

@Before
public void initialize(){
ApplicationContext context = new AnnotationConfigApplicationContext(
AppConfig.class);
}

/**
* Test case for execute, and getPiResult methods.
* @throws Exception
*/
@Test
public void testExecuteTaskWithoutError() throws Exception {

String[] parameters = {"10000"};
Double result = (Double) calculationService.execute(parameters);
System.out.println("Result: " + result.toString());

double expected = 3.1416926435905432;
assertEquals(expected, result, .00000000001);
}

}
```

## Build and Run project

### Build

Using Maven

```Package it: \$ mvn package
```

Two jar files will be created in target folder

• examplePi.jar: Only project classes
• examplePi-jar-with-dependencies.jar: Project and dependency classes in a single jar

### Run

```\$java -jar target/examplePi-jar-with-dependencies.jar 5000

Start calculating... Press Enter if you want to cancel
Current job:Job [first=0, last=5000]
Current result:3.1417926135957908
Result: 3.1417926135957908
```