tree-depth-proba-large.js

// Update of tree-depth-proba.js 
// Supposed to allow to deal with higher values of depth (approximations are done)

// success(depth: number, q: Frac)
//
// Compute the probability to generate at least one tree with depth superior to `depth`
// Given we tried 1 times with a probality of having a node of q
//
// with:
//   type Tree<T> = Node<T> | Leaf<T>
//   type Node<T> = { left: Tree<T>, right: Tree<T> }
//   type Leaf<T> = T

const factorialCache = {};
const factorial = n => {
	if (n === 0n) return 1n;
	if (factorialCache[n]) return factorialCache[n];
	const v = n * factorial(n - 1n);
	factorialCache[n] = v;
	return v;
};

const binom = (n, k) => factorial(n) / (factorial(k) * factorial(n - k));

const pCache = {};
const p = (n, m, q) => {
	if (n === 0n) return new Frac(1n, 1n);
	const key = `${n},${m},${q.num}/${q.denum}`;
	if (pCache[key]) return pCache[key];

	let v = new Frac(0n, 1n);
	for (let i = 1n ; i <= m ; ++i) {
		v = Frac.add(
				v,
				Frac.mul(
					new Frac(binom(BigInt(m), BigInt(i)), 1n),
					Frac.mul(
						new Frac(q.num ** i, q.denum ** i),
						Frac.mul(
							new Frac((q.denum - q.num) ** (m - i), q.denum ** (m - i)),
							p(n - 1n, i * 2n, q),
						),
					),
				),
			);
	}
	pCache[key] = v;
	return v;
}

function pgcd(a, b) {
	return (b === 0n) ? a : pgcd(b, a % b);
}

function Frac(num, denum) {
	this.num = num;
	this.denum = denum;
  
	this.simpl = function() {
		const g = pgcd(this.num, this.denum);
		this.num = this.num / g;
		this.denum = this.denum / g;
    
    const MaxDigits = 20;
    if (String(this.denum).length <= MaxDigits) return;
        
    // approximations
    const numToRemove = String(this.denum).length - MaxDigits;
    const divideBy = 10n ** BigInt(numToRemove);
    this.num = this.num / divideBy;
		this.denum = this.denum / divideBy;
	}
}

Frac.add = function(f, otherFrac) {
	const ff = new Frac(f.num * otherFrac.denum + otherFrac.num * f.denum, f.denum * otherFrac.denum);
	ff.simpl();
	return ff;
}

Frac.mul = function(f, otherFrac) {
	const ff = new Frac(f.num * otherFrac.num, f.denum * otherFrac.denum);
	ff.simpl();
	return ff;
}

const success = (depth, q) => {
	const factor = 100000n;
	const pOne = p(BigInt(depth), 1n, q);
	return Number((pOne.num * 100n * factor) / pOne.denum) / Number(factor);
}

// Example:
// success(5, new Frac(1n, 3n))