Why Does My C Large Precision Addition Have Incorrect Carry Propagation?

Carry Propagation in Large Precision Math

In your C large precision class, you encounter an issue where adding 0xffffffff and 0x04 results in 0xffff0003 instead of the expected 0x0100000003. This issue arises due to incorrect carry propagation.

To understand the problem, let's examine the overflow situation when adding large numbers. When two unsigned bytes (or unsigned short in your code) are added and the result exceeds the maximum value (255), the carry flag is set to 1. This carry should propagate to the next byte, indicating that the result should be incremented by 1.

In your code, you correctly set the carry flag when the sum of two bytes overflows (255). However, the subsequent lines do not propagate the carry correctly. Here's the problematic code:

if (i < lhs.nbytes)
{
    if (ret.data[i].data == 255 && ret.data[i + 1].carry == 1) increment(&trhs, i + 1);
    ret.data[i].data += ret.data[i + 1].carry;
}

Issue 1:

The increment(&trhs, i 1) statement only increments trhs[i 1] when ret.data[i].data == 255 and ret.data[i 1].carry == 1. However, carry propagation should occur regardless of the value of ret.data[i].data.

Issue 2:

The ret.data[i].data = ret.data[i 1].carry statement adds the carry to ret.data[i].data, but this is incorrect. The carry should be added to the result before storing it in ret.data[i].data.

Solution:

To fix the carry propagation, make the following changes:

if (i < lhs.nbytes)
{
    ret.data[i].data += ret.data[i + 1].carry;
    if (ret.data[i].data > 255)
    {
        increment(&trhs, i + 1);
        ret.data[i].data -= 256; // Subtract 256 to adjust for overflow
    }
}

These changes ensure that the carry is always propagated correctly. When the sum of two bytes exceeds 255, it subtracts 256 from the ret.data[i].data to adjust for overflow.

The above is the detailed content of Why Does My C Large Precision Addition Have Incorrect Carry Propagation?. For more information, please follow other related articles on the PHP Chinese website!