# Naming \`bigint\_helper\_methods\` (bike-shedding) **URL:** \ **Category:** libs\ **Created:** [October 12, 2024, 3:14pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688 "2024-10-12T15:14:35Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![Rudxain](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rudxain/32/12209_2.png) [@Rudxain](https://internals.rust-lang.org/u/Rudxain)\ **Post date:** [October 12, 2024, 3:14pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/1 "2024-10-12T15:14:36Z")
[Context](https://github.com/rust-lang/rust/issues/85532#issuecomment-2403442775) I've created this topic for the discussion of naming those methods. Addition: - `carrying_add` seems fine. - `extending_add` is ok, but seems misleadingly similar to `widening_add` - `overflowing_add_carry` seems descriptive, but "inconsistent". We don't have to care about consistency here, as these methods have type signatures that are different from the other arithmetic methods (such as `checked_add`). - `carrying_add_carry`: Department of Redundancy Department. - `add_with_carry`: bonus for readability! but very inconsistent ☹ I'm not going to elaborate on subtraction, as I have little time, and my opinion is (overall) the same for all methods. Subtraction seems confusing to me, for similar reasons as the "Inverted Joystick Effect" (the same reason why some people flip the direction of mouse scrolling). Like, `borrowing_sub` might be interpreted as redundant (`sub_with_borrow`), or as a double-negation (`carrying_add`), depending on who you ask. ---
**Author:** ![jdahlstrom](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jdahlstrom/32/3351_2.png) [@jdahlstrom](https://internals.rust-lang.org/u/jdahlstrom)\ **Post date:** [October 12, 2024, 7:04pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/2 "2024-10-12T19:04:28Z")
I find `add_with_carry` and `subtract_with_borrow` to be very reasonable names, perhaps partly because of the x86 instructions `ADC` and `SBB`. I don't think they're necessarily inconsistent with the `overflowing_` etc functions, because the distinguishing thing is that they _take_ (not just return) the carry/borrow bit, and functions that take some extra `x` are commonly named `with_x` or `y_with_x`. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [October 12, 2024, 8:05pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/3 "2024-10-12T20:05:43Z")
I'll also mention [this comment](https://github.com/rust-lang/rust/issues/85532#issuecomment-2224994447), because people in the thread realized that we need not just `x * y + c`, but actually `x * y + z + c`: if you're implementing `z += x * y`, you need both the existing accumulator _and_ the new carry. (And both [fit](https://www.wolframalpha.com/input?i=simplify+%282%5En+-+1%29*%282%5En+-+1%29+%2B+%282%5En+-+1%29+%2B+%282%5En+-+1%29) without the possibility of overflow.) So we need a name that works with something like `mul_add_with_carry` too. ---
**Author:** ![programmerjake](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/programmerjake/32/5893_2.png) [@programmerjake](https://internals.rust-lang.org/u/programmerjake)\ **Post date:** [October 13, 2024, 2:33am UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/4 "2024-10-13T02:33:54Z")
how about `mul_add_add`? ---
**Author:** ![tspiteri](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tspiteri/32/7283_2.png) [@tspiteri](https://internals.rust-lang.org/u/tspiteri)\ **Post date:** [October 13, 2024, 6:02am UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/5 "2024-10-13T06:02:51Z")
I also like `add_with_carry`, and prefer it to `carrying_add`. I would use `sub_` instead of `subtract_` to match other methods and traits. For what it's worth, I find `sub_with_carry` confusing as that name does not give me confidence the `bool` is subtracted. Maybe this is because in the x86 instruction SBB (subtract with borrow), the flag is subtracted, while in the ARM instruction SBC (subtract with carry), the flag is inverted before subtracting. ---
**Author:** ![tspiteri](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tspiteri/32/7283_2.png) [@tspiteri](https://internals.rust-lang.org/u/tspiteri)\ **Post date:** [October 13, 2024, 9:28am UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/6 "2024-10-13T09:28:01Z")
The signed method currently called `iN::carrying_add` is a bit more confusing as is, because its input parameter is a carry flag, but its output is an overflow flag, not a carry flag. Maybe `overflowing_add_with_carry` would make sense here. It is a bit verbose, but it is a very specific method for a very specific task, so maybe the verbosity is not so bad. And this would emphasize the distinction between the unsigned and signed methods without requiring a careful reading of the docs. (Similar for `iN::borrowing_sub` -\> `overflowing_sub_with_borrow`.) ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [October 13, 2024, 6:01pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/7 "2024-10-13T18:01:55Z")
> [@tspiteri](#): > > The signed method currently called [...] TBH, I find all the signed ones very difficult to describe. It kinda feels like they want to overflow an `Ordering` (-1/0/+1), but I don't know that that's efficiently possible on actual chips, which makes me think the V1 of this at least should just stabilize the unsigned ones that are much clearer. ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [October 15, 2024, 12:18pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/8 "2024-10-15T12:18:35Z")
`add_with_carry` and `subtract_with_borrow` both seem quite verbose. In `crypto-bigint` we abbreviated those as `adc` and `sbb` which I also wasn't happy with because I feel they are quite jargony (not to mention `x86` jargon, which is just one of many platforms we support). I was actually pretty pleased with `carrying_add` and `borrowing_sub`, especially since there's already something of an established `*ing_add`/`*ing_sub` pattern with e.g. `wrapping_add`/`wrapping_sub` which also "handles" carries via wrapping. ---
**Author:** ![tspiteri](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tspiteri/32/7283_2.png) [@tspiteri](https://internals.rust-lang.org/u/tspiteri)\ **Post date:** [October 15, 2024, 2:54pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/9 "2024-10-15T14:54:49Z")
There is also the option `add_carry` and `sub_borrow`. ---
**Author:** ![winksaville](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/winksaville/32/4321_2.png) [@winksaville](https://internals.rust-lang.org/u/winksaville)\ **Post date:** [October 15, 2024, 3:47pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/10 "2024-10-15T15:47:07Z")
Another option, shorten _with_ to _w_, so add\_w\_carry and sub\_w\_borrow. ---
**Author:** ![pitaj](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pitaj/32/11262_2.png) [@pitaj](https://internals.rust-lang.org/u/pitaj)\ **Post date:** [October 15, 2024, 10:35pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/11 "2024-10-15T22:35:25Z")
Your analogy would apply if the functions didn't also take a carry argument. If they only resulted in a carry output, they would essentially be the same as `checked_add`. But since `add_with_carry` both takes a carry argument and results in a carry output, I think it makes sense to have a different naming convention. I also disagree that it's verbose, especially for something so niche. I would choose: - `add_with_carry` - `sub_with_borrow` ---
**Author:** ![clarfonthey](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/clarfonthey/32/12413_2.png) [@clarfonthey](https://internals.rust-lang.org/u/clarfonthey)\ **Post date:** [October 18, 2024, 11:43pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/12 "2024-10-18T23:43:18Z")
Just thinking more about the unsigned/signed problem, at least for addition/subtraction. Going to use the term "word" to mean digit, limb, or whatever unit you have in a bigint, for simplicity. Basically, the issue is that overflow has a different definition for signed/unsigned integers: for unsigned integers, you overflow from MAX to 0, but for signed, you overflow from MAX to MIN. For intermediate words, you always want to have the unsigned overflow behaviour: you get a new carry if you overflow past all of your bits. But for the last word, you want to know whether you overflowed in the proper sense, since it determines whether you need to add a new unit. So, it feels apt that rather than just returning `bool` here, we should return the value of that new unit directly. So, what feels like we should be doing: - have `carrying_add` and `carrying_sub`/`borrowing_sub` which use the current signature of `(T, T, bool) -> (T, bool)`, but always have unsigned semantics - have `extending_add` and `extending_sub` which have the signature `(T, T, bool) -> (T, Option)` The `extending` operation would have the following implementations for unsigned/signed characters: ```rust fn extending_add_unsigned(lhs: u32, rhs: u32, carry: bool) -> (u32, Option) { let (sum, overflow1) = lhs.overflowing_add(rhs); let (sum, overflow2) = sum.overflowing_add(carry as u32); (sum, (overflow1 | overflow2).then(1)) } fn extending_add_signed(lhs: i32, rhs: i32, carry: bool) -> (i32, Option) { let (sum, overflow1) = lhs.overflowing_add(rhs); let (sum, overflow2) = sum.overflowing_add(carry as i32); (sum, (overflow1 | overflow2).then_some(|| if overflow1 != overflow2 { -1 } else { 0 })) } ``` I'm pretty sure the signed logic is correct, but I'll need to double-check my work later. Also, based upon the feedback we've gotten from people: while the term "borrow" might be common in American teaching of subtraction, "carry" doesn't have any ambiguity and is how the instructions are generally named, so, I kind of prefer renaming `borrowing_sub` to just `carrying_sub` for less confusion. ---
**Author:** ![programmerjake](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/programmerjake/32/5893_2.png) [@programmerjake](https://internals.rust-lang.org/u/programmerjake)\ **Post date:** [October 19, 2024, 1:05am UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/13 "2024-10-19T01:05:36Z")
> [@clarfonthey](#): > > so, I kind of prefer renaming `borrowing_sub` to just `carrying_sub` for less confusion. `carrying_sub` is ambiguous. for `u32` arguments/output: - it could be like x86's `sbb` instruction which does: ```rust // carry is inverted from how it works in digital hardware, // since hardware actually just adds !rhs out = lhs.wrapping_sub(rhs).wrapping_sub(carry as u32); carry = (lhs as i64 - rhs as i64 - carry as i64) < 0; ``` - it could be like arm's `sbcs` instruction which does: ```rust // this is how subtraction is implemented in hardware. // carry is opposite of x86's sbb out = lhs.wrapping_add(!rhs).wrapping_add(carry as u32); carry = lhs as u64 + !rhs as u64 + carry as u64 > u32::MAX as u64; ``` ---
**Author:** ![clarfonthey](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/clarfonthey/32/12413_2.png) [@clarfonthey](https://internals.rust-lang.org/u/clarfonthey)\ **Post date:** [October 26, 2024, 6:30pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/14 "2024-10-26T18:30:10Z")
Ugh, yikes. I guess that we're kind of stuck with the "borrowing" name, then. ---
**Author:** ![ais523](https://avatars.discourse-cdn.com/v4/letter/a/a183cd/32.png) [@ais523](https://internals.rust-lang.org/u/ais523)\ **Post date:** [February 23, 2025, 3:52pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/15 "2025-02-23T15:52:50Z")
"Add with carry" / "subtract with borrow" terminology isn't unique to the x86 line – the 6502 uses the same terminology (and the same mnemonics, ADC / SBB). So it seems reasonable to use it in the name of our helper methods. As mentioned above, however, processors do vary in how they represent a borrow produced by a subtraction. Usually, it's stored in the carry bit, but some processors (e.g. the 6502) use the convention of "0 = a borrow occurred, 1 = no borrow occurred" and for some (e.g. x86) it's the other way round, "0 = no borrow occurred, 1 = a borrow occurred". (The former set of processors, I think, are using a model in which a conceptual 1 bit is placed in the carry bit before doing the subtraction, and a borrow borrows from it and makes it 0. I think some even implement it like that in hardware, expressing, e.g., 8-bit `A - B` as `A + (0xFF^B) + 1`, which is mathematically equivalent to `A + 0x100 - B`, and then the 1 at the end can be replaced with an input carry bit; this allows the same circuit to be used for addition and subtraction.) This makes me think that with our current sense of results, maybe "overflow"-based terminology may be more intuitive (as long as we indicate that for subtraction, it refers to a negative overflow), as it isn't obvious what mental model of the operation a programmer will be using. I think carries from addition are consistent across processors, with 1 indicating a carry and 0 indicating no carry. ---
**Author:** ![ais523](https://avatars.discourse-cdn.com/v4/letter/a/a183cd/32.png) [@ais523](https://internals.rust-lang.org/u/ais523)\ **Post date:** [March 23, 2025, 7:27pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/16 "2025-03-23T19:27:57Z")
I've had more thoughts about this… The basic issue is that the carry flag conceptually isn't a boolean, but a 1-bit integer. When adding, the carry flag is conceptually an unsigned integer – either it adds 1 or it does nothing (i.e. adds 0), and 0 and 1 are the values of a 1-bit unsigned integer (a `u1`). However, when subtracting, the carry flag is conceptually a signed integer – either it adds -1 or it does nothing (i.e. adds 0), and 0 and -1 are the values of a 1-bit signed integer (an `i1`). The disconnect in conventions for borrowing that's seen among processors is because there isn't an obvious way to encode an `i1` into a boolean – either the smaller value becomes `false` and the larger value becomes `true` (allowing it to be used directly in arithmetic), or else the zero value becomes `false` and the nonzero value becomes `true` (matching the convention that `false` usually represents 0). I am not sure that it would make sense to block the stabilisation of bigint helper methods on `u1` and `i1` types being added to the language (although IIRC such types are actually scheduled to be added at some point). If we were willing to do that, though (e.g. if the arbitrary-width integers get stabilised quickly), I think the logical thing to do would be to use "carry" terminology throughout, but with a `u1` carry for additions and an `i1` carry for subtractions (reflecting the fact that a subtraction's carry is conceptually negative). ---
**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\ **Post date:** [September 14, 2026, 7:28pm UTC](https://internals.rust-lang.org/t/naming-bigint-helper-methods-bike-shedding/21688/17 "2026-09-14T19:28:44Z")
This topic was automatically closed 540 days after the last reply. New replies are no longer allowed.