2
\$\begingroup\$

While trying to discover a way to calculate the digits of Pi faster with the Leibniz formula for Pi, I noticed that, if I took two consecuent numbers in the series, and calculate their average, I would get a number incredibly closer to Pi compared to these other two numbers, and furthermore, if I took another consecuent two of these averaged values and, redundantly, average them, again the result would be closer to Pi.

Explanation (Skip this part if you want to see the code)

To understand it more, its like a tree of averages, where the original series is at the bottom, then, every two consecuent terms of the series will have a child, which is their averages. These childs will make another infinite series that converges faster to Pi in the same manner the Leibniz series do(that means bouncing up and down from Pi until slowly stopping into it, like a guitar chord resonating until it stops), so for these childs too we'll calculate the average of each two consecuent terms, and make another child series out of those new childs. This process will repeat until the final series results in only having one final child at the top of the tree, which means we can't average anymore since we need two terms to do so, meaning that that last child is the closest to Pi that this algorithm, if it can be said that way, can get.

The program

For this purpose I have made the following program, it functions with two threads called PiLoopThread and DisplayThread (named that way after my C++ Leibniz series calculator intent), in which the first is in charge of calculating Pi and its averages subseries, and the other of displaying information about the calculations and basically what's going on from time to time. At the start the program first sets up the UI, and then starts the two before mentioned threads.

The methods where the magic happens are nextCicle() and updateAverages().

  • nextCicle() is in charge of updating PI, LastPI (for calculating the average), and the cicle Count.
  • updateAverages() updates the averages tree by using an ArrayList of all the previous "top-most childs". It first appends the average of PI and LastPI at the end of the ArrayList ( i = listSize - 1 ), then if there is a previous element from that element ( i--; i >= 0 ), it becomes the average of those both elements (list.set( i , average( list.get(i), list.get(i+1) ) )), and that continues until there are no more previous elements to reaverage ( i >= 0 equals false ). That's made that way so the BigDecimals to store during the life of the program are the minimum.

The Problem

What I want to know is if my code is precise and can perform relatively well. Since this is the first time I'm using BigDecimals, I'm not very confident in that I've used them well and that my program will use too much memory, so a review on them would be nice :)

All the important code is in the BDFuncs.java and, of course, Vars.java :

Vars.java

package picalculator;

import java.math.BigDecimal;
import java.math.MathContext;
import java.util.ArrayList;

public class Vars {

    public static final BigDecimal ZERO = new BigDecimal("0" );
    public static final BigDecimal ONE = new BigDecimal("1");
    public static final BigDecimal TWO = new BigDecimal("2");
    public static final BigDecimal FOUR = new BigDecimal("4");

    public static BigDecimal LastPI = ZERO.plus();
    public static BigDecimal PI = new BigDecimal( "0.0", MathContext.DECIMAL128 );
    public static BigDecimal Count = new BigDecimal("0");

    public static ArrayList<BigDecimal> PIAvgs = new ArrayList<>( 1000000 );

    public static boolean shouldStop = false;

    public static final Object piLock = new Object();

}

BDFuncs.java

-Note: nextCicle() is executed in a loop that looks like the following pseudocode: "while !shouldStop do nextCicle() and then sleep for 1ms".

package picalculator;

import java.math.BigDecimal;
import java.math.MathContext;
import static picalculator.Vars.*;

public class BDFuncs {

    // The magic happens here
    // This function calculates the next PI in the series, as well as the actual child series while creating other news (see updateAverage()). 
    public static void nextCicle() {
        synchronized ( piLock ) {
            LastPI = PI.plus();
            if ( shouldSubstract() ) PI = PI.subtract( getCicleTerm() );
            else PI = PI.add( getCicleTerm() );
            updateAverage();
            Count = Count.add( ONE );
        }
    }

    private static BigDecimal getCicleTerm() {
        return ONE.divide( Count.multiply( TWO ).add( ONE ), MathContext.DECIMAL128 );
    }

    private static boolean shouldSubstract() {
        if ( Count.remainder( TWO ).compareTo( ONE ) == 0 ) return true;
        else return false;
    }

