Calculating Pi by Leibniz formular

By | May 17, 2016

Problem

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

pi-formular

Solution

1.1. Computation

f(x) = sum{k=0}{m}{(-1^k)/(2k+1)} 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 pi  <= 1/10^n   (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: -1^k/(2k+1) <=   1/10^n doubleleftright 10^n < 2k+1 doubleright k >= (10^n-1)/2″ title=”-1^k/(2k+1) <=   1/10^n doubleleftright 10^n < 2k+1 doubleright k >= (10^n-1)/2″/>   (2)</li>
</ul>
<p>Thus, we need to take the serial out to (2) to be sure that we have n digit of accuracy. This also means that the algorithm runs in <img src=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

      Speed up (n) = 1/(p/n + 1-p)

    Implementation

    Class diagram

    pi-class-diagram

    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
    Thread t = new Thread() {
    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();
    Thread.sleep(2000);
    
    //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;
    }
    jobs.add(j);
    }
    
    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 ExecutorService executor = Executors.newFixedThreadPool(batchSize);
    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);
    futures.add(f);
    }
    
    //Get result from future task
    for (Future&lt;T&gt; f : futures) {
    addToResult(f.get());
    }
    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 T addToResult(T t);
    
    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) {
    throw new IllegalArgumentException("Please provide N");
    }
    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
    protected Double addToResult(Double t) {
    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;
    /**
    * Test methods of executableTaskImple
    *
    */
    public class MainTest {
    
    private CalculationService&lt;?&gt; calculationService;
    
    @Before
    public void initialize(){
    ApplicationContext context = new AnnotationConfigApplicationContext(
    AppConfig.class);
    calculationService = (CalculationService&lt;?&gt;) context.getBean("executableTask");
    }
    
    /**
    * 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
    

    Download sourcecode:ExamplePI-Leibniz

    Acknowledgment

    Thank Mr. Tin Bui for his review.
    I believe that community will help improve much better so I share it.

    References:

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.