Tracking Issue for bigint helper methods

Feature gate: #![feature(bigint_helper_methods)]

Stable (1.91.0)

impl uN {
    fn carrying_add(self, rhs: uN, carry: bool) -> (uN, bool);
    fn borrowing_sub(self, rhs: uN, borrow: bool) -> (uN, bool);
    fn carrying_mul(self, rhs: uN, carry: uN) -> (uN, uN);
}

Const-unstable

impl uN {
    const fn carrying_add(self, rhs: uN, carry: bool) -> (uN, bool);
    const fn borrowing_sub(self, rhs: uN, borrow: bool) -> (uN, bool);
    const fn carrying_mul(self, rhs: uN, carry: uN) -> (uN, uN);
    const fn carrying_mul_add(self, rhs: uN, carry: uN, add: uN) -> (uN, uN);
}

Unstable

impl uN {
    const fn widening_mul(self, rhs: uN) -> (uN, uN);
}
impl iN {
    const fn widening_mul(self, rhs: uN) -> (iN, iN);
}

The below methods are now tracked in #151989:

impl iN {
    const fn carrying_add(self, rhs: iN, carry: bool) -> (iN, bool);
    const fn borrowing_sub(self, rhs: iN, carry: bool) -> (iN, bool);
    const fn carrying_mul(self, rhs: iN, carry: iN) -> (uN, iN);
    const fn carrying_mul_unsigned(self, rhs: uN, carry: uN) -> (uN, iN);
    const fn carrying_mul_add(self, rhs: iN, carry: iN, add: iN) -> (uN, iN);
    const fn carrying_mul_unsigned_add(self, rhs: uN, carry: uN, add: iN) -> (uN, iN);
}

Previous Description

These methods are intended to help centralise the effort required for creating efficient big integer implementations, by offering a few methods which would otherwise require special compiler intrinsics or custom assembly code in order to do efficiently. They do not alone constitute big integer implementations themselves, but are necessary building blocks for a larger implementation.

Public API

// On unsigned integers:

/// `self * rhs` (wide multiplication, same as `self.carrying_mul(rhs, 0)`)
const fn widening_mul(self, rhs: Self) -> (Self, Self);


// On signed integers:

/// `self + rhs + carry` (full adder)
const fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self - rhs - carry` (full "subtractor")
const fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

Stabilized as part of 1.91, but not yet const stable:

// On unsigned integers:

/// `self + rhs + carry` (full adder)
const fn carrying_add(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self - rhs - carry` (full "subtractor")
const fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

/// `self * rhs + carry` (multiply-accumulate)
const fn carrying_mul(self, rhs: Self, carry: Self) -> (Self, Self);

/// `self * rhs + carry` (multiply-accumulate-carry)
const fn carrying_mul_add(self, rhs: Self, addend: Self, carry: Self) -> (Self, Self);

Steps / History

widening_mul RFC: widening_mul rfcs#2417
Initial implementation of carrying_add, borrowing_sub, carrying_mul, and widening_mul Add carrying_add, borrowing_sub, widening_mul, carrying_mul methods to integers #85017
Remove implementations on signed types Remove bigint_helper_methods for *signed* types #90848 per discussion in Signed carry carrying_add in bigint_helper_methods #90541
Add new carrying_add and borrowing_sub on signed types: Reimplement carrying_add and borrowing_sub for signed integers. #93873
Add a compiler intrinsic to back bigint_helper_methods #133663
Add assembly tests to ensure this keeps doing the right thing
- One for carrying_add was added in Fix chaining carrying_adds #133674
Clarify documentation
("without the ability to overflow" can be confusing.)
Final commenting period (FCP)
Partial Stabilization PR Partial-stabilize the basics from bigint_helper_methods #144494

Unresolved Questions

Should these be implemented using compiler intrinsics? LLVM currently has no equivalents, so, we'd have to custom-build some.
- Done in Add a compiler intrinsic to back bigint_helper_methods #133663
Should an alternative API be provided for widening_mul that simply returns the next-larger type? What would we do for u128/i128?
What should the behaviour be for signed integers? Should there be implementations for signed integers at all?
Is the "borrowing" terminology worth it for subtraction, or should we simply call that "carrying" as well for consistency?
Are there other methods that should be added in addition to the existing ones?

Are there other methods that should be added in addition to the existing ones?

I'd like a mul_mod, as shown in #85017, because I think you can't implement it efficiently without asm and it's a basic block for power_mod and other things.

Another set of methods that could be useful that I'll probably offer implementations for at some point:

/// `(self << rhs) | carry`
fn carrying_shl(self, rhs: u32, carry: Self) -> (Self, Self); 

/// `(self >> rhs) | carry`
fn borrowing_shr(self, rhs: u32, carry: Self) -> (Self, Self);

/// `self << rhs`
fn widening_shl(self, rhs: u32) -> (Self, Self);

