Home
Monte Carlo solution for Mathematics × Programming Competition #7
Tags:, , , ,

Monte Carlo solution for Mathematics × Programming Competition #7

September 28, 2017 No Comments algorithms, c / c++, javascript, math, monte carlo, Monte Carlo Simulation, Monte Carlo Simulation Algorithm

math-and-programming Monte Carlo solution for Mathematics × Programming Competition #7 algorithms c / c++ javascript math monte carlo Monte Carlo Simulation Monte Carlo Simulation Algorithm

math-and-programming

A point is chosen randomly in a square. 4 lines are drawn to connect this point with the 4 vertices of this square, such that 4 triangles are formed. Find the probability that all interior angles of the 4 triangles are less than 120°. Give your answer correct to the nearest 3 decimal places.

Bruteforce is the first programming approach that comes to my mind. It is easy to implement and straightforward. One thing to keep in mind is that the point cannot fall exactly on the edge of the square. The coordinates of x and y are incremented by a small number e.g. x += 1e-5, y += 1e-5.

It is not exactly the bruteforce.. because you just can’t simply bruteforce all points… We call it sampling bruteforce where you iterate nearly as many points as possible by a resolution.

Then the answer is just by counting all the valid points divided by total number of points (sampling)

To check if a point is valid, we can just connect (x, y) to four corners, and check these 4 triangles one by one. We need a cosine formula that computes the angles given three 3 sides.

triangle Monte Carlo solution for Mathematics × Programming Competition #7 algorithms c / c++ javascript math monte carlo Monte Carlo Simulation Monte Carlo Simulation Algorithm

triangle

Known 3 sides, we use formula c^2=a^2+b^2−2ab cos(C) to compute the cos values for 3 angles. Then you can compute the angle (in degrees) using the arc-cosine function. Alternatively, we can check the cos(angle) value larger than -0.5 because cos(120 degrees) = -0.5.

The following computes the side given 2 points:

1
2
3

