Naming `bigint_helper_methods` (bike-shedding)

Context

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 :frowning:

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.

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.

7 Likes

I'll also mention this comment, 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 without the possibility of overflow.)

So we need a name that works with something like mul_add_with_carry too.

3 Likes

how about mul_add_add?

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.

5 Likes

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.)

2 Likes

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.

4 Likes

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.

3 Likes

There is also the option add_carry and sub_borrow.

1 Like

Another option, shorten with to w, so add_w_carry and sub_w_borrow.

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
3 Likes

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<T>)

The extending operation would have the following implementations for unsigned/signed characters:

fn extending_add_unsigned(lhs: u32, rhs: u32, carry: bool) -> (u32, Option<u32>) {
    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<i32>) {
    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.

1 Like

carrying_sub is ambiguous. for u32 arguments/output:

  • it could be like x86's sbb instruction which does:
    // 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:
    // 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;
    
5 Likes

Ugh, yikes. I guess that we're kind of stuck with the "borrowing" name, then.

2 Likes