Crossover Lab asks when a fully counted integer multiplication construction can beat a specified reference. It follows source code, constants, recursion, precision and implementation costs. The graphs show conditional mathematical bounds on input size, not CPU benchmarks or measured first crossovers.
This guide describes the 25 October 2026 audited snapshot, at the 222-entry numerical checkpoint. It is not a live leaderboard. The audit contains 595 historical candidate and variant source entries. The original request concerned 577 entries that lacked cost analysis. Source discovery reached all 577; completing discovery did not resolve every mathematical cost obligation.
222Entries with numerical bounds
At least one conditional lower or sufficient upper. The graph has 195 uppers, 62 lowers and 35 entries with both.
196Completed source-scope outcomes
Supporting audits, restricted components or other contributions without a separately supplied whole multiplier to price here.
177Open cost obligations
Source evidence exists, but a needed selection, native, physical, invoice or whole-cost argument remains unresolved.
222 + 196 + 177 = 595. These are source-entry outcomes, not a claim of 595 independent algorithms or 595 valid exponent records. The original 577 missing analyses are not all solved.
Read the graphs
What are the two charts comparing?
The time chart places each source at its GitHub merge date. The 595 source rows are a history of merged candidates and costed variants, not a list of 595 validated records. Its bounds were derived retrospectively: the date does not mean those cost constants were known then, or that a merge certified the mathematics. The second chart places each source against its reported exponent saving κ. A larger κ describes a stronger asymptotic saving in the stated source model; it does not determine its finite constants.
The wider reconciled historical streams also contain unmerged, disputed or announcement-only candidates. They remain identifiable in the downloadable source ledger; an unavailable or pending acceptance date is not replaced with an invented merge date. The page does not poll for new results or reconstruct every intervening title edit.
The vertical coordinate in both charts measures input size. Here n is the number of bits in each operand, not the product's length, bytes, a compiler rank or a count of group vertices.
Many certified sizes are too large even for ordinary scientific notation. The chart stores exact expressions and plots their compressed coordinate:
Y = log₂(log₂(log₂ n)) n = 2^(2^(2^Y)) bits per operand
Examples of the scale; these are not crossover results.
Chart height Y
Input bits n
2
65,536
3
2^256
4
2^65536
For an upper written U = 2^(2^P), its plotted height is log₂ P. Lower on the chart means fewer input bits. The “linear” and “logarithmic spacing” controls change the spacing of Y, not the underlying certified sizes. No operand of these enormous sizes is constructed.
What do the marks, lines and empty entries mean?
A blue upper mark is a sufficient bound. A lower mark is a necessary bound for its declared family. A vertical segment joins compatible lower and upper endpoints; it is a mathematical range, not a statistical confidence interval. An entry with only one endpoint does not have a hidden second endpoint.
Individual mode connects audited uppers as a visual guide and can rise or fall. It does not interpolate costs for the missing entries. Running-best mode keeps only the smallest certified upper encountered so far; that step curve necessarily cannot rise. Equal uppers may result from a shared conservative proof gate, rather than equal actual performance. Uncosted activity ticks have no numerical vertical value.
Hover or focus a mark, then open its source card. Read the counted realization, effective saving, retained assumptions and certificate before comparing it with another point.
Understand the bounds
Is a sufficient upper the actual first crossover?
No. A sufficient upper U provides a particular, explicitly counted construction that wins for every input size at or above its verified domain, under its listed contracts. The same construction may win much earlier. The upper also need not be close to the best possible proof of that construction.
A necessary lower L proves that no allowed member of the declared family strictly wins below L. Such a proof needs compulsory work in that family. A very large template, an activation rule or the threshold where an upper-bound proof starts working does not by itself establish a lower.
A range combines those two statements only when the lower family includes the counted upper witness. It does not locate the exact first win or the smallest eventual-domination threshold.
Why do the policy and family qualifications matter?
Some lower proofs concern a literal, unreduced source realization: its native word, prescribed group sweep and paid operations remain present. Pruning, compression, aggregation, a smaller supplier or a different synthesis may fall outside that family. The source card states those restrictions.
Where a comparison family permits an inactive branch, the proof may explicitly require that branch to return the identical GMP reference. That is an added family rule when stated as such; it is not silently treated as an original source fact.
The quantifiers differ: a lower can cover all valid switching policies within its narrow family, while a sufficient upper establishes one particular counted schedule. A policy that chooses GMP forever has no strict crossover, so an existential upper is not an upper for every policy.
Can a better exponent have a worse crossover?
Yes. An asymptotic saving does not pay for its finite setup, native word, group cover, precision or recursion constants. A compiler or native-constant improvement at unchanged κ can also improve feasibility and belongs in this history. The individual sequence is therefore primary; the running best is an optional summary.
There is even a checked separated-endpoint example: the declared PR531 family's sufficient upper lies below the declared PR4416 family's necessary lower, although PR4416 was merged later and reports a larger κ. This orders those two restricted families under their assumptions. It does not prove a trend across the history or order every possible implementation of either idea.
The operation-count model is a fixed, nonuniform Boolean circuit model. Its paid basis is AND and XOR. If a circuit uses A AND gates and X XOR gates, the selected tariff is:
Cρ(n) = A(n) + ρ · X(n), with ρ > 0
The slider changes the relative XOR price ρ. It does not set CPU frequency, nanoseconds per gate, SIMD width, a memory bandwidth or a hardware benchmark. Bounds advertised as valid for every positive tariff are proved with the needed separate gate-type inequalities; they are not fitted at one slider setting.
Circuit generation, coefficients determined only by public input length, and fixed wiring are free in this model. Input-dependent arithmetic, carries, signs, clears, data selection, required movement and recovery are charged through the stipulated Boolean lowering. A “free wire” does not make arbitrary data processing free.
Does this show when an implementation will beat GMP on my computer?
No. Cache behavior, allocation, instruction throughput, parallelism, memory limits and engineering choices require a physical runtime model and measurements. An astronomical Boolean upper is a mathematical guarantee in its stated model, not a feasible experiment or a recommended implementation.
The common model makes its conditional comparisons meaningful. It does not make different machine models interchangeable: a historical Word-RAM improvement, for example, is not automatically an improvement in this Boolean model.
The reference algorithms
What does “optimized GMP” mean at impossible input sizes?
The reference is a declared, source-derived circuit family based on GMP 6.3.0, its selected 64-bit native Skylake routines, actual algorithm thresholds and the stated continuation of the TABLE3 selector. The audit includes source cases for recursive products, Toom and interpolation, FFT and modular branches, native routines, carry corrections and memory/cursor operations.
At lengths beyond a physical machine's address space, this is an explicit mathematical continuation of that reference under the documented public-size, valid-array, correctness and compilation contracts. It is not a claim that an ordinary GMP binary can allocate those inputs. Unbounded public sizes and the continuation are part of the comparator's definition.
Its proved cost envelopes are conservative upper bounds, not exact GMP counts. A tighter proof of the same envelope can strengthen a necessary lower calculation without changing the reference algorithm. Historical certificates keep their original bytes and assumptions; a new endpoint needs its own checked source-specific argument.
Where does Harvey–van der Hoeven fit?
The project also investigates Harvey–van der Hoeven's asymptotically fast multiplication. The published asymptotic result and its stated base-case split do not supply all numerical constants needed for an exact full-runtime crossover in the same model.
The 222-entry historical feasibility graph is admitted against the specified optimized GMP reference. It is not a graph of numerically established crossovers against the original HvH algorithm. Separate HvH envelopes, component calculations or exploratory scenarios shown elsewhere must be read with their own labels; missing constants are not silently set to one.
Each certificate identifies what was actually counted. Some concern a literal original source family. Others construct a new Gaussian/Fermat Boolean realization of a native complex core explicitly selected by that PR. That can give a legitimate bound without pricing the PR's original changed BIT circuit, bootstrap method, phase-fusion outer algorithm or Word-RAM runtime.
Those distinctions are substantive. Reusing the selected native theorem is not permission to transfer an ancestor's upper, invoice, owner assignment or cutoff. The audit binds immutable source heads, manifests, selected programs and their orientations, required frames, complete owner/physical schedules, invoices and parameters as needed. Exact byte identity may justify importing a named component; equal κ, a family tag or a matching profile alone does not.
Some initial parser quotes belonged to referenced or predecessor results. Where primary source and merge evidence establish the actual selected target, both values are preserved and the correction is disclosed. A source correction is not a new historical-record adjudication.
Why are 196 entries scoped but not given a number?
A source can contribute a validation, obstruction, local identity, decoder bound, restricted interface or useful tooling without supplying a separately selected complete integer multiplier. Its own contribution can be classified honestly without inventing a crossover. That classification does not deny the existence or value of the algorithms it examines.
An unchanged κ is not a reason to exclude an actual implementation: constant improvements and independently bound source-identical realizations can still matter. Conversely, a title, announcement, merged status or numerical exponent is not enough to establish an implementation and its full costs.
The remaining 177 open entries retain specific obligations. Examples include recovering a selected native word, resolving a source selector, binding a complete owner schedule, pricing a fresh invoice, or proving the needed all-size/precision interface. “Open” does not mean disproved; “source fetched” does not mean numerically solved.
The same fixed comparator now has a separately checked upper envelope of 2^1875(n+1)^8 Boolean gates. It tightens the necessary lower for PR147 to 2^85 input bits, and for PR890 and PR942 to 2^94 bits, for their explicitly declared unpruned complete-cover circuit families. This counts a surviving paid source operation at every group vertex. It does not multiply that floor by an unproved coordinate factor.
These lower bounds cover all valid public switching policies in those families. Their sufficient uppers use one counted schedule above its verified domain. A policy that always calls GMP never crosses. PR147 covers the early Gaussian branch only; the other two retain separately funded record tails. Other compressed, pruned or original hybrid implementations are excluded. The wide remaining intervals do not establish practical feasibility.
What does the 222-entry update add?
The 25 October update adds 19 source entries with numerical bounds. PR533, PR536 and PR538 now have separately reviewed lower and upper arguments for the same declared Gaussian-core realization. PR608 and PR777 add sufficient upper schedules. Seventeen newly costed source entries have a necessary lower of 2^94 bits for their stated complete, unpruned literal-cover families.
The lower covers every valid public switching policy within its declared family. An upper proves that one fully counted schedule wins above its stated domain. It does not make every policy win, and it does not determine the first crossover of the original implementation. Several remaining source or analytic interfaces are retained assumptions. The individual cards identify metadata reconciliation, recovered native bytes, changed realizations and other qualifications.
Earlier numerical endpoints are preserved. A higher reported exponent alone does not lower these bounds, and gaps in the graphs are not assigned a value.
What has been verified?
What do the scripts and peer receipts establish?
The package preserves primary source bytes, hashes, written arguments, exact rational/integer evaluators and separate AI review receipts. Depending on the case, checks include selected program identities, finite scalar or frame replays, full owner/window censuses, negative controls, complete invoices, moment enclosures, precision/stock reserves and every outer cost row.
Each receipt states what was actually rerun. Authenticating an earlier replay is not the same as rerunning it. A scalar specialization or a finite GF(2) frame check does not prove an arbitrary-input operator endpoint, spectator restoration or absolute phase. Such native, all-size compiler and analytic statements remain explicit hypotheses where not separately established.
“Closed” means the declared conditional certificate and review checks have closed. It does not mean a complete Lean proof, formal verification of every source translation, independent human endorsement, an unconditional theorem about every implementation, or an exact first crossover.
Publication note: the final replay exposed a stale proof-document reference in PR2077. A separately reviewed refresh changed four provenance hashes while preserving every mathematical value, source selection, invoice and contract. Read the exact correction audit ↗.
How can I reproduce or challenge a result?
Open a point's source card and identify its exact counted realization, model, lower/upper scope and retained premises.
Download every required archive part, the package manifest and restore tool from the reproduction page. Restore the complete folder offline with hash checking.
Read the written derivation and both review receipts, then run the advertised per-case reproduction commands. Compare the frozen certificate bytes and exact hashes.
When reporting a problem, name the PR, source commit, certificate, disputed step and counterexample or failed command. Keep a source-selection error separate from an arithmetic error or a missing universal premise.
Content-addressed storage keeps identical bytes once while preserving every original path. All required parts matter: downloading only one ZIP does not reconstruct the whole research collection.
Crossover Lab is a project by Alejandro Zarzuelo Urdiales, with AI-assisted research, source auditing, mathematical derivations and implementation. The original constructions, source packages, reviews and community discussions belong to their credited authors. This explorer does not claim authorship of those upstream results.
Credits and source links are retained per entry, including the underlying integer-multiplication research repository and community ↗, the GMP project, and the work of David Harvey and Joris van der Hoeven. Please cite the relevant primary construction and its authors alongside the specific audit certificate when discussing a result.