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.
