Unsigned subtraction in C
I'm trying to implement multi-point unsigned subtraction over a finite field (p = 2 ^ 191-19) in C, but I can't figure out how to deal with the battle of borrowing! My operands are represented in radix-2 ^ 16 as:
typedef unsigned long long T[12];
which means that each element of a T-type array has exactly 16-bit data (radix-2 ^ 16 representation). Now I want to subtract two operands of type T, but I don't know which one is smaller! If the result is negative, I want to add the result to the first value in order to have positive results in modular arithmetic. Here is my implementation based on this book-30 page (Multiple Subtraction Algorithm):
void bigint192_sub(T r, const T a, const T b){
int i;
int borrow;
r[0] = a[0] - b[0];
borrow = r[0] >> 16;
r[0] &= 0xFFFF;
for(i=1;i<12;++i){
r[i] = a[i] - b[i] - borrow;
borrow = r[i] >> 16;
r[i] &= 0xFFFF;
}
}
but i got the wrong answer!
My inputs: a =0x2d7e33e5bba0f6bb87ce04b28e940662db8f3f81aaf94576 b =0x28afc585dca4a8003b081f7289de11c2d229d5a967081f72 Myresult=0x4d16e62defd4ebc4cc8e54104b7f4a0096769d843f12604 Crresult=0x4ce6e5fdefc4ebb4cc5e54004b5f4a0096569d843f12604
source to share
You must correct the estimate borrow
as it can only be 0
or 1
. Thus, you should treat underflow as borrow
equal 1
:
borrow = (r[i] >> 16) != 0;
Also, I would rewrite the function in a more general form, since we can treat the first pass as if we don't have a loan:
void bigint192_sub(T r, const T a, const T b){
int i;
int borrow;
for (borrow = 0, i = 0; i < 12; ++i) {
r[i] = a[i] - b[i] - borrow;
borrow = (r[i] >> 16) != 0;
r[i] &= 0xFFFF;
}
}
source to share