Skip to content

Optimize representation-independent BigInteger arithmetic - #132709

Merged
tannergooding merged 19 commits into
dotnet:mainfrom
tannergooding:tannergooding-biginteger-dense-zero-limbs
Sep 1, 2026
Merged

tannergooding merged 19 commits into
dotnet:mainfrom
tannergooding:tannergooding-biginteger-dense-zero-limbs

Conversation

@tannergooding

Copy link
Copy Markdown
Member

Optimize representation-independent BigInteger arithmetic

BigInteger currently carries every native limb through arithmetic even when the operand has
structure that makes much of that work unnecessary. This change keeps the existing representation
but adds shared arithmetic kernels for:

  • complete low-zero-limb prefixes;
  • powers of two and shifted divisors;
  • repeated and shifted-repeated limb streams;
  • scalar factors 3, 5, and 7, including factor-aware powers;
  • multi-limb Mersenne divisors of the form B^k - 1.

The dispatches are crossover-gated, and ordinary grammar-school division and multiplication retain
their original kernels. Packed 3/5/7 power tables carry both 32-bit and 64-bit storage in
architecture-neutral IL and select the native layout through JIT-folded nint.Size.

Representative Windows x64 results use identical hosts, six alternating processes, and
DOTNET_TieredCompilation=0. Values are medians of six processes.

Public BigInteger

Common operand sizes

Operation Baseline Changed Change
3^47 201.17 ns 133.75 ns -33.5%
3^257 538.82 ns 150.77 ns -72.0%
7^257 582.91 ns 168.80 ns -71.0%
10^257 589.54 ns 191.08 ns -67.6%
21^128 414.49 ns 262.76 ns -36.6%
35^257 718.07 ns 446.44 ns -37.8%
Divide 769 bits by 3 118.93 ns 96.87 ns -18.5%
Divide 2,047 bits by 7 215.44 ns 156.24 ns -27.5%
Four repeated-one limbs 124.12 ns 101.80 ns -18.0%
Seven shifted repeated-three limbs 217.82 ns 136.68 ns -37.3%
4,096 bits / (3 << 257) via DivRem 1,084.26 ns 776.16 ns -28.4%

Larger structured operands

Operation Baseline Changed Change
3^1025 1,531.49 ns 202.40 ns -86.8%
7^1025 2,130.20 ns 228.66 ns -89.3%
10^1025 2,527.87 ns 258.62 ns -89.8%
31 repeated-one limbs 2,128.02 ns 265.36 ns -87.5%
DivRem by B^31 - 1 6,804.60 ns 706.29 ns -89.6%
4,096 bits / (3 << 2,047) via DivRem 2,565.31 ns 499.77 ns -80.5%
Multiply with 16,384 trailing zero bits 24,280.55 ns 563.00 ns -97.7%
Common-offset divide at 16,384 bits 631.86 ns 110.10 ns -82.6%
Common-offset GCD at 16,384 bits 1,593.95 ns 401.64 ns -74.8%

Allocations are unchanged for the operation-focused representative matrix; the improvement comes
from avoiding arithmetic and scans after structure has been recognized.

End-to-end PiDigits

The established PiDigits_3 Benchmarks Game workload exercises repeated BigInteger
multiplication, addition, and division together. The canonical benchmark uses 3,000 digits; 300 and
1,000 digits show how the same changes scale at more common operand sizes.

Digits .NET 10.0.11 Current baseline Layer 1 .NET 10 to current Layer 1 change Cumulative
300 3.546 ms 2.964 ms 2.767 ms -16.4% -6.6% -22.0%
1,000 37.017 ms 28.029 ms 25.143 ms -24.3% -10.3% -32.1%
3,000 354.370 ms 258.965 ms 223.798 ms -26.9% -13.6% -36.8%

