Function bigintDigitSum

src/compute-engine/library/number-theory.ts:96–121

* Sum of the digits of `|m|` in the given base, in a single O(digits) pass * (via native `toString(base)` for base 2..36, else a `checkDeadline`- * guarded mod/divide loop for larger bases) — see `bigintDigitsLSB` for the * same base-36 cutoff rationale. Avoids materializing an intermediate digit

(
  m: bigint,
  base: bigint,
  deadline: number | undefined
)

 * For base 2..36 this delegates to bigint's native `toString(base)` — a
 * linear-time, digit-by-digit reinterpretation of the binary representation
 * — instead of the naive repeated-mod-and-divide loop, which is O(digits²):
 * quadratic enough to turn a several-hundred-thousand-digit input into a
 * many-second hang (WP-2.18). For base > 36 (not supported by `toString`),
 * falls back to the mod/divide loop, guarded by `checkDeadline`.
 */
function bigintDigitsLSB(
  m: bigint,
  base: bigint,
  deadline: number | undefined
): bigint[] {
  if (m === 0n) return [0n];
  if (base <= 36n) {
    const s = m.toString(Number(base));
    const digits = new Array<bigint>(s.length);
    for (let i = 0; i < s.length; i++) {
      if ((i & 0xffff) === 0) checkDeadline(deadline);
      digits[s.length - 1 - i] = charToDigit(s.charCodeAt(i));
    }
    return digits;
  }
  const digits: bigint[] = [];
  let x = m;
  // Unlike the base<=36 loop above, each step here is a bigint mod/div
  // against an arbitrary (possibly itself huge) `base` — its cost is not a
  // fixed small constant, so check the deadline every iteration rather than
  // amortizing over a stride.
  while (x > 0n) {
    checkDeadline(deadline);
    digits.push(x % base);