Tracking Issue for bigint helper methods · Issue #85532 · rust-lang/rust (original) (raw)

Feature gate: #![feature(bigint_helper_methods)]

This is a tracking issue for the following methods on integers:

• carrying_add
• borrowing_sub
• carrying_mul
• carrying_mul_add
• widening_mul

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 + 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);

/// 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);

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
• Clarify documentation
  ("without the ability to overflow" can be confusing.)
• Final commenting period (FCP)
• Stabilization PR

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?