Problem 5 Pi calculation

The idea: estimate π by throwing darts

Monte Carlo π rests on a ratio. Inscribe a circle of radius 1 inside a square spanning [-1, 1] on each axis. The square has area 2 × 2 = 4; the full circle has area π × 1² = π. If you scatter darts uniformly at random across the square, the fraction that land inside the circle converges to the ratio of the two areas:

hits / throws → π / 4, so π ≈ 4 × hits / throws.

A “dart” is one random point (x, y) with each coordinate drawn uniformly from [-1, 1]. It counts as a hit when x² + y² ≤ 1 — that is, when it falls inside the unit circle. More throws means a tighter estimate; the error shrinks like 1 / √throws, which is exactly why we want millions of darts and therefore want to parallelize.

Why this parallelizes cleanly

Each dart is independent of every other dart. A thread does not need to know what any other thread threw to decide whether its own point is a hit. That makes this a textbook partition → map → reduce workload, the same shape as the linear-search and min/max/sum problems:

• Partition — split the total throw budget N across K threads, so each thread is responsible for about N/K throws.
• Map — each thread throws its share of darts and keeps a private hit counter. No shared mutable state during the hot loop, so there are no locks and no contention.
• Reduce — after every thread finishes, the main thread sums the per-thread hit counts into one total and applies 4 × total_hits / N.

The private counter is the load-bearing detail. If all threads incremented one shared count, every increment would be a read-modify-write race and you would lose hits (see Pitfalls). Giving each thread its own counter and combining once at the end removes synchronization from the part of the program that runs billions of times.

Reading the diagram

Keep two quantities firmly apart, because conflating them is the single most common reading error:

• Throws are the darts a thread actually launches. With N = 750,000 over K = 3 threads, each thread throws N/K = 250,000 darts. This is the work assigned by the partition step.
• Hits are the subset of those throws that land inside the circle. Because the circle covers π/4 ≈ 78.5% of the square, about 250,000 × π/4 ≈ 196,000 of each thread's throws are hits. This is the number stored in results[tid].

The reduce step sums the hit counts, not the throw counts: 588,000 hits out of 750,000 total throws gives 4 × 588,000 / 750,000 ≈ 3.136. So the 196k figure in each worker box is the hit count, and the 250k figure is the darts thrown — both appear in the box precisely so you can see they are different numbers.

Java — private counters, joined, then reduced

import java.util.Random;

public class Solution {
  private static final int NUM_THREADS = 3;
  private static final int NUMBER_OF_TOSSES = 750_000;
  private static final int[] results = new int[NUM_THREADS];

  public static void main(String[] args) throws InterruptedException {
    Thread[] threads = new Thread[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
      final int threadId = i;
      threads[i] = new Thread(() -> {
        Random rand = new Random();
        // Split the throw budget so the remainder (N mod K) is not dropped:
        // start/end use (id * N)/K and ((id+1) * N)/K, which round-robins
        // any leftover throws across the early threads.
        int start = (threadId * NUMBER_OF_TOSSES) / NUM_THREADS;
        int end   = ((threadId + 1) * NUMBER_OF_TOSSES) / NUM_THREADS;
        int countInCircle = 0;
        for (int j = start; j < end; j++) {
          double x = rand.nextDouble() * 2 - 1; // x in [-1, 1)
          double y = rand.nextDouble() * 2 - 1; // y in [-1, 1)
          if (x * x + y * y <= 1) {             // inside the unit circle
            countInCircle++;
          }
        }
        results[threadId] = countInCircle;      // one write, no race
      });
      threads[i].start();
    }

    for (Thread t : threads) t.join();          // wait for all maps

    int totalInside = 0;                         // reduce
    for (int r : results) totalInside += r;
    double pi = (4.0 * totalInside) / NUMBER_OF_TOSSES;
    System.out.println("PI = " + pi);
  }
}

Each thread owns one slot of results and writes it exactly once after its loop, so no lock is needed even though the array is shared — the slots are disjoint and the join() calls establish a happens-before edge before the reduce reads them.

Go — goroutines, a WaitGroup, and per-goroutine counters

package main

import (
	"fmt"
	"math/rand"
	"sync"
)

const (
	numThreads = 3
	tosses     = 750_000
)

func main() {
	results := make([]int, numThreads)
	var wg sync.WaitGroup

	for id := 0; id < numThreads; id++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			r := rand.New(rand.NewSource(int64(id) + 1))
			// (id*tosses)/numThreads boundaries hand any N mod K
			// remainder to the early goroutines instead of dropping it.
			start := (id * tosses) / numThreads
			end := ((id + 1) * tosses) / numThreads
			count := 0
			for j := start; j < end; j++ {
				x := r.Float64()*2 - 1
				y := r.Float64()*2 - 1
				if x*x+y*y <= 1 {
					count++
				}
			}
			results[id] = count // disjoint slot, no mutex needed
		}(id)
	}

	wg.Wait() // wait for all maps

	totalInside := 0 // reduce
	for _, c := range results {
		totalInside += c
	}
	pi := 4.0 * float64(totalInside) / float64(tosses)
	fmt.Printf("PI = %v\n", pi)
}

The shape matches Java: a WaitGroup replaces join(), each goroutine writes one disjoint slice element, and the reduce runs only after wg.Wait().

A note on the partition arithmetic

It is tempting to simplify each thread's loop to for (j = 0; j < N/K; j++) and call it equivalent. For the per-thread iteration count that is true — each thread runs N/K iterations either way. But it is not exactly identical when N is not a multiple of K. With integer division, plain N/K per thread rounds down, so K × (N/K) can be less than N and the last N mod K throws are silently dropped. Computing start = (id × N)/K and end = ((id+1) × N)/K instead distributes that remainder — the early threads each pick up one extra throw — so the threads collectively cover all N darts. With N = 750,000 and K = 3 the remainder is zero and both forms agree, but the (id+1) × N / K form is the one to reach for so the estimate is divided by the throws you actually made.

Pitfalls

• One shared counter. If every thread increments a single shared count_in_circle, each count++ is an unsynchronized read-modify-write. Concurrent increments interleave and overwrite each other, so the count comes out too low and π is underestimated. Keep a private counter per thread and combine once in the reduce step (or use an atomic, but that reintroduces contention in the hot loop).
• Dividing by the wrong denominator. The estimate is 4 × total_hits / N, where N is the total number of throws, not the number of hits and not the number of threads. If the partition drops the N mod K remainder, the threads actually throw fewer than N darts while you still divide by N, biasing the result.
• Shared or correlated RNG. Sharing one Random across threads either serializes on its internal lock (killing the parallelism) or, if unsynchronized, corrupts its state. Give each thread its own generator. Seeding every thread identically is just as bad — the threads then explore the same point sequence, so the extra threads add no new information and the estimate does not improve. Seed each thread distinctly (for example from its id).

Source

Adapted from the Knowledge Guide lesson Problem 5 Pi calculation (Concurrency › Concurrency Problems), site/concurrency/concurrency-problems/010-problem-5-pi-calculation.html, which presents the Monte Carlo π estimator and its multithreaded partition–map–reduce solution with Java reference code.