有没有办法让这个功能更快？（C）

Question

我在 C 中有一个代码，它以与人类相同的方式进行加法，因此，例如，如果我有两个数组A[0..n-1]and B[0..n-1]，则该方法将执行C[0]=A[0]+B[0]，C[1]=A[1]+B[1]...

我需要帮助使这个函数更快，即使解决方案使用的是内在函数。

我的主要问题是我有一个非常大的依赖问题，因为迭代i+1取决于迭代的进位i，只要我使用基数 10。所以如果A[0]=6和B[0]=5，C[0]必须是1并且我有1下一个加法的进位。

我能做的更快的代码是这样的：

void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2,
                      unsigned char *Vout, unsigned N) {
    for (int i = 0; i < N; i++) {
        Vout[i] = Vin1[i] + Vin2[i];
    } 

    unsigned char carry = 0;

    for (int i = 0; i < N; i++) {
        Vout[i] += carry;
        carry = Vout[i] / 10;
        Vout[i] = Vout[i] % 10;
    }
}

但我也尝试了这些方法，结果证明速度较慢：

void LongNumAddition1(unsigned char *Vin1, unsigned char *Vin2,
                      unsigned char *Vout, unsigned N) {
    unsigned char CARRY = 0;
    for (int i = 0; i < N; i++) {
        unsigned char R = Vin1[i] + Vin2[i] + CARRY;
        Vout[i] = R % 10; CARRY = R / 10;
    }
}

void LongNumAddition1(char *Vin1, char *Vin2, char *Vout, unsigned N) {
    char CARRY = 0;
    for (int i = 0; i < N; i++) {
        char R = Vin1[i] + Vin2[i] + CARRY;
        if (R <= 9) {
            Vout[i] = R;
            CARRY = 0;
        } else {
            Vout[i] = R - 10;
            CARRY = 1;
        }
    }
}

我一直在 google 上进行研究，发现了一些与我实现的类似的伪代码，也在 GeeksforGeeks 内部，这个问题有另一个实现，但它也更慢。

你能帮我么？

Answer 1

如果不想改变数据的格式，可以试试SIMD。

typedef uint8_t u8x16 __attribute__((vector_size(16)));

void add_digits(uint8_t *const lhs, uint8_t *const rhs, uint8_t *out, size_t n) {
    uint8_t carry = 0;
    for (size_t i = 0; i + 15 < n; i += 16) {
        u8x16 digits = *(u8x16 *)&lhs[i] + *(u8x16 *)&rhs[i] + (u8x16){carry};

        // Get carries and almost-carries
        u8x16 carries = digits >= 10; // true is -1
        u8x16 full = digits == 9;

        // Shift carries
        carry = carries[15] & 1;
        __uint128_t carries_i = ((__uint128_t)carries) << 8;
        carry |= __builtin_add_overflow((__uint128_t)full, carries_i, &carries_i);

        // Add to carry chains and wrap
        digits += (((u8x16)carries_i) ^ full) & 1;
        // faster: digits = (u8x16)_mm_min_epu8((__m128i)digits, (__m128i)(digits - 10));
        digits -= (digits >= 10) & 10;

        *(u8x16 *)&out[i] = digits;
    }
}

这是每位数约 2 条指令。您需要添加代码来处理尾端。

这是算法的运行。

首先，我们将数字与上次迭代的进位相加：

lhs           7   3   5   9   9   2
rhs           2   4   4   9   9   7
carry                             1
         + -------------------------
digits        9   7   9  18  18  10

我们计算哪些数字会产生进位 (?10)，哪些数字会传播它们 (=9)。无论出于何种原因，使用 SIMD 时 true 为 -1。

carries       0   0   0  -1  -1  -1
full         -1   0  -1   0   0   0

我们转换carries为整数并将其移位，也转换full为整数。

              _   _   _   _   _   _
carries_i  000000001111111111110000
full       111100001111000000000000

现在我们可以将这些加在一起来传播进位。请注意，只有最低位是正确的。

              _   _   _   _   _   _
carries_i  111100011110111111110000
(relevant) ___1___1___0___1___1___0

有两个指标需要注意：

1. carries_i设置了最低位，并且digit ? 9. 有一个进场进入这个广场。

2. carries_i其最低位未设置，并且digit = 9. 已经有一个进过这个广场，重置位。

我们用 计算它(((u8x16)carries_i) ^ full) & 1，然后添加到digits。

(c^f) & 1     0   1   1   1   1   0
digits        9   7   9  18  18  10
         + -------------------------
digits        9   8  10  19  19  10

然后我们移除 10s，它们已经全部被携带了。

digits        9   8  10  19  19  10
(d?10)&10     0   0  10  10  10  10
         - -------------------------
digits        9   8   0   9   9   0

我们还跟踪执行，这可能发生在两个地方。