function getSide(x1, y1, x2, y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
function getSide(x1, y1, x2, y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

To check if a triangle has angles smaller or equal to 120 degrees.

1
2
3
4
5
6
7
8
9

function check(x1, y1, x2, y2, x3, y3) {
    var a = getSide(x1, y1, x2, y2);
    var b = getSide(x1, y1, x3, y3);
    var c = getSide(x2, y2, x3, y3);
    var cosc = (a * a + b * b - c * c) / (2 * a * b);
    var cosa = (b * b + c * c - a * a) / (2 * b * c);
    var cosb = (c * c + a * a - b * b) / (2 * c * a);
    return (cosc >= -0.5) && (cosb >= -0.5) && (cosa >= -0.5);
}
function check(x1, y1, x2, y2, x3, y3) {
    var a = getSide(x1, y1, x2, y2);
    var b = getSide(x1, y1, x3, y3);
    var c = getSide(x2, y2, x3, y3);
    var cosc = (a * a + b * b - c * c) / (2 * a * b);
    var cosa = (b * b + c * c - a * a) / (2 * b * c);
    var cosb = (c * c + a * a - b * b) / (2 * c * a);
    return (cosc >= -0.5) && (cosb >= -0.5) && (cosa >= -0.5);
}

If you use Math.acos, the third angle can be computed by tex_766c284459f8e5613caafbfc3a1ba070 Monte Carlo solution for Mathematics × Programming Competition #7 algorithms c / c++ javascript math monte carlo Monte Carlo Simulation Monte Carlo Simulation Algorithm .

1
2
3
4
5
6
7
8
9
10
11

function check(x1, y1, x2, y2, x3, y3) {
    var a = getSide(x1, y1, x2, y2);
    var b = getSide(x1, y1, x3, y3);
    var c = getSide(x2, y2, x3, y3);
    var cosc = (a * a + b * b - c * c) / (2 * a * b);
    var cosa = (b * b + c * c - a * a) / (2 * b * c);
    angle_c = Math.acos(cosc);
    angle_a = Math.acos(cosa);
    angle_b = 180 - angle_c - angle_a;
    return (angle_c <= 120) && (angle_b <= 120) && (angle_a <= 120);
}
function check(x1, y1, x2, y2, x3, y3) {
    var a = getSide(x1, y1, x2, y2);
    var b = getSide(x1, y1, x3, y3);
    var c = getSide(x2, y2, x3, y3);
    var cosc = (a * a + b * b - c * c) / (2 * a * b);
    var cosa = (b * b + c * c - a * a) / (2 * b * c);
    angle_c = Math.acos(cosc);
    angle_a = Math.acos(cosa);
    angle_b = 180 - angle_c - angle_a;
    return (angle_c <= 120) && (angle_b <= 120) && (angle_a <= 120);
}

Now, the bruteforce sampling…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var total = 0;  // Total sampling points
var valid = 0;  //Valid points
 
for (let x = 1e-7; x <= 0.99999; x += 1e-4) {
    for (let y = 1e-7; y <= 0.99999; y += 1e-4) {
        total ++;
        if ( check(x, y, 0, 0, 0, 1) &&
             check(x, y, 0, 1, 1, 1) &&
             check(x, y, 1, 1, 1, 0) &&
             check(x, y, 1, 0, 0, 0)         
        ) {
            valid ++;
        }
    }
}
 
console.log(valid);
console.log(total);
console.log(Math.round(valid / total * 1000) / 1000);  // 3 decimal previsions.
var total = 0;  // Total sampling points
var valid = 0;  //Valid points

for (let x = 1e-7; x <= 0.99999; x += 1e-4) {
    for (let y = 1e-7; y <= 0.99999; y += 1e-4) {
        total ++;
        if ( check(x, y, 0, 0, 0, 1) &&
             check(x, y, 0, 1, 1, 1) &&
             check(x, y, 1, 1, 1, 0) &&
             check(x, y, 1, 0, 0, 0)         
        ) {
            valid ++;
        }
    }
}

console.log(valid);
console.log(total);
console.log(Math.round(valid / total * 1000) / 1000);  // 3 decimal previsions.

The precison for 3 decimal places remain unchanged from incremental step 1-3 to 1e-6 at the cost of incrementing computational resources.

This method is deterministic i.e. if you run the program many times, you will still get exactly same output (answer).

The runtime complexity is O(xy) where x and y are the incrementing steps for x and y coordinate. How about we just want to know roughly probability (we don’t need to know the 4-th or 5-th decimal precision)?

We can use the following Monte Carlo random sampling method. If we have enough sampling points, the probability will be very close to the actual answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

const N = 10000000;
 
for (let i = 0; i < N; ++ i) {
    let x = Math.random(1.0);  // return  [0, 1)
    let y = Math.random(1.0);
    if ( check(x, y, 0, 0, 0, 1) &&
         check(x, y, 0, 1, 1, 1) &&
         check(x, y, 1, 1, 1, 0) &&
         check(x, y, 1, 0, 0, 0)         
    ) {
        valid ++;
    }
}
 
console.log(valid);
console.log(N);
console.log(Math.round(valid / N * 1000) / 1000);
const N = 10000000;

for (let i = 0; i < N; ++ i) {
    let x = Math.random(1.0);  // return  [0, 1)
    let y = Math.random(1.0);
    if ( check(x, y, 0, 0, 0, 1) &&
         check(x, y, 0, 1, 1, 1) &&
         check(x, y, 1, 1, 1, 0) &&
         check(x, y, 1, 0, 0, 0)         
    ) {
        valid ++;
    }
}

console.log(valid);
console.log(N);
console.log(Math.round(valid / N * 1000) / 1000);

Please note that Math.random(1.0) returns [0, 1) where 0 is inclusive, but the error may be negligible because this entire method is based on random sampling, which has slight errors!

Even if you have 0.213 as answer, the valid points count may vary a little bit:

2126142
2127333
2125929
….

So, if you have a small N, the output answer may not be good enough which may be 0.212, 0.214 (the close numbers). The runtime complexity is O(N) where N is the number of sampling points.

If you need a quick answer which may not be that accurate, you may give a N=1e4 where it may output 0.200, 0.205, 0.216, 0.215 … which is roughly 20%. The advantage is quick running time.

However, by incrementing N, you can run it in parallel, either distributed or multi threading/multi cores. Using the C++ Parallel For, we might have the following implementation that runs the Monte Carlo simulations in parallel.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int main() {
    srand(time(NULL)); // seed
    const int N1 = 1000;
    const int N2 = 100000;
    int n = 0;
    int c = 0;
    Concurrency::critical_section cs;
    Concurrency::parallel_for(0, N1, [&](int i) { // Parallel For
        int t = check(N2);  //  Parallel Blocks
        cs.lock(); // Race Conditions
        n += N2;   // Total Sampling points
        c += t;    // Total Valid Points
        cs.unlock();
    });
    cout << "Probability ~= " << setprecision(9) << (double)c / n  << endl;
    return 0;
}
int main() {
    srand(time(NULL)); // seed
    const int N1 = 1000;
    const int N2 = 100000;
    int n = 0;
    int c = 0;
    Concurrency::critical_section cs;
    Concurrency::parallel_for(0, N1, [&](int i) { // Parallel For
        int t = check(N2);  //  Parallel Blocks
        cs.lock(); // Race Conditions
        n += N2;   // Total Sampling points
        c += t;    // Total Valid Points
        cs.unlock();
    });
    cout << "Probability ~= " << setprecision(9) << (double)c / n  << endl;
    return 0;
}

The Monte Carlo and the ‘Sampling’ brute-force methods are all based on sampling.

Monte Carlo Simulation Algorithms to compute the Pi based on Randomness:

nt via Monte Carlo Simulation

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1493 words
Last Post: Steem API/converter (SBD, STEEM, VESTS)
Next Post: SteemSQL Tutorial: How to Get Random Posts on SteemIt?

The Permanent URL is: Monte Carlo solution for Mathematics × Programming Competition #7

Related posts:

  1. How to Add To Favorite using Javascript? We all know that in most modern browsers, you can use the short key Ctrl...
  2. PHP Script to Execute MySQL statements in a text file If you have a few routine SQL statements to execute, you can save them in...
  3. It takes 5 hours on a 8-bit famicom clone (SB2000) to compute 80 decimal places of PI This is just for fun, and of course for those good memories with 8-bit famicom...
  4. Manage WordPress Connections, Settings in One Place for Multiple WordPress Sites on Same Domain I have hosted 4 wordpress sites on the same VPS, similar to the trick described...
  5. Teaching Kids Programming – Remove a Node and Subtree using Depth First Search or Breadth First Search Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms Remove a node (and nodes belong...
  6. Teaching Kids Programming – Breadth First Search Algorithm to Compute the Max Width of a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary tree root, return...
  7. 3 Types of Coding Languages That Will Intrigue & Educate Youngsters Those who learn coding languages are likely to have a bright future ahead of them....
  8. Codeforces: A. Double Cola The problem is from codeforces http://www.codeforces.com/problemset/problem/82/A This is interesting because it seems like those guys...

Leave a Reply