The current baseline has the same allocation volume as .NET 10. Layer 1 reduces it by approximately
1.9%: from 8,846,344 to 8,676,064 bytes at 300 digits, 114,149,160 to 111,944,520 bytes at
1,000 digits, and 1,175,501,536 to 1,152,812,312 bytes at 3,000 digits.

Controls and tradeoffs

Control Baseline Changed Change
Dense divide, 47 bits 60.08 ns 60.76 ns +1.1%
Dense divide, 257 bits 68.92 ns 69.43 ns +0.7%
Dense divide, 769 bits 85.57 ns 84.46 ns -1.3%
Dense divide, 2,047 bits 126.76 ns 128.00 ns +1.0%
Dense multiply, 3 limbs 87.83 ns 90.76 ns +3.3%
Dense multiply, 17 limbs 435.11 ns 445.86 ns +2.5%
Divide 47 bits by generic 11 45.84 ns 47.63 ns +3.9%
DivRem by three-limb Mersenne divisor 246.58 ns 253.96 ns +3.0%
4,096 bits / (3 << 47) via DivRem 819.44 ns 823.00 ns +0.4%

The small regressions above are the fixed dispatch cost before enough arithmetic is available to
amortize it. Larger instances cross over sharply; no representative control regresses by 5%.

Validation

  • 8,587 System.Runtime.Numerics tests pass on Windows x64.
  • 8,587 tests pass with DOTNET_EnableHWIntrinsic=0.
  • 8,586 tests pass on Windows x86, with one expected 64-bit-only skip.
  • Independent model review and differential arithmetic harnesses covered repeated limbs, shifted
    streams, Mersenne division, scalar division, powers, GCD, and both process widths.

Note

This pull request description was drafted with GitHub Copilot.

tannergooding and others added 13 commits August 24, 2026 10:03
Preserve baseline kernels for ordinary operands, gate specialized arithmetic at measured crossovers, and address cross-platform and review findings.

Co-authored-by: Copilot App <[email protected]>
Assert span and aliasing contracts and avoid copying dividend buffers before Burnikel-Ziegler fallthroughs.

Co-authored-by: Copilot App <[email protected]>
@azure-pipelines

Copy link
Copy Markdown
Azure Pipelines:
Successfully started running 3 pipeline(s).
13 pipeline(s) were filtered out due to trigger conditions.
There may be pipelines that require an authorized user to comment /azp run to run.

@dotnet-policy-service

Copy link
Copy Markdown
Contributor

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

Optimizes BigInteger arithmetic by detecting structured operands and dispatching to specialized multiplication, division, GCD, shift, and exponentiation kernels.

Changes:

  • Adds structured-limb and Mersenne arithmetic paths.
  • Adds cached power tables for factors 3, 5, and 7.
  • Expands property tests across signs, architectures, and arithmetic boundaries.

Two unresolved findings remain: an untested shifted-limb fallback and an unreachable power-of-two branch.

Show a summary per file
File Description
BigIntegerPropertyTests.cs Adds structured arithmetic coverage.
BigIntegerCalculator.Utils.cs Moves shared debug initialization.
BigIntegerCalculator.SquMul.cs Adds structured multiplication paths.
BigIntegerCalculator.ShiftRot.cs Moves shared right-shift logic.
BigIntegerCalculator.PowTables.cs Adds packed power tables.
BigIntegerCalculator.PowMod.cs Adds table-backed exponentiation.
BigIntegerCalculator.GcdInv.cs Optimizes common-zero-limb GCD.
BigIntegerCalculator.DivRem.cs Adds specialized and Mersenne division.
BigInteger.cs Integrates optimized arithmetic dispatch.
System.Runtime.Numerics.csproj Includes the power-table source.
BigIntegerCalculator.Shared.cs Adds shared arithmetic kernels.

Review details

  • Files reviewed: 11/11 changed files
  • Comments generated: 2
  • Review effort level: Balanced

