Demo: computing a large factorial with JS BigInts, and converting the result to string

factorial_and_tostring.js

// A dead simple factorial function, for correctness checking.
function SimpleFactorial(n) {
  n = BigInt(n);
  let result = 1n;
  for (let i = 2n; i <= n; i++) result *= i;
  return result;
}

// An optimized factorial function, based on the following ideas:
// - Instead of repeatedly multiplying a giant intermediate result with
//   a tiny next factor, multiply "neighboring" factors (1*2, 3*4, 5*6, ...),
//   then multiply neighboring chunks in a next round, and so on. This means
//   that values of similar size will be multiplied, which allows engines to
//   use Karatsuba and other advanced multiplication algorithms.
// - As a further tuning, don't start with individual factors (which would
//   introduce significant skew to the tree structure, as 1*2 is a lot smaller
//   than (n-1)*n); instead start by multiplying small ranges of initial factors
//   into chunks of roughly similar size.
// - For the time being, Number operations are much faster in JavaScript
//   engines than BigInt operations, so choose the initial chunk size such that
//   these chunks can be computed using Numbers, and only switch to BigInts
//   for the subsequent rounds that combine chunks.
function Factorial(n) {
  let chunks = [];
  let chunk = 1;
  for (let i = 2; i <= n; i++) {
    let candidate = chunk * i;
    if (candidate <= Number.MAX_SAFE_INTEGER) {
      chunk = candidate;
    } else {
      chunks.push(BigInt(chunk));
      chunk = i;
    }
  }
  chunks.push(BigInt(chunk));

  while (chunks.length > 1) {
    // Note the `-1` in the end condition: in case of an odd number of chunks,
    // the last chunk is simply left alone.
    for (let i = 0; i < chunks.length - 1; i++) {
      // For convenience, we don't multiply neighboring chunks, but pop off
      // the last chunk. The former middle of the array will be the new end.
      chunks[i] *= chunks.pop();
    }
  }

  return chunks[0];
}

// Same as the above with an additional optimization: shifting away powers of 2
// in the original list of factors, and adding them all back in with a single
// left-shift at the end. Gives about 3% improvement.
function Factorial2(n) {
  let chunks = [];
  let chunk = 1;
  let twos = 0;
  for (let i = 2; i <= n; i++) {
    let factor = i;
    while ((factor & 1) === 0) {
      twos++;
      factor >>= 1;
    }
    let candidate = chunk * factor;
    if (candidate <= Number.MAX_SAFE_INTEGER) {
      chunk = candidate;
    } else {
      chunks.push(BigInt(chunk));
      chunk = factor;
    }
  }
  chunks.push(BigInt(chunk));

  while (chunks.length > 1) {
    for (let i = 0; i < chunks.length - 1; i++) {
      chunks[i] *= chunks.pop();
    }
  }
  return chunks[0] << BigInt(twos);
}

// Same as above, but instead of testing for powers of 2, adjust the loops so
// that only the required odd factors are generated. Turns out to be about
// 1% slower than {Factorial2}.
function Factorial3(n) {
  let chunks = []
  let chunk = 1;
  for (let i = n; i >= 3; i >>= 1) {
    for (let j = 3; j <= i; j += 2) {
      let candidate = chunk * j;
      if (candidate <= Number.MAX_SAFE_INTEGER) {
        chunk = candidate;
      } else {
        chunks.push(BigInt(chunk));
        chunk = j;
      }
    }
  }
  chunks.push(BigInt(chunk));

  while (chunks.length > 1) {
    for (let i = 0; i < chunks.length - 1; i++) {
      chunks[i] *= chunks.pop();
    }
  }
  return chunks[0] << BigInt(PowersOfTwoInFactorial(n));
}

function PowersOfTwoInFactorial(n) {
  let test = 1;
  let result = 0;
  while (test <= n) {
    if ((n & test) === test) {
      result += test - 1;
    }
    test <<= 1;
  }
  return result;
}

// Correctness test: make sure that `SimpleFactorial` and `Factorial` compute
// identical results.
for (let i = 0; i < 1000; i++) {
  let simple = SimpleFactorial(i);
  let faster = Factorial(i);
  if (simple !== faster) {
    console.log(`(fast1) Error at ${i}: ${simple} vs. ${faster}`);
  }
  faster = Factorial2(i);
  if (simple !== faster) {
    console.log(`(fast2) Error at ${i}: ${simple} vs. ${faster}`);
  }
  faster = Factorial3(i);
  if (simple !== faster) {
    console.log(`(fast3) Error at ${i}: ${simple} vs. ${faster}`);
  }
}
//quit();

// Timing test. Depending on hardware, `SimpleFactorial` would take ~5 minutes,
// `Factorial` takes ~0.5 seconds.
console.time("Factorial (v1)");
let big = Factorial(1_000_000);
console.timeEnd("Factorial (v1)");

console.time("Factorial (v2)");
Factorial(1_000_000);
console.timeEnd("Factorial (v2)");

console.time("Factorial (v3)");
Factorial(1_000_000);
console.timeEnd("Factorial (v3)");

console.time("toString");
let str = big.toString();
console.timeEnd("toString");

console.log(`String length: ${str.length} characters.`);