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:
- Count how many grid dots are in a circle(can be done in linear time when using the circle function).
- 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 += 1+(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 += 1+(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:
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
↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓↑↓