@tannergooding
tannergooding marked this pull request as ready for review August 25, 2026 16:02
Copilot AI review requested due to automatic review settings August 25, 2026 16:02
@azure-pipelines

Copy link
Copy Markdown
Azure Pipelines:
Successfully started running 3 pipeline(s).
13 pipeline(s) were filtered out due to trigger conditions.
There may be pipelines that require an authorized user to comment /azp run to run.

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Review details

Suppressed comments (1)

Previously missed (1) — in code that hasn't changed since the last review.

src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:996

  • This 32-bit implementation is unreachable: both production callers are guarded by nint.Size == 8 (BigIntegerCalculator.SquMul.cs:40-43 and :286-288), and there are no other call sites. Keeping an unexercised architecture branch risks divergence; either remove it and make the helper explicitly 64-bit-only, or enable the x86 dispatch and add benchmark-backed tests.
            else
            {
                if (((ulong)(uint)repeatedLimb * convolutionLength) > uint.MaxValue)
                {
                    return false;
  • Files reviewed: 11/11 changed files
  • Comments generated: 1
  • Review effort level: Balanced

Copilot AI review requested due to automatic review settings August 25, 2026 16:22

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Review details

Suppressed comments (1)

Previously missed (1) — in code that hasn't changed since the last review.

src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:787

  • This file is compiled into both System.Private.CoreLib and System.Runtime.Numerics, but the new sparse/repeated multiplication and specialized scalar-division kernels starting here have no System.Private.CoreLib call sites; System.Number.BigInteger still uses Mul1/MultiplyNaive and its own division path. Together with the moved RightShiftSelf, this adds hundreds of lines of unused IL (and potentially R2R code) to CoreLib for optimizations consumed only by System.Runtime.Numerics. Please keep only genuinely shared helpers in this file and place the BigInteger-only kernels in the Runtime.Numerics partial files, or quantify and justify the CoreLib binary-size cost.
        internal static void MultiplyNaiveSparse(ReadOnlySpan<nuint> left, ReadOnlySpan<nuint> right, Span<nuint> bits)
  • Files reviewed: 11/11 changed files
  • Comments generated: 0 new
  • Review effort level: Balanced

Co-authored-by: Copilot App <[email protected]>
Copilot AI review requested due to automatic review settings August 25, 2026 22:59

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Review details

  • Files reviewed: 11/11 changed files
  • Comments generated: 1
  • Review effort level: Balanced

Copilot AI review requested due to automatic review settings August 28, 2026 15:41

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot review overview

Review tier: Balanced
Findings: 1 Low severity

New issues introduced by this change (1)
Severity Finding
Low severity src/​libraries/​System.Runtime.Numerics/​tests/​BigInteger/​BigIntegerPropertyTests.cs — The shifted scalar cases here (6, 12, and 20) all reduce to the dedicated 3/5 paths, while…
Issues resolved since last review (1)
Severity Finding
Low severity src/​libraries/​System.Runtime.Numerics/​tests/​BigInteger/​BigIntegerPropertyTests.cs — The new table-continuation path is not covered by these cases: the largest single-factor exponent… View resolved comment
Suppressed comments (1)

Previously missed (1) — in code that hasn't changed since the last review.

src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:787

  • This structured-multiplication kernel is only referenced from System.Runtime.Numerics-specific files, but placing it in the shared source also emits it into System.Private.CoreLib. The same applies to the repeated-run helpers, scalar division machinery, and relocated RightShiftSelf; repository-wide caller searches find no CoreLib consumers for those methods. Please keep or conditionally compile the Numerics-only kernels outside SYSTEM_PRIVATE_CORELIB, otherwise this optimization adds hundreds of lines of unused IL to CoreLib without binary-size evidence.
        internal static void MultiplyNaiveSparse(ReadOnlySpan<nuint> left, ReadOnlySpan<nuint> right, Span<nuint> bits)

Co-authored-by: Copilot Autofix powered by AI <[email protected]>
Copilot AI review requested due to automatic review settings August 28, 2026 16:04

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot review overview

Review tier: Balanced
Findings: None

Issues resolved since last review (1)
Severity Finding
Low severity src/​libraries/​System.Runtime.Numerics/​tests/​BigInteger/​BigIntegerPropertyTests.cs — The shifted scalar cases here (6, 12, and 20) all reduce to the dedicated 3/5 paths, while… View resolved comment
Suppressed comments (4)

Previously missed (2) — in code that hasn't changed since the last review.

src/libraries/System.Private.CoreLib/src/System/Numerics/BigIntegerCalculator.Shared.cs:994

  • The 32-bit implementation in this else branch is unreachable: the only production call sites in Square and Multiply both require nint.Size == 8 before invoking this helper. Either remove the 32-bit branch to avoid carrying dead arithmetic code, or remove those caller guards and add x86 coverage if the path is intended to run there.
            else
            {
                if (((ulong)(uint)repeatedLimb * convolutionLength) > uint.MaxValue)

src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:78

  • This explanation omits the adjacent base-7 constant and therefore does not describe how Log2OfSevenFractionalBits or log2OfSevenLower is derived. Include floor((log2(7) - 2) * 2^64) and state that prepending 2 reconstructs both the base-5 and base-7 values.

This issue also appears in the following locations of the same file:

  • line 123
  • line 402
            // Accordingly, these constants are:
            //   floor((log2(3) - 1) * 2^64)
            //   floor((log2(5) - 2) * 2^64)
            // Prepending 1 and 2 below reconstructs floor(log2(3) * 2^64) and
            // floor(log2(5) * 2^64), respectively.

src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:125

  • These hand-authored packed tables are executable arithmetic data, but the added tests do not validate every cached entry against an independent calculation (for example, several intermediate powers are never selected by the deterministic cases). A single bad limb would silently return an incorrect BigInteger.Pow result. Add a test that enumerates every 3/5/7 entry for the native layout and compares it with repeated multiplication; the existing x86/x64 test runs will then validate both layouts.
        private static ReadOnlySpan<ulong> Pow3TableStorage64 =>
        [
            1, 0x0006954FE21E3E81, // 3^32

src/libraries/System.Runtime.Numerics/src/System/Numerics/BigIntegerCalculator.PowTables.cs:408

  • Both the 32-bit and 64-bit packed power tables are embedded in every architecture-neutral build, so this optimization adds a substantial amount of permanent assembly data even though only one layout is used per process. Please report the resulting System.Runtime.Numerics binary-size delta and weigh it against the end-to-end gains; if the cost is material, consider a representation that avoids duplicating every limb while preserving startup performance.
        private static ReadOnlySpan<int> Pow3TableIndices32 =>
        [
            0, 2, 5, 10, 18, 32, 59,
        ];

        private static ReadOnlySpan<uint> Pow3TableStorage32 =>
        [

@jeffhandley jeffhandley left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@tannergooding @PranavSenthilnathan @eiriktsarpalis - I scanned through this and chatted with Tanner about this and agreed to proceed with merging this PR, which will unblock subsequent PRs in the queue. I want to start getting coverage of these changes early in .NET 12 Preview 1. Before we finish the comprehensive BigInteger wave of work in preview 1 though, let's plan for Pranav, Tanner, and perhaps Eirik doing a collaborative walkthrough over all the changes in this area.

Copilot AI review requested due to automatic review settings August 31, 2026 22:28

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot review overview

🔵 Needs a closer look

Review tier: Balanced
Findings: None

@tannergooding
tannergooding merged commit 730531f into dotnet:main Sep 1, 2026
133 of 135 checks passed
@dotnet-milestone-bot dotnet-milestone-bot Bot added this to the 12.0-preview1 milestone Sep 2, 2026
@github-actions github-actions Bot locked and limited conversation to collaborators Oct 2, 2026
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants