Tracking Issue for bigint helper methods

[clarfonthey]

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?

[leonardo-m]

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.

[clarfonthey]

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.

[clarfonthey]

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

[photino]

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

[clarfonthey]

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.

[RalfJung]

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.

[AaronKutch]

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.

[clarfonthey]

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.

[AaronKutch]

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.

[clarfonthey]

I would make a PR for that.

[AaronKutch]

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.

[AaronKutch]

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.