/// `self >> rhs`
fn widening_shr(self, rhs: u32) -> (Self, Self);

Essentially, return the two halves of a rotation, i.e. x.widening_shl(y) is the same as (x << y, x >> (BITS - y)) and similarly for widening_shr. Not sure whether they should allow rhs == BITS or not, but presumably they wouldn't for consistency with existing shift methods.

@scottmcm

From @scottmcm in the original PR:

Some prior art I happened upon: https://docs.rs/cranelift-codegen/0.74.0/cranelift_codegen/ir/trait.InstBuilder.html#method.isub_bin
Same as isub with an additional borrow flag input. Computes:
   a = x - (y + b_{in}) \pmod 2^B

Why don't we add carrying_mul and widening_mul for i128/u128 as well?

Mostly effort implementing them efficiently. In the meantime, you can do it with four calls to the u64 version. Or three if you want to be fancy.

fn borrowing_sub(self, rhs: Self, carry: bool) -> (Self, bool);

I was very confused by this function name at first, since borrowing in Rust usually refers to references. I am not a native speaker, but I do formal mathematical work in English professionally, and yet I never before heard the term "borrowing" in the context of subtraction. So I think this, at least, needs some explanation in the docs. (I would have expected something like carrying_sub, but maybe that is nonsense for a native speaker.)

The current docs for some of the other methods could probably also be improved: they talk about not having the "ability to overflow", which makes it sound like not overflowing is a bad thing.

The word borrow here comes from the terminology for a full subtractor. I am thinking that maybe the borrowing_sub function could be removed altogether. The same effect that borrowing_sub has can be obtained from carrying_add by making the first carrying_add in the chain have a set carry bit, and then bitnot every rhs. This fact could be put in the documentation of carrying_add.

The word borrow here comes from the terminology for a full subtractor. I am thinking that maybe the borrowing_sub function could be removed altogether. The same effect that borrowing_sub has can be obtained from carrying_add by making the first carrying_add in the chain have a set carry bit, and then bitnot every rhs. This fact could be put in the documentation of carrying_add.

Considering how the primary goal of these methods is to be as efficient as possible, usually optimising down to a single instruction, I don't think it'd be reasonable to just get rid of subtraction in favour of telling everyone to use addition instead. Definitely open to changing the name, though.

These helper methods will not be very useful to me unless they are implemented for every kind of integer. Here is an implementation for a widening multiplication-addition for u128:

/// Extended multiply-addition of `(lhs * rhs) + add`. The result is returned as a tuple of the wrapping part and the
/// overflow part. No numerical overflow is possible even if all three arguments are set to their max values.
pub const fn widen_mul_add(lhs: u128, rhs: u128, add: u128) -> (u128, u128) {
    //                       [rhs_hi]  [rhs_lo]
    //                       [lhs_hi]  [lhs_lo]
    //                     X___________________
    //                       [------tmp0------]
    //             [------tmp1------]
    //             [------tmp2------]
    //     [------tmp3------]
    //                       [-------add------]
    // +_______________________________________
    //                       [------sum0------]
    //     [------sum1------]

    let lhs_lo = lhs as u64;
    let rhs_lo = rhs as u64;
    let lhs_hi = (lhs.wrapping_shr(64)) as u64;
    let rhs_hi = (rhs.wrapping_shr(64)) as u64;
    let tmp0 = (lhs_lo as u128).wrapping_mul(rhs_lo as u128);
    let tmp1 = (lhs_lo as u128).wrapping_mul(rhs_hi as u128);
    let tmp2 = (lhs_hi as u128).wrapping_mul(rhs_lo as u128);
    let tmp3 = (lhs_hi as u128).wrapping_mul(rhs_hi as u128);
    // tmp1 and tmp2 straddle the boundary. We have to handle three carries
    let (sum0, carry0) = tmp0.overflowing_add(tmp1.wrapping_shl(64));
    let (sum0, carry1) = sum0.overflowing_add(tmp2.wrapping_shl(64));
    let (sum0, carry2) = sum0.overflowing_add(add as u128);
    let sum1 = tmp3
        .wrapping_add(tmp1.wrapping_shr(64))
        .wrapping_add(tmp2.wrapping_shr(64))
        .wrapping_add(carry0 as u128)
        .wrapping_add(carry1 as u128)
        .wrapping_add(carry2 as u128);
    (sum0, sum1)
}

I have tested this with my crate awint.

edit: There is a version of this that uses the Karatsuba trick to use 3 multiplications instead of 4, but it incurs extra summations, branches, and is not as parallel. For typical desktop processors the above should be the fastest.

I would make a PR for that.

Some alternative signatures include u128::widen_mul_add(lhs, rhs, add), lhs.widen_mul_add(rhs, add), or add.widen_mul_add(lhs, rhs). In awint my general purpose mul-add function is mul_add_triop which uses the third signature but takes self mutably and add-assigns lhs * rhs. I'm not sure which is best.