    // This function works by calculating ONLY the averages at the last side of the tree.
    // It first calcles the last average of the first child series, and then using that
    // average and the last average of the same child series(if any), calculates its average
    // and sets it as the second child series' last child, repeating so until it reaches the
    // top of the tree, or in this case, while the index is more or equal than 0.
    private static void updateAverage() {
        PIAvgs.add( average( LastPI, PI ) );
        for ( int i = PIAvgs.size() - 2; i >= 0; i-- ) {
            PIAvgs.set( i, average( PIAvgs.get( i ) , PIAvgs.get( i + 1 ) ) );
        }
    }

    private static BigDecimal average( BigDecimal bd1, BigDecimal bd2 ) {
        return bd1.add( bd2 ).divide( TWO );
    }

    public static BigDecimal[] getData() {
        BigDecimal[] tempArr = new BigDecimal[3];
        synchronized ( piLock ) {
            tempArr[0] = PI.plus();
            tempArr[1] = ( PIAvgs.isEmpty() ? ZERO : PIAvgs.get(0) );
            tempArr[2] = Count.plus();
        }
        return tempArr;
    }

}

Here is a screenshot of the working program:

PiCalculator

As you can see, it managed to get Pi with just averaging right up to the 34th digit in just 120 Leibniz term calculations that just took less than 1 sec, so, yeah, wow.

It just gets up to there though since apparently BigDecimal can only get up to 34 digits of exact precision using MathContext.DECIMAL128 :P

You can download the jar from here.

If you want the full source code ( plus the .jar ) you can download it from here too for the NetBeans IDE.

\$\endgroup\$
3
\$\begingroup\$
public class Vars {

    ...

    public static BigDecimal LastPI = ZERO.plus();
    public static BigDecimal PI = new BigDecimal( "0.0", MathContext.DECIMAL128 );
    public static BigDecimal Count = new BigDecimal("0");

    public static ArrayList<BigDecimal> PIAvgs = new ArrayList<>( 1000000 );

    public static boolean shouldStop = false;

Why?

Firstly, why are the variables deliberately placed in a different scope to the code which operates on them?

Secondly, why are they static? For that matter, why is everything in BDFuncs static?

Thirdly, why the inconsistency in the capitalisation? ALL_CAPS in Java convention is reserved for constants; other fields should be in lowerCamelCase.


    public static void nextCicle() {

FWIW the correct spelling is cycle.

        synchronized ( piLock ) {
            LastPI = PI.plus();

Why .plus()? That method literally does nothing.

            if ( shouldSubstract() ) PI = PI.subtract( getCicleTerm() );
            else PI = PI.add( getCicleTerm() );

Why doesn't the term include its sign, so that you always add? That would be more mathematically coherent and would make it easier to understand the code because it would remove the requirement to call the methods in the right order.

            updateAverage();
            Count = Count.add( ONE );

This seems like the appropriate place to ask why Count is a BigDecimal rather than just an int.


If you want to minimise the errors then as a rule of thumb you should add the terms in increasing size, i.e. starting with the last one. This is a problem for iterative refinement: serious calculation would not just iterative refinement.


    private static void updateAverage() {
        PIAvgs.add( average( LastPI, PI ) );
        for ( int i = PIAvgs.size() - 2; i >= 0; i-- ) {
            PIAvgs.set( i, average( PIAvgs.get( i ) , PIAvgs.get( i + 1 ) ) );
        }
    }

It's not clear to me from reading the code that it actually has the same tree structure as defined in the question. Comments giving the invariants might clarify this - or maybe it is not, in fact, the case.


Finally, let me propose some reading for you:

\$\endgroup\$
  • \$\begingroup\$ The Van Wijngaarden's Transform seems to be exactly what I'm doing, I'll dive into it in more detail. Sorry for my malformed and sometimes incoherent code, it's the first time I've used Java in a while and also the first time I used BigDecimals. I'm not exactly a pro when it comes to coding, that's why I was coming to this site, to see if I was heading my code the right way, but reading and tasting the answer policy of this site suggest there might be a better Stack Exchange site for that. Anyways, thanks for the review, I'll update my code and the question if possible :) \$\endgroup\$ – Nikko77 Mar 21 at 16:51
  • \$\begingroup\$ The subtle difference is that van Wijngaarden gets better results by not carrying it out fully. Don't update the question: the changes will be rolled back. However, once you've considered all the feedback received and applied that which you agree with, you can post a new question. See the meta FAQ on options for follow-ups. \$\endgroup\$ – Peter Taylor Mar 21 at 19:36

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.