2 files changed, 212 insertions, 3 deletions
diff --git a/pbt/ts/src/gen.test.ts b/pbt/ts/src/gen.test.ts
index eaba36f..75c41c8 100644
--- a/pbt/ts/src/gen.test.ts
+++ b/pbt/ts/src/gen.test.ts
@@ -1,7 +1,7 @@
 import Prando from 'prando';
-import {none} from 'fp-ts/lib/Option.js';
+import { none } from 'fp-ts/lib/Option.js';
 import * as G from './gen.js';
-import {test, expect} from 'vitest';
+import { test, expect } from 'vitest';
 
 test('can generate and shrink bytes', async () => {
   const prng = new Prando(Math.random() * 1000);
@@ -17,3 +17,155 @@ test('can generate and shrink bytes', async () => {
     expect(replayed, `Replaying at ${i}`).toEqual(bytes[i - 1]);
   }
 });
+
+test('can generate an arbitrary integer', () => {
+  const prng = new Prando(Math.random() * 1000);
+  const gen = G.genInt();
+  const value = gen.generate();
+  expect(typeof value).toBe('number');
+});
+
+test('can generate N arbitrary integers', () => {
+  const prng = new Prando(Math.random() * 1000);
+  const gen = G.genInt();
+  const value = gen.generateN(5);
+  expect(value.length).toBe(5);
+});
+
+test('can generate arbitrary integer within bounds', () => {
+  const seed = Math.random() * 1000;
+  const gen = G.genIntWithin(1000, 200000, seed);
+  for (let i = 0; i < 100; i++) {
+    const value = gen.generate();
+    expect(value).toBeGreaterThanOrEqual(1000);
+    expect(value).toBeLessThanOrEqual(200000);
+  }
+});
+
+test('generated integers are uniformly distributed', () => {
+  const seed = Math.random() * 1000;
+  const lb = 0;
+  const ub = 65536;
+  const gen = G.genIntWithin(lb, ub, seed);
+  const range = ub - lb;
+  const buckets = 128;
+  const numSamples = 100000;
+  // indexed by lower bound
+  const counts: Record<number, number> = {};
+  for (let i = 1; i <= buckets; i++) {
+    counts[Math.ceil(range / buckets) * i + lb] = 0;
+  }
+  const values = [];
+  for (let i = 0; i < numSamples; i++) {
+    const value = gen.generate();
+    values.push(value);
+    const bucket = Object.keys(counts).find((b) => value < parseInt(b));
+    if (!bucket) {
+      console.log('ignoring bucket for value', value);
+    } else {
+      const b = parseInt(bucket);
+      counts[b] = (counts[b] || 0) + 1;
+    }
+  }
+
+  // compute χ² statistic
+  const expectedCount = numSamples / buckets;
+  const chiSquared = Object.values(counts).reduce((acc, count) => {
+    const diff = count - expectedCount;
+    return acc + (diff * diff) / expectedCount;
+  });
+  // compute p-value and Cramér's V.
+  // In our case the p-value will
+  // systematically be negligible and therefore will reject the null
+  // hypothesis, eg. that the frequency distribution of numbers we
+  // generate is truly uniform. However, Cramér's V is a better
+  // measure of effect size and will be small if the distribution is
+  // uniform.
+  const cramerv = computeCramersV(chiSquared, numSamples, buckets);
+  const pValue = computeChiSquaredPValue(chiSquared, buckets);
+  console.log(`Chi-squared: ${chiSquared}, p-value: ${pValue}, Cramer V: ${cramerv}`);
+  expect(cramerv).toBeLessThan(0.01);
+});
+
+
+/**
+ * Computes the right-tailed p-value for a Chi-Squared distribution
+ * using the Wilson-Hilferty approximation.
+ *
+ * @param chiSquareValue The calculated empirical chi-square statistic (e.g., 1190.372)
+ * @param numBuckets The total number of bins/categories in your test (e.g., 100)
+ * @returns The p-value between 0.0 and 1.0
+ */
+function computeChiSquaredPValue(chiSquareValue: number, numBuckets: number): number {
+  // Degrees of Freedom = Number of buckets - 1
+  const df = numBuckets - 1;
+
+  if (df <= 0) {
+    throw new Error("Number of buckets must be greater than 1.");
+  }
+  if (chiSquareValue < 0) {
+    return 1.0;
+  }
+
+  // 1. Compute the Wilson-Hilferty Normal Approximation Z-score
+  const term1 = Math.pow(chiSquareValue / df, 1 / 3);
+  const term2 = 1 - 2 / (9 * df);
+  const denominator = Math.sqrt(2 / (9 * df));
+
+  const zScore = (term1 - term2) / denominator;
+
+  // 2. Compute right-tailed probability from Z-score using standard Normal CDF
+  return standardNormalRightTail(zScore);
+}
+
+/**
+ * Standard Normal Right-Tail Probability Q(z) = P(Z > z)
+ * Uses a highly precise numerical approximation for the error function (erf).
+ */
+function standardNormalRightTail(z: number): number {
+  // Standard Normal Cumulative Distribution Function (CDF)
+  const cdf = 0.5 * (1 + errorFunction(z / Math.sqrt(2)));
+  // Right tail is 1 - CDF
+  return 1 - cdf;
+}
+
+/**
+ * Abramowitz and Stegun approximation for the Error Function (erf),
+ * accurate to 1.5 x 10^-7
+ *
+ * See https://en.wikipedia.org/wiki/Error_function#Bounds_and_numerical_approximations
+ */
+function errorFunction(x: number): number {
+  const sign = x < 0 ? -1 : 1;
+  const absX = Math.abs(x);
+
+  // Constants for the numerical approximation
+  const p = 0.3275911;
+  const a1 = 0.254829592;
+  const a2 = -0.284496736;
+  const a3 = 1.421413741;
+  const a4 = -1.453152027;
+  const a5 = 1.061405429;
+
+  const t = 1.0 / (1.0 + p * absX);
+  const y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * Math.exp(-absX * absX);
+
+  return sign * y;
+}
+
+/**
+ * Calculates Cramér's V to determine the practical effect size (strength of bias).
+ * See https://en.wikipedia.org/wiki/Cramér%27s_V
+ *
+ * @param chiSquare The empirical chi-square value (e.g., 1190.372)
+ * @param totalSamples The total number of data points (e.g., 100000)
+ * @param numBuckets The total number of bins/buckets (e.g., 100)
+ * @returns A value between 0.0 (no bias) and 1.0 (extreme bias)
+ */
+function computeCramersV(chiSquare: number, totalSamples: number, numBuckets: number): number {
+  const df = numBuckets - 1;
+  if (df <= 0 || totalSamples <= 0) return 0;
+
+  // Core Formula: sqrt( chi2 / (N * df) )
+  return Math.sqrt(chiSquare / (totalSamples * df));
+}
diff --git a/pbt/ts/src/gen.ts b/pbt/ts/src/gen.ts
index 531a118..c27cfec 100644
--- a/pbt/ts/src/gen.ts
+++ b/pbt/ts/src/gen.ts
@@ -1,4 +1,4 @@
-import {Option, none, some} from 'fp-ts/lib/Option.js';
+import { Option, none, some } from 'fp-ts/lib/Option.js';
 import Prando from 'prando';
 
 // a shrinkable generator needs to maintain some state,
@@ -71,3 +71,60 @@ export class ReplayBytes implements GenBytes {
     return chunk;
   }
 }
+
+class GenInt implements Gen<number> {
+  private bytes: BytesGen;
+
+  constructor(seed: number | undefined = undefined) {
+    this.bytes = new BytesGen(new Prando(seed ? seed : Math.random() * 1000));
+  }
+
+  generate(): number {
+    const bytes = this.bytes.generate(1);
+    return bytes[0];
+  }
+
+  generateN(n: number): number[] {
+    const result = [];
+    for (let i = 0; i < n; i++) {
+      result.push(this.bytes.generate(1)[0]);
+    }
+
+    return result;
+  }
+}
+
+class GenIntWithin implements Gen<number> {
+  private bytes: BytesGen;
+
+  constructor(private min: number, private max: number, seed: number | undefined = undefined) {
+    this.bytes = new BytesGen(new Prando(seed ? seed : Math.random() * 1000000000));
+    this.min = min;
+    this.max = max;
+  }
+
+  generate(): number {
+    const range = this.max - this.min;
+    const numBytes = Math.ceil(Math.log2(range) / 8);
+    const bytes = this.bytes.generate(numBytes);
+    let value = 0;
+    for (let i = 0; i < bytes.length; i++) {
+      value = (value << 8) | bytes[i];
+    }
+    return this.min + (value % range);
+  }
+
+  generateN(n: number): number[] {
+    const result = [];
+    for (let i = 0; i < n; i++) {
+      result.push(this.bytes.generate(1)[0]);
+    }
+
+    return result;
+  }
+
+}
+
+export const genInt = (seed : number | undefined = undefined) => new GenInt(seed);
+
+export const genIntWithin = (min: number, max: number, seed : number | undefined = undefined) => new GenIntWithin(min, max, seed);