I would also change up the documentation headers for the carrying_add function to say

Extended addition of `self + rhs + carry`. The booleans are interpreted as a single bit
integer of value 0 or 1. If unsigned overflow occurs, then the boolean in the tuple
returns 1. The output carry can be chained into the input carry of another carrying add,
which allows for arbitrarily large additions to be calculated.

I specifically note unsigned overflow, because that happens for both signed and unsigned
integers because of how two's complement works.

borrowing_sub should be left in with its naming, but its documentation could be

Extended subtraction of `self - rhs - borrow`. The "borrowing" here refers to borrowing in the full subtractor sense.
The booleans are interpreted as a single bit integer of value 0 or 1. If unsigned overflow occurs, then the boolean
in the tuple returns 1. The output carry can be chained into the input carry of another borrowing subtract,
which allows for arbitrarily large subtraction to be calculated.

Auto merge of #144494 - scottmcm:min_bigint_helpers, r=Mark-Simulacrum

It looks like all of these (for u{N}) except widening_mul shipped in Rust 1.91: https://blog.rust-lang.org/2025/10/30/Rust-1.91.0/ (stabilization PR)

I would be curious where to track const fn support as that's the one piece missing for our purposes

@scottmcm

It looks like all of these (for u{N}) except widening_mul shipped in Rust 1.91? https://blog.rust-lang.org/2025/10/30/Rust-1.91.0/

Updated the issue

I would be curious where to track const fn support as that's the one piece missing for our purposes

From the stabilization PR #144494:

(I did not const-stabilize them in this PR because the fallbacks are using #[const_trait] plus there's two new intrinsics involved, so I didn't want to also open those cans of worms here. Given that both intrinsics have fallbacks, and thus don't do anything that can't already be expressed in existing Rust, const-stabilizing these should be straight-forward once the underlying machinery is allowed on stable. But that doesn't need to keep these from being usable at runtime in the mean time.)

I think anyone interested could probably make a PR to const stabilize these. It was a good idea to keep them separate but I don't think there is anything that would prevent const stabilization now, given const traits are used for convenience rather than out of necessity.

Cc @scottmcm in case you were planning to follow up here yourself

This is just my personal 2¢, but I think that the signed integer methods and the widening multiplication should be separated out into two new issues, keeping this issue only for the const-stabilisation of the existing methods. Maybe even creating a new thread for that and closing this one.

This thread has become a bit of a mess referencing a lot of things and I think it would be helpful to separate them out, even if the feature flags remain unified for now.

I personally would expect any PRs preparing these sets of methods, updates regarding their design, and stabilisation FCPs will be separate.

Auto merge of rust-lang#144494 - scottmcm:min_bigint_helpers, r=Mark-…

Auto merge of #144494 - scottmcm:min_bigint_helpers, r=Mark-Simulacrum

I opened new discussion for signed integer methods: #151989.

Place for discussing const-stability of currently stable methods: #152015

Widening multiplication: #152016

Since that should cover all the unstable methods with the feature flag, I'm going to make a PR to move the tracking issues over and then close this one. As mentioned, a lot of discussion has happened and with part of the feature already merged, it's a bit confusing to track here; we should move into the three new issues for discussion instead.

Rollup merge of rust-lang#152018 - clarfonthey:bigint-tracking-issues…

Unrolled build for #152018

Rollup merge of #152018 - clarfonthey:bigint-tracking-issues, r=scottmcm

fix(amm): U256::mul four-product carry propagation

Navigation Menu

Tracking Issue for bigint helper methods #85532

Stable (1.91.0)

Const-unstable

Unstable

Previous Description

Public API

Steps / History

Unresolved Questions

128 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Tracking Issue for bigint helper methods #85532

Description

Stable (1.91.0)

Const-unstable

Unstable

Previous Description

Public API

Steps / History

Unresolved Questions

Activity

leonardo-m commented on May 21, 2021

clarfonthey commented on May 21, 2021

clarfonthey commented on Jun 1, 2021

photino commented on Sep 7, 2021

clarfonthey commented on Sep 7, 2021

RalfJung commented on Sep 9, 2021

AaronKutch commented on Sep 9, 2021

clarfonthey commented on Sep 9, 2021

AaronKutch commented on Sep 9, 2021

clarfonthey commented on Sep 9, 2021

AaronKutch commented on Sep 9, 2021

AaronKutch commented on Sep 9, 2021

AaronKutch commented on Sep 9, 2021

128 remaining items

tarcieri commented on Oct 30, 2025

tgross35 commented on Oct 30, 2025

clarfonthey commented on Oct 30, 2025

nickkuk commented on Feb 2, 2026

clarfonthey commented on Feb 2, 2026

clarfonthey commented on Feb 2, 2026

clarfonthey commented on Feb 2, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions