Why Doesn't My C Large Precision Addition Propagate Carry Bits Correctly?

Can't make value propagate through carry

Your goal is to implement a large precision class in C , and you've encountered an issue when adding numbers together. When you add 0xffffffff and 0x04, you get 0xffff0003 instead of the expected 0x0100000003.

Source of the Issue

The highlighted section of your code is:

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;
}

Here's why it's causing the incorrect result:

Carry Propagation: In each iteration of the loop, the carry from the previous addition should be added to the current result. However, this code only applies the carry if ret.data[i].data is 255 and ret.data[i 1].carry is 1. This means that carries are not always propagated, which results in the incorrect answer.

Incorrect Storage Order: The mpfl class seems to store numbers in little-endian format, where the least significant byte is stored in the highest index. This is not the preferred way to store numbers for addition as it makes it harder to process carries from higher-order bytes.

Recommendations

To resolve these issues, consider the following recommendations:

1. Store numbers in big-endian format: Place the most significant byte in the lowest index. This makes carry propagation straightforward.
2. Propagate carries consistently: In the operator function, ensure that the carry from each addition is propagated to the next iteration, regardless of the values of ret.data[i].data and ret.data[i 1].carry.
3. Use a custom ALU (Arithmetic Logic Unit): Implement a lightweight ALU class that provides basic arithmetic operations, including addition and carry propagation. This approach can simplify your code and improve performance.
4. Review the full codebase: The provided code snippet is only a small part of the larger mpfl class. It's essential to review the entire implementation, particularly the sections responsible for carry handling and digit manipulation.

The above is the detailed content of Why Doesn't My C Large Precision Addition Propagate Carry Bits Correctly?. For more information, please follow other related articles on the PHP Chinese website!