将两个数组与 int 值相乘

Question

假设我有n1并且n2我想将它们相乘，例如我有数组

n1={1,2,3};

并在

n2={5,6}   

它们是两个整数，n1我们有123和n2 56

123*56=6888

那么结果我应该有

result = {6,8,8,8}    

这是我认为不完整的算法

for(i in n1 bigger array)
    for(j in n2 smaller one)
    {
        mult=n1[i]*n2[j]
        mult+= carry;

        if(mult>=10)
        {
            carry = (mult/10);
            mult-= (carry*10);
        }
    }
}

我该如何写呢？完成内部循环后我不知道存储位置我应该将 num 存储在数组中然后再次计算......我应该如何写它？我在这里搜索了整个溢出，但没有在c代码中找到它

目标是计算整数所具有的大数，8 Bytes,in other words 64 bits以便它们可以存储2pow64-1，19 digits现在这将有助于计算大于 19 位的数字

Answer 1

如果您的数字数组是小端字节序，那么会稍微容易一些。那么你的乘法示例将如下所示

 3  2  1 * 6 5
---------------
18 12  6
   15 10  5
---------------
18 27 16  5    // now propagate carries
 8 28 16  5
 8  8 18  5
 8  8  8  6
============

的乘积n1[i]和n2[j]将有助于result[i+j]. 主循环大致如下

for (i = 0; i < l1; ++i) // l1 is length of n1
{
    for (j = 0; j < l2; ++j) // l2 is length of n2
    {
        result[i+j] += n1[i]*n2[j];
    }
}
// now carry propagation

您会看到结果必须至少(l1-1) + (l2-1) + 1很长，因为最高有效数字的乘积为 int result[(l1-1) + (l2-1)]。另一方面，n1 < 10^l1和n2 < 10^l2，所以乘积是< 10^(l1+l2)和 您最多需要l1+l2数字。
但是，如果您使用char（有符号或无符号），每个数字都会很快溢出，因为（对于k <= min(l1-1,l2-1)）k+1两位数字的乘积（每个数字可以大到 81）对k乘积的数字有贡献。

因此，最好根据结果数字分组执行乘法，以更大的类型累加，并在写入结果数字时进行进位传播。使用小端数字

char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl)
{
    // allocate and zero-initialise, may be one more digit than needed
    char *result = calloc(l1+l2+1,1);
    *rl = l1 + l2;
    size_t k, i, lim = l1+l2-1;
    for (k = 0; k < lim; ++k)
    {
        unsigned long accum = result[k];
        for (i = (k < l2) ? 0 : k-(l2-1); i <= k && i < l1; ++i)
        {
            accum += (n1[i] - '0') * (n2[k-i] - '0');
        }
        result[k] = accum % 10 + '0';
        accum /= 10;
        i = k+1;
        while(accum > 0)
        {
            result[i] += accum % 10;
            accum /= 10;
            ++i;
        }
    }
    if (result[l1+l2-1] == 0)
    {
        *rl -= 1;
        char *real_result = calloc(l1+l2,1);
        for (i = 0; i < l1+l2-1; ++i)
        {
            real_result[i] = result[i];
        }
        free(result);
        return real_result;
    }
    else
    {
        result[l1+l2-1] += '0';
        return result;
    }
}

对于大端数字，必须修改索引 - 希望您可以自己弄清楚 - 但原理保持不变。

事实上，用铅笔和纸跟踪指数后，结果并没有太大不同：

char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl)
{
    // allocate and zero-initialise, may be one more digit than needed
    // we need (l1+l2-1) or (l1+l2) digits for the product and a 0-terminator
    char *result = calloc(l1+l2+1,1);
    *rl = l1 + l2;
    size_t k, i, lim = l1+l2-1;
    // calculate the product from least significant digit to
    // most significant, least significant goes into result[l1+l2-1],
    // the digit result[0] can only be nonzero by carry propagation.
    for (k = lim; k > 0; --k)
    {
        unsigned long accum = result[k]; // start with carry
        for (i = (k < l2) ? 0 : k-l2; i < k && i < l1; ++i)
        {
            accum += (n1[i] - '0') * (n2[k-1-i] - '0');
        }
        result[k] = accum % 10 + '0';
        accum /= 10;
        i = k-1;
        while(accum > 0)
        {
            result[i] += accum % 10;
            accum /= 10;
            --i;
        }
    }
    if (result[0] == 0) // no carry in digit 0, we allocated too much
    {
        *rl -= 1;
        char *real_result = calloc(l1+l2,1);
        for (i = 0; i < l1+l2-1; ++i)
        {
            real_result[i] = result[i+1];
        }
        free(result);
        return real_result;
    }
    else
    {
        result[0] += '0'; // make it an ASCII digit
        return result;
    }
}

编辑：添加 0 终止符

注意：这些不是NUL以 - 结尾的(unsigned) char数组，因此我们需要保留长度信息（无论如何这都是好事），因此最好将该信息与数字数组一起存储在struct. 另外，正如所写，它仅适用于正数。如果您只有原始数组，则处理负数会很尴尬，因此存储附加信息的另一点。

保留数字'0' + value对于计算来说没有意义，它只方便打印，但前提是它们是NUL- 终止的数组。然后您可能需要为 - 终止符添加一个槽NUL。在这种情况下，我们存储产品长度的参数rl并不是绝对必要的。