Skip to content
Knitting

Parallel BigInt prime search

What is this about?

Section titled “What is this about?”

This example searches a seeded region of large odd integers for a probable prime. Each candidate is checked with the Miller–Rabin primality test, and the host gives each worker a long-running, disjoint scan through the region.

The result is probable, not a formal proof. More Miller–Rabin rounds make a false positive less likely, at the cost of more work per candidate.

How it works

Section titled “How it works”
  1. The host creates a deterministic odd starting point from the requested bit width.
  2. Worker i checks start + 2i, then advances by 2 * threads so scans do not overlap.
  3. Each worker keeps testing candidates until it finds a probable prime, sees an abort signal, or reaches the region limit.
  4. The first result wins; the host aborts the other calls through their shared signals.
  5. Aborted workers stop at their next signal check and the host prints a compact summary.

The default uses 1,500-bit candidates, a region of one billion odd numbers, and eight rounds. The region is intentionally much larger than a normal run needs: workers usually stop because one of them finds a prime, not because they reach the limit. The seed fixes the searched region, but the winning candidate can vary with worker scheduling because the first result cancels the rest.

Run

Section titled “Run”
bun.sh
bun src/run_prime_hunt.ts --threads 4 --bits 1500 --region 1000000000 --rounds 8

Expected output:

threads:    4
bits:       1500
region:     1,000,000,000 odd candidates
workers:    4
tested:     varies
prime:      a probable 1500-bit prime
cancelled:  yes
elapsed:    500 ms

The searched region is deterministic. The tested count, winning prime, and elapsed time depend on how quickly each worker finds a result and observes the signal, as well as your runtime, CPU, and worker count.

Why this pattern works

Section titled “Why this pattern works”
  • Each worker owns one long-running scan with a disjoint stride.
  • The host owns input generation, cancellation, and reporting.
  • Task payloads are strings and numbers, so BigInt conversion stays inside the worker.
  • Abort-aware tasks stop wasted BigInt work as soon as another worker finds a result.
  • A finite region keeps the no-hit case safe and testable.
  • The same pattern scales from a quick 64-bit demo to a much larger search.

Code

Section titled “Code”
run_prime.hunt.ts
import { createPool, isMain } from "knitting";
import {
  scanForProbablePrime,
  type ScanResult,
} from "./prime_scan.ts";


type Options = {
  threads: number;
  bits: number;
  region: number;
  rounds: number;
};


type AbortablePromise<T> = Promise<T> & {
  reject: (reason?: unknown) => void;
};


function positiveIntArg(name: string, fallback: number): number {
  const index = process.argv.indexOf(`--${name}`);
  const value = index === -1 ? undefined : Number(process.argv[index + 1]);
  return Number.isSafeInteger(value) && value > 0 ? value : fallback;
}


function readOptions(): Options {
  return {
    threads: positiveIntArg("threads", 4),
    bits: positiveIntArg("bits", 1_500),
    region: positiveIntArg("region", 1_000_000_000),
    rounds: positiveIntArg("rounds", 8),
  };
}


function xorshift32(state: number): number {
  state |= 0;
  state ^= state << 13;
  state ^= state >>> 17;
  state ^= state << 5;
  return state | 0;
}


function makeRandomOdd(bits: number, seed: number): bigint {
  let state = seed;
  let value = 0n;


  for (let offset = 0; offset < bits; offset += 32) {
    state = xorshift32(state);
    value = (value << 32n) | BigInt(state >>> 0);
  }


  const mask = (1n << BigInt(bits)) - 1n;
  return (value & mask) | (1n << BigInt(bits - 1)) | 1n;
}


function waitForFirstPrime(
  jobs: AbortablePromise<ScanResult>[],
): Promise<ScanResult | null> {
  return new Promise((resolve, reject) => {
    let remaining = jobs.length;


    for (const job of jobs) {
      job.then(
        (result) => {
          if (result.prime !== null) {
            resolve(result);
            return;
          }


          remaining--;
          if (remaining === 0) resolve(null);
        },
        reject,
      );
    }
  });
}


async function main() {
  const options = readOptions();
  const start = makeRandomOdd(options.bits, 0x6d2b_79f5);
  const workerCount = Math.min(options.threads, options.region);
  const step = 2 * options.threads;


  using pool = createPool({
    threads: options.threads,
    abortSignalCapacity: workerCount,
  })({ scanForProbablePrime });


  const started = performance.now();
  const jobs: AbortablePromise<ScanResult>[] = [];


  for (let worker = 0; worker < workerCount; worker++) {
    const count = Math.ceil((options.region - worker) / options.threads);
    const workerStart = start + 2n * BigInt(worker);


    jobs.push(
      pool.call.scanForProbablePrime([
        workerStart.toString(),
        count,
        step,
        options.rounds,
      ]),
    );
  }


  let winner: ScanResult | null;
  try {
    winner = await waitForFirstPrime(jobs);
    if (winner !== null) {
      for (const job of jobs) job.reject();
    }


    const results = await Promise.all(jobs);
    const tested = results.reduce((total, result) => total + result.tested, 0);
    const cancelled = results.some((result) => result.aborted);
    const elapsed = performance.now() - started;


    console.log(`threads:    ${options.threads}`);
    console.log(`bits:       ${options.bits}`);
    console.log(`region:     ${options.region.toLocaleString()} odd candidates`);
    console.log(`workers:    ${workerCount}`);
    console.log(`tested:     ${tested.toLocaleString()}`);
    console.log(`prime:      ${winner?.prime ?? "not found"}`);
    console.log(`cancelled:  ${cancelled ? "yes" : "no"}`);
    console.log(`elapsed:    ${elapsed.toFixed(0)} ms`);
  } catch (error) {
    for (const job of jobs) job.reject();
    await Promise.allSettled(jobs);
    throw error;
  }
}


if (isMain) {
  await main();
}

CLI knobs

Section titled “CLI knobs”
  • --bits — size of each candidate; larger numbers cost more to test.
  • --region — total number of odd candidates available to all workers.
  • --rounds — Miller–Rabin rounds; more rounds increase confidence and cost.
  • --threads — number of workers in the pool.

Things to try

Section titled “Things to try”
  1. Use --bits 64 --region 10000 for an almost instant run.
  2. Increase --rounds to 20 and compare the elapsed time.
  3. Increase --region to 10000000000 and watch workers stop long before the limit.
  4. Increase --bits to 2048 and watch BigInt arithmetic become the main cost.