diff options
Diffstat (limited to 'src/commands/factor.js')
| -rw-r--r-- | src/commands/factor.js | 660 |
1 files changed, 660 insertions, 0 deletions
diff --git a/src/commands/factor.js b/src/commands/factor.js new file mode 100644 index 0000000..db0110f --- /dev/null +++ b/src/commands/factor.js @@ -0,0 +1,660 @@ +#!/usr/bin/env bun + +import { fstatSync, readSync } from "node:fs"; +import { cpus } from "node:os"; +import { decodeSurrogateEscapedBytes, isWriteError, localeQuotedDiagnostic, lsEscapedName, parseOptions, readAll, systemErrorMessage } from "../shared/common.js"; +import { fail, stderr, stdout } from "../shared/diagnostics.js"; +import { defineCommand, runAsMain } from "../shared/command.js"; + +export const FACTOR_LONG_OPTIONS = ["exponents", "help", "version"]; + +export function factorMetaOption(args) { + for (const arg of args) { + if (arg === "--") return null; + if (!arg.startsWith("-") || arg === "-") continue; + if (arg.startsWith("--")) { + const option = normalizeFactorLongOption(arg); + const name = option.slice(2).split("=", 1)[0]; + if (!FACTOR_LONG_OPTIONS.includes(name) || option.includes("=")) return null; + if (option === "--help" || option === "--version") return option; + continue; + } + for (let j = 1; j < arg.length; j++) if (arg[j] !== "h") return null; + } + return null; +} + +export function factorize(value) { + let n = BigInt(value); + if (n < 0n) n = -n; + if (n <= 1n) return []; + const factors = []; + for (const d of [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n]) { + while (n % d === 0n) { + factors.push(d); + n /= d; + } + } + if (n > 1n) factorBigInt(n, factors); + return factors.sort((a, b) => a < b ? -1 : a > b ? 1 : 0); +} + +export function factorBigInt(n, factors) { + if (n === 1n) return; + if (isProbablePrime(n)) { + factors.push(n); + return; + } + const nearDouble = factorNearDoubleSemiprime(n); + if (nearDouble != null) { + factorBigInt(nearDouble, factors); + factorBigInt(n / nearDouble, factors); + return; + } + // A high-bound p-1 pass is useful for very large residuals with smooth + // predecessor factors, but it is disproportionately expensive across a + // contiguous range of 96-bit values. Pollard rho is the better first + // strategy below this threshold. + const pMinusOne = n >= 1_000_000_000_000_000_000_000_000_000_000n + ? pollardPMinusOne(n, 500_000) + : n >= (1n << 72n) + ? pollardPMinusOne(n, 100_000) + : null; + if (pMinusOne != null) { + factorBigInt(pMinusOne, factors); + factorBigInt(n / pMinusOne, factors); + return; + } + const divisor = pollardRho(n); + factorBigInt(divisor, factors); + factorBigInt(n / divisor, factors); +} + +export function bigintGcd(a, b) { + while (b !== 0n) { + const t = a % b; + a = b; + b = t; + } + return a < 0n ? -a : a; +} + +export function modPow(base, exponent, mod) { + let result = 1n; + base %= mod; + while (exponent > 0n) { + if (exponent & 1n) result = (result * base) % mod; + base = (base * base) % mod; + exponent >>= 1n; + } + return result; +} + +export function factorNearDoubleSemiprime(n) { + if (n < 1_000_000_000_000_000_000n) return null; + for (let delta = -4096n; delta <= 4096n; delta++) { + const discriminant = delta * delta + 8n * n; + const root = bigintSqrt(discriminant); + if (root * root !== discriminant) continue; + const numerator = root - delta; + if (numerator % 4n !== 0n) continue; + const factor = numerator / 4n; + if (factor > 1n && factor < n && n % factor === 0n) return factor; + } + return null; +} + +export function pollardPMinusOne(n, bound) { + let a = 2n; + let sinceGcd = 0; + for (const p of primesUpTo(bound)) { + let power = p; + while (power <= Math.floor(bound / p)) power *= p; + a = modPow(a, BigInt(power), n); + if (++sinceGcd < 256) continue; + sinceGcd = 0; + const d = bigintGcd(a - 1n, n); + if (d > 1n && d < n) return d; + if (d === n) return null; + } + const d = bigintGcd(a - 1n, n); + return d > 1n && d < n ? d : null; +} + +export function bigintSqrt(n) { + if (n < 2n) return n; + let x = 1n << BigInt(Math.ceil(n.toString(2).length / 2)); + for (;;) { + const y = (x + n / x) >> 1n; + if (y >= x) return x; + x = y; + } +} + +export function isProbablePrime(n) { + if (n < 2n) return false; + for (const p of [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n]) { + if (n === p) return true; + if (n % p === 0n) return false; + } + let d = n - 1n; + let s = 0n; + while ((d & 1n) === 0n) { + d >>= 1n; + s++; + } + const bases = n < (1n << 128n) ? [2n, 3n, 5n, 7n, 11n, 13n, 17n] : [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n]; + for (const a of bases) { + if (a >= n - 2n) continue; + let x = modPow(a, d, n); + if (x === 1n || x === n - 1n) continue; + let composite = true; + for (let r = 1n; r < s; r++) { + x = (x * x) % n; + if (x === n - 1n) { + composite = false; + break; + } + } + if (composite) return false; + } + return true; +} + +export function pollardRho(n) { + if (n % 2n === 0n) return 2n; + const preferredConstants = [13n, 3n, 1n, 22n, 11n, 4n, 15n, 5n, 7n, 2n, 17n, 19n, 26n]; + for (let attempt = 0; ; attempt++) { + const c = attempt < preferredConstants.length ? preferredConstants[attempt] : BigInt(attempt + 1); + let y = 2n; + let d = 1n; + let r = 1; + let q = 1n; + let x = 0n; + let ys = 0n; + const f = (v) => (v * v + c) % n; + while (d === 1n) { + x = y; + for (let i = 0; i < r; i++) y = f(y); + let k = 0; + while (k < r && d === 1n) { + ys = y; + const limit = Math.min(256, r - k); + for (let i = 0; i < limit; i++) { + y = f(y); + const diff = x > y ? x - y : y - x; + q = (q * diff) % n; + } + d = bigintGcd(q, n); + k += 256; + } + r *= 2; + if (r > 2_000_000 && d === 1n) break; + } + if (d === n) { + do { + ys = f(ys); + d = bigintGcd(x > ys ? x - ys : ys - x, n); + } while (d === 1n); + } + if (d > 1n && d < n) return d; + if (attempt === preferredConstants.length - 1 && n > 1_000_000_000_000_000_000_000_000n) { + const pPlusOne = pollardPPlusOne(n, 11_000_000, 6n); + if (pPlusOne != null) return pPlusOne; + } + } +} + +export function pollardPPlusOne(n, bound, parameter) { + let v = parameter; + for (const p of primesUpTo(bound)) { + let power = p; + while (power <= Math.floor(bound / p)) power *= p; + v = lucasV(v, BigInt(power), n); + } + const d = bigintGcd(v - 2n, n); + return d > 1n && d < n ? d : null; +} + +export function lucasV(parameter, exponent, mod) { + let vk = 2n % mod; + let vk1 = parameter % mod; + for (const bit of exponent.toString(2)) { + const v2k = positiveMod(vk * vk - 2n, mod); + const v2k1 = positiveMod(vk * vk1 - parameter, mod); + if (bit === "0") { + vk = v2k; + vk1 = v2k1; + } else { + vk = v2k1; + vk1 = positiveMod(vk1 * vk1 - 2n, mod); + } + } + return vk; +} + +export function positiveMod(value, mod) { + value %= mod; + return value < 0n ? value + mod : value; +} + +export async function factor(args) { + args = normalizeFactorLongOptions(args); + const { opts, operands } = parseOptions(args, { short: { h: false }, long: { exponents: false, help: false, version: false } }); + opts.exponents = opts.h || opts.exponents; + if (!operands.length && !fstatSync(0).isFile()) return streamFactorStdin(opts); + let values; + try { + if (operands.length) values = operands.map((operand) => String(operand).replace(/\0\S*/g, "")); + else { + const input = decodeSurrogateEscapedBytes(await readAll("-")); + const fastStatus = factorFastSmallIntegerInput(input, opts); + if (fastStatus != null) return fastStatus; + values = input.replace(/\0\S*/g, "").trim().split(/\s+/).filter(Boolean); + } + } catch (error) { + return fail("factor", `error reading input: ${systemErrorMessage(error)}`); + } + const parallel = await factorLargeContiguousRangeInParallel(values, opts); + if (parallel != null) return parallel; + const batchFactors = prepareSmallIntegerFactorizer(values) ?? prepareContiguousRangeFactorizer(values); + let status = 0; + for (const raw of values) { + status = factorOneValue(raw, opts, batchFactors) || status; + } + return status; +} + +export async function streamFactorStdin(opts) { + let pending = []; + let pendingLength = 0; + let values = []; + let status = 0; + const flushValues = async () => { + if (!values.length) return; + const batch = values; + values = []; + const parallelStatus = await factorLargeContiguousRangeInParallel(batch, opts); + if (parallelStatus != null) { + status = parallelStatus || status; + return; + } + // Dense small ranges (notably upstream factor/t00: 0..10,000,000) + // must use the compact Uint32 sieve. The generic range factorizer keeps + // one JS array per value and caused JSC heap growth into multiple GiB. + const batchFactors = prepareSegmentedSmallIntegerFactorizer(batch) + ?? prepareSmallIntegerFactorizer(batch) + ?? prepareContiguousRangeFactorizer(batch); + for (const raw of batch) status = factorOneValue(raw, opts, batchFactors) || status; + }; + const flushToken = () => { + if (!pendingLength) return; + const raw = decodeSurrogateEscapedBytes(Buffer.concat(pending, pendingLength)).replace(/\0\S*/g, ""); + pending = []; + pendingLength = 0; + if (raw) values.push(raw); + }; + try { + const inputBuffer = Buffer.allocUnsafe(64 * 1024); + while (true) { + const bytesRead = readSync(0, inputBuffer, 0, inputBuffer.length, null); + if (bytesRead === 0) break; + const chunk = inputBuffer.subarray(0, bytesRead); + let start = 0; + for (let index = 0; index < chunk.length; index++) { + if (![9, 10, 11, 12, 13, 32].includes(chunk[index])) continue; + if (index > start) { + const part = Buffer.from(chunk.subarray(start, index)); + pending.push(part); + pendingLength += part.length; + } + flushToken(); + start = index + 1; + } + if (start < chunk.length) { + const part = Buffer.from(chunk.subarray(start)); + pending.push(part); + pendingLength += part.length; + } + // Process four 100k-value child chunks concurrently while applying + // backpressure to stdin, keeping the range optimization bounded. + if (values.length >= 400_000) await flushValues(); + } + flushToken(); + await flushValues(); + return status; + } catch (error) { + if (isWriteError(error)) throw error; + return fail("factor", `error reading input: ${systemErrorMessage(error)}`); + } +} + +export function factorOneValue(raw, opts, batchFactors = null) { + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value)) { + stderr(`factor: ${localeQuotedDiagnostic(factorDiagnosticValue(raw))} is not a valid positive integer\n`); + return 1; + } + const normalizedValue = normalizeFactorValue(value); + const factors = batchFactors?.get(normalizedValue) ?? factorize(normalizedValue); + stdout(`${normalizedValue}:${formatFactors(factors, opts).map((n) => ` ${n}`).join("")}\n`); + return 0; +} + +export const FACTOR_FAST_OUTPUT_CHUNK_BYTES = 4096; + +export function factorFastSmallIntegerInput(input, opts) { + if (opts.exponents || input.includes("\0")) return null; + let count = 0; + let max = 0; + for (const token of input.matchAll(/\S+/g)) { + const raw = token[0]; + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value) || value.length > 8) return null; + const n = Number(value); + if (!Number.isSafeInteger(n)) return null; + if (n > max) max = n; + count++; + } + if (count < 10000 || max > 100_000_000) return null; + + const spf = smallestPrimeFactors(max); + let out = ""; + for (const token of input.matchAll(/\S+/g)) { + const n = Number(token[0].replace(/^\+/, "")); + const line = `${n}:${formatSmallIntegerFactors(n, spf)}\n`; + if (out && out.length + line.length > FACTOR_FAST_OUTPUT_CHUNK_BYTES) { + stdout(out); + out = ""; + } + out += line; + } + if (out) stdout(out); + return 0; +} + +export function formatSmallIntegerFactors(value, spf) { + if (value <= 1) return ""; + let n = value; + let out = ""; + while (n > 1) { + const p = spf[n] || n; + out += ` ${p}`; + n = Math.trunc(n / p); + } + return out; +} + +export function factorDiagnosticValue(value) { + return [...String(value)].map((ch) => { + if (/[\udc80-\udcff]/.test(ch)) return `\\${(ch.charCodeAt(0) - 0xdc00).toString(8).padStart(3, "0")}`; + return lsEscapedName(ch, { escapeDouble: false }); + }).join(""); +} + +export function normalizeFactorValue(value) { + return BigInt(value).toString(); +} + +export function normalizeFactorLongOptions(args) { + const out = []; + let end = false; + for (const arg of args) { + if (end || arg === "--" || !arg.startsWith("--")) { + out.push(arg); + if (arg === "--") end = true; + continue; + } + out.push(normalizeFactorLongOption(arg)); + } + return out; +} + +export function normalizeFactorLongOption(arg) { + const body = arg.slice(2); + const eq = body.indexOf("="); + const name = eq === -1 ? body : body.slice(0, eq); + if (!name) return arg; + const match = FACTOR_LONG_OPTIONS.find((option) => option.startsWith(name)); + if (!match) return arg; + return eq === -1 ? `--${match}` : `--${match}=${body.slice(eq + 1)}`; +} + +export async function factorLargeContiguousRangeInParallel(values, opts) { + if (process.env.BNU_FACTOR_CHILD === "1" || values.length < 2000 || opts.exponents) return null; + const normalized = []; + for (const raw of values) { + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value)) return null; + normalized.push(value); + } + const lo = BigInt(normalized[0]); + const hi = BigInt(normalized[normalized.length - 1]); + if (lo < 1_000_000_000_000_000_000n || hi < lo || hi - lo !== BigInt(normalized.length - 1)) return null; + for (let i = 1; i < normalized.length; i++) { + if (BigInt(normalized[i]) !== lo + BigInt(i)) return null; + } + + // Each Bun worker carries a substantial runtime and JIT footprint. Keep + // the default single-process so an ordinary invocation cannot multiply its + // memory use by the host CPU count. Controlled benchmarks and audits may + // opt in to bounded parallelism with BNU_FACTOR_WORKERS. + const configuredWorkerLimit = /^\d+$/.test(process.env.BNU_FACTOR_WORKERS ?? "") + ? Number(process.env.BNU_FACTOR_WORKERS) + : null; + const workerLimit = configuredWorkerLimit ?? 1; + const workers = Math.min(workerLimit, Math.max(1, Math.floor(values.length / 100)), cpus().length || 1); + if (workers < 2) return null; + const chunkSize = Math.ceil(values.length / workers); + const chunks = []; + for (let i = 0; i < values.length; i += chunkSize) chunks.push(values.slice(i, i + chunkSize)); + const results = await Promise.all(chunks.map(async (chunk) => { + const proc = Bun.spawn([process.execPath, import.meta.path, "factor"], { + env: { ...process.env, BNU_FACTOR_CHILD: "1" }, + stdin: new Blob([chunk.join("\n") + "\n"]), + stdout: "pipe", + stderr: "pipe", + }); + const [code, out, err] = await Promise.all([ + proc.exited, + new Response(proc.stdout).text(), + new Response(proc.stderr).text(), + ]); + return { code, out, err }; + })); + let status = 0; + for (const result of results) { + if (result.out) stdout(result.out); + if (result.err) stderr(result.err); + if (result.code !== 0) status = result.code; + } + return status; +} + +export function prepareContiguousRangeFactorizer(values) { + if (values.length < 100 || values.length > 1_000_000) return null; + const normalized = []; + for (const raw of values) { + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value)) return null; + normalized.push(value); + } + const lo = BigInt(normalized[0]); + const hi = BigInt(normalized[normalized.length - 1]); + if (hi < lo || hi - lo !== BigInt(normalized.length - 1)) return null; + for (let i = 1; i < normalized.length; i++) { + if (BigInt(normalized[i]) !== lo + BigInt(i)) return null; + } + + const residues = normalized.map(BigInt); + const factors = Array.from({ length: normalized.length }, () => []); + for (const p of primesUpTo(1_000_000)) { + const bigP = BigInt(p); + const rem = lo % bigP; + let index = Number(rem === 0n ? 0n : bigP - rem); + for (; index < residues.length; index += p) { + while (residues[index] % bigP === 0n) { + factors[index].push(bigP); + residues[index] /= bigP; + } + } + } + + return { + get(value) { + const index = Number(BigInt(value) - lo); + if (index < 0 || index >= residues.length) return null; + const out = [...factors[index]]; + if (residues[index] > 1n) out.push(...factorize(residues[index])); + return out.sort((a, b) => a < b ? -1 : a > b ? 1 : 0); + }, + }; +} + +export const primeCache = new Map(); + +export function primesUpTo(max) { + const cached = primeCache.get(max); + if (cached) return cached; + const composite = new Uint8Array(max + 1); + const primes = []; + for (let i = 2; i <= max; i++) { + if (composite[i]) continue; + primes.push(i); + if (i > Math.floor(max / i)) continue; + for (let j = i * i; j <= max; j += i) composite[j] = 1; + } + primeCache.set(max, primes); + return primes; +} + +export function prepareSmallIntegerFactorizer(values) { + if (values.length < 10000) return null; + let max = 0; + for (const raw of values) { + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value) || value.length > 8) return null; + const n = Number(value); + if (!Number.isSafeInteger(n)) return null; + if (n > max) max = n; + } + if (max > 100_000_000) return null; + const spf = smallestPrimeFactors(max); + return { + get(value) { + let n = Number(value); + if (n <= 1) return []; + const factors = []; + while (n > 1) { + const p = spf[n] || n; + factors.push(BigInt(p)); + n = Math.trunc(n / p); + } + return factors; + }, + }; +} + +export function prepareSegmentedSmallIntegerFactorizer(values) { + if (values.length < 10_000) return null; + const normalized = []; + for (const raw of values) { + const value = raw.replace(/^\+/, ""); + if (!/^\d+$/.test(value) || value.length > 8) return null; + const n = Number(value); + if (!Number.isSafeInteger(n) || n > 100_000_000) return null; + normalized.push(n); + } + const lo = normalized[0]; + const hi = normalized.at(-1); + if (hi - lo !== normalized.length - 1) return null; + for (let index = 1; index < normalized.length; index++) { + if (normalized[index] !== lo + index) return null; + } + + // Keep a compact CSR-style table of every factor in this segment. Storing + // only the first divisor forced each residual through the generic Pollard + // path and made the 80m..90m upstream range take more than 15 minutes. + // Two sieve passes cost little and keep a 400k-value batch to a few typed + // arrays rather than one JS array per integer. + const primes = primesUpTo(Math.floor(Math.sqrt(hi))); + const residues = new Uint32Array(normalized); + const counts = new Uint8Array(normalized.length); + for (const p of primes) { + let first = Math.ceil(lo / p) * p; + if (first < p * p) first = p * p; + for (let value = first; value <= hi; value += p) { + const index = value - lo; + while (residues[index] > 1 && residues[index] % p === 0) { + residues[index] = Math.trunc(residues[index] / p); + counts[index]++; + } + } + } + for (let index = 0; index < residues.length; index++) { + if (residues[index] > 1) counts[index]++; + } + const offsets = new Uint32Array(normalized.length + 1); + for (let index = 0; index < counts.length; index++) offsets[index + 1] = offsets[index] + counts[index]; + const factors = new Uint32Array(offsets.at(-1)); + const positions = new Uint32Array(offsets.subarray(0, normalized.length)); + residues.set(normalized); + for (const p of primes) { + let first = Math.ceil(lo / p) * p; + if (first < p * p) first = p * p; + for (let value = first; value <= hi; value += p) { + const index = value - lo; + while (residues[index] > 1 && residues[index] % p === 0) { + residues[index] = Math.trunc(residues[index] / p); + factors[positions[index]++] = p; + } + } + } + for (let index = 0; index < residues.length; index++) { + if (residues[index] > 1) factors[positions[index]++] = residues[index]; + } + return { + get(value) { + const original = Number(value); + const index = original - lo; + if (index < 0 || index >= normalized.length || original <= 1) return original <= 1 ? [] : null; + const out = []; + for (let position = offsets[index]; position < offsets[index + 1]; position++) out.push(BigInt(factors[position])); + return out; + }, + }; +} + +export let smallestPrimeFactorCache = new Uint32Array(0); + +export function smallestPrimeFactors(max) { + if (smallestPrimeFactorCache.length > max) return smallestPrimeFactorCache; + const spf = new Uint32Array(max + 1); + for (let i = 2; i <= max; i++) { + if (spf[i] !== 0) continue; + spf[i] = i; + if (i > Math.floor(max / i)) continue; + for (let j = i * i; j <= max; j += i) { + if (spf[j] === 0) spf[j] = i; + } + } + smallestPrimeFactorCache = spf; + return spf; +} + +export function formatFactors(factors, opts) { + if (!opts.exponents) return factors.map(String); + const out = []; + for (let i = 0; i < factors.length;) { + let count = 1; + while (factors[i + count] === factors[i]) count++; + out.push(count === 1 ? String(factors[i]) : `${factors[i]}^${count}`); + i += count; + } + return out; +} + +const singleCall = defineCommand("factor", factor, factorMetaOption); +export default singleCall; + +if (import.meta.main) await runAsMain(singleCall); |
