VS C++中uint64_t数组实现128位乘法的进位错误排查

问题现象 #

在Visual Studio C++环境下，对小端格式存储于数组中的两个uint64_t数值执行128位乘法模拟时，结果出现两处进位传播错误：

0x0306f7b285eead7d8cc88407a9f4c002 * 0xf9084d7a11528273377bf8560b3ffe =

0x2f1e00eebe083ca406e838b64ae89188195f931cca21eaaa66062c82cfffc correct
# #
0x2f1e00eebe083ca406e838b64ae88188195f931cca21faaa66062c82cfffc my code

问题代码 #

#include <stdint.h>      // For uint64_t, uint8_t, ptrdiff_t
#include <stddef.h>      // For size_t, ptrdiff_t
#include <string.h>      // For memcpy, memset
#include <stdio.h>       // For printf
#include <intrin.h>      // For _umul128, _addcarry_u64

// Define uint128_t type using struct
typedef struct {
    uint64_t lo;
    uint64_t hi;
} uint128_t;

// Function to multiply two uint64_t numbers and get a uint128_t result
uint128_t multiply_uint64(uint64_t a, uint64_t b) {
    uint128_t result;
    result.lo = _umul128(a, b, &result.hi);
    return result;
}

size_t len = 2;
memset(result, 0, 2 * len * sizeof(uint64_t));
    for (size_t i = 0; i < len; ++i) {
        uint64_t carry = 0;
        for (size_t j = 0; j < len; ++j) {
            // Multiply x[i] and y[j]
            uint128_t product = multiply_uint64(x[i], y[j]);

            // Add product.lo to result[i + j] with carry
            uint8_t c1 = _addcarry_u64(0, product.lo, result[i + j], &result[i + j]);
            // Add carry from previous addition to result[i + j]
            uint8_t c2 = _addcarry_u64(c1, result[i + j], carry, &result[i + j]);

            // Update carry for next iteration
            uint64_t temp_carry = product.hi + c2;
            carry = temp_carry;
        }
        result[i + len] = carry;
    }

错误分析 #

代码的核心问题在于进位处理逻辑混乱，未正确处理大数乘法中的多步进位传递：

1. 内层循环加法顺序错误：将carry加到已经更新过的result[i+j]上，破坏了原本的累加逻辑。
2. 对product.hi与加法进位的处理仅做简单相加，未考虑该相加操作可能产生的新进位，导致高位进位丢失。

修复方案 #

调整内层循环的进位处理逻辑，确保每一步的累加和进位都正确传递到对应位置：

#include <stdint.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <intrin.h>

typedef struct {
    uint64_t lo;
    uint64_t hi;
} uint128_t;

uint128_t multiply_uint64(uint64_t a, uint64_t b) {
    uint128_t result;
    result.lo = _umul128(a, b, &result.hi);
    return result;
}

// 假设x、y是输入的小端数组，result是输出数组（需提前分配足够空间）
void big_multiply(uint64_t* x, uint64_t* y, uint64_t* result, size_t len) {
    memset(result, 0, 2 * len * sizeof(uint64_t));
    for (size_t i = 0; i < len; ++i) {
        uint64_t carry = 0;
        for (size_t j = 0; j < len; ++j) {
            uint128_t product = multiply_uint64(x[i], y[j]);
            
            // 第一步：累加product.lo到result[i+j]，带上一轮carry
            uint64_t sum_lo = result[i + j];
            uint8_t c = _addcarry_u64(0, sum_lo, product.lo, &sum_lo);
            c = _addcarry_u64(c, sum_lo, carry, &sum_lo);
            result[i + j] = sum_lo;
            
            // 第二步：累加product.hi和第一步的进位到result[i+j+1]，更新carry
            uint64_t sum_hi = result[i + j + 1];
            c = _addcarry_u64(0, sum_hi, product.hi, &sum_hi);
            c = _addcarry_u64(c, sum_hi, c, &sum_hi);
            result[i + j + 1] = sum_hi;
            carry = c;
        }
        // 处理当前i循环剩余的carry
        if (carry != 0) {
            result[i + len] += carry;
        }
    }
}

关键修复点 #

• 先将product.lo、当前result[i+j]和上一轮carry累加，得到新的result[i+j]和临时进位。
• 将product.hi与临时进位累加至result[i+j+1]，并将新产生的进位作为下一轮循环的carry。
• 确保所有进位都被传递到更高位，避免丢失。

验证 #

修改后重新运行测试用例，结果中的错误位将被修正，与正确结果完全一致。

内容的提问来源于stack exchange，提问作者Caster