Computation Contest #7 Results and Solution


Solution

The problem of this contest was to test two methods to approximate pi and measure how accurate they get compared to how many digits it gets right.
I wrote a simple code which uses the following two methods:

  1. Count how many grid dots are in a circle(can be done in linear time when using the circle function).
  2. Use the following sequence to apprixmate it:

I decided to go with a maximum accuracy of twenty binary digits. Here is my code

import javax.swing.JFrame;
import java.awt.Graphics;
import java.awt.Color;

public class abcd extends JFrame {
    int[] firstMethod;
    int[] secondMethod;
    public abcd() {
        setSize(800, 400);
        setVisible(true);

        doFirstMethod();
        doSecondMethod();
        repaint();
    }
    // return accuracy in bits:
    public int getAccuracy(double approx) {
        if((int)approx != 3)
            return 0;
        long approxL = Double.doubleToLongBits(approx);
        long piL = Double.doubleToLongBits(Math.PI);
        long mantissaStart = 0x0008000000000000L;
        int prec = 0;   
        for(long i = mantissaStart; i >= 0; i >>= 1) {
            if((approxL & i) != (piL & i))
                return prec;
            prec++;
        }
        return prec;
    }
    public void doFirstMethod() {
        firstMethod = new int[20];
        int index = 0;
        for(int i = 0; index < 20; i >>3)) {
            double π = countDots(i);
            int numDigits = getAccuracy(π);
            if(numDigits >= index+1) {
                // Repeat the calculation a couple of times to increase time accuracy
                long t1 = System.nanoTime();
                for(int j = 0; j < 1000000; j++)
                    getAccuracy(π);
                long t2 = System.nanoTime();
                firstMethod[index] = (int)((t2-t1)/1000000.0);
                index++;
            }
        }
    }
    public void doSecondMethod() {
        secondMethod = new int[20];
        int index = 0;
        for(int i = 0; index < 20; i >>3)) {
            double π = sumUp(i);
            int numDigits = getAccuracy(π);
            if(numDigits >= index+1) {
                // Repeat the calculation a couple of times to increase time accuracy
                long t1 = System.nanoTime();
                for(int j = 0; j < 1000000; j++)
                    getAccuracy(π);
                long t2 = System.nanoTime();
                secondMethod[index] = (int)((t2-t1)/1000000.0);
                index++;
            }
        }
    }

    // Use the partial sums of the infinite sequence sum 1/n² = π²/6:
    public double sumUp(int n) {
        double sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += 1.0/i/i;
        }
        return Math.sqrt(sum*6);
    }

    // Counts how many grid points lie in-/outside a quarter circle. Kind of similar to integrating the circle function.
    public double countDots(int r) {
        long num = 0;
        long rSqr = r*r;
        for(int i = 0; i < r; i++) {
            num += (long)(Math.sqrt(rSqr-i*i)); // Use the floor function to find the number of grid points inside the circle at this position.
        }
        return 4*num/(double)rSqr;
    }

    public void paint(Graphics g) {
        g.setColor(Color.BLACK);
        for(int i = 1; i < 20; i++) {
            g.drawLine(i*10, 200-firstMethod[i-1], i*10+10, 200-firstMethod[i]);
            g.drawLine(200+i*10, 200-secondMethod[i-1], 200+i*10+10, 200-secondMethod[i]);
        }
    }

    public static void main(String[] args) {
        new abcd();
    }
}

This code outputs the following two graphs:
Screenshot from 2019-12-14 19-52-06.png
Not much to see except from the fact that both graphs are growing kind of linear.
↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

List of participants with their entries:

Name Solution found Comment
@lallo Integrating the circle function Strange that your function seems to grow exponentially, while mine are at least on the scale I observed mostly linear. Probably python is doing something strange?

↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

Winners:

Congratulations @lallo, you won 2 SBI!

↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓

The next contest starts tomorrow. Don't miss it!


Comments 6


A member bonus $trendotoken tip, and !trendovoter, for @quantumdeveloper from MAPXV! These bonuses are for members, selected at random, and last for a few days.

Also consider our MAPR fund and MAXUV vote bonds too.
MAP Steem Fintech: growing your STEEM without SP.

14.12.2019 19:18
0

Congratulations @mapxv, you successfuly trended the post shared by @quantumdeveloper!
@quantumdeveloper will receive 4.40698725 TRDO & @mapxv will get 2.93799150 TRDO curation in 3 Days from Post Created Date!

"Call TRDO, Your Comment Worth Something!"

To view or trade TRDO go to steem-engine.com
Join TRDO Discord Channel or Join TRDO Web Site

14.12.2019 19:18
0

Congratulations @mapxv, 55.45% upvote has been shared with your successful call on the post that shared by @quantumdeveloper!


Support b>@trendotoken projects by delegating : 100SP , 200SP , 500SP , 1000SP , 2000SP

14.12.2019 19:18
0

A bonus $trendotoken tip from ONECENT!
Also consider MAPR fund and MAXUV vote bonds too.
MAP Steem FinTech: growing your STEEM without SP.

14.12.2019 19:19
0

I think in my case it grows exponentially because my algorithm doesn't stop when a certain level of precision is achieved, but it stops after doing n iterations.
So it depends on the input that is exponential. But I'm not sure.
I should modify the algorithm and find the exactly number of iteration and time needed to achieve 1,2,3,4,5,... decimal digits correct. And see if it changes.

14.12.2019 20:00
0

Congratulations @quantumdeveloper, your post successfully recieved 4.40698725 TRDO from below listed TRENDO callers:

@mapxv earned : 2.9379915 TRDO curation


To view or trade TRDO go to steem-engine.com
Join TRDO Discord Channel or Join TRDO Web Site

17.12.2019 19:31
0