乘两个数组为int值 [英] multiply two arrays with int values
问题描述
假设我有 N1 和 N2 我想将它们相乘
比如我有阵
suppose I have n1 and n2 I want to multiply them
for example I have array
n1={1,2,3};
和
n2={5,6}
他们是在两个整数N1 有一个 123 和 N2 56
123*56=6888
然后结果我应该有
then in result I should have
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 code找到它
How can I write it? I don't know the place of store after finishing the insider loop I should store num in array and then compute again and... How should I write it? I searched the whole of overflow here but I didn't find about it in c code
目标是计算大量的整数数字有 8个字节，换句话说，64位，使他们能够存储 2pow64-1 是 19位现在这将有助于计算超过19位。
The Goal is to Compute the Large numbers Integer Numbers has 8 Bytes,in other words 64 bits so they can store 2pow64-1 which is 19 digits now this will help to compute very larger than 19 digits
推荐答案
这将是，如果你的数字阵列是小端稍微容易些。然后你的榜样乘法看起来
It would be slightly easier if your digit-arrays were little-endian. Then your example multiplication would look
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] 将有助于结果[I + J] 。主循环大致可以看起来像
The product of n1[i] and n2[j] would contribute to result[i+j]. The main loop could roughly look like
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 结果[（L1-1）+（L2-1）] 。在另一方面， N1＆LT; 10 ^ L1 和 N2＆LT; 10 ^ 12 ，因此产品＆LT; 10 ^（L1 + L2），你需要最多 L1 + L2 数字。结果
但是，如果你正在使用字符工作（符号或无符号），这将很快溢出每个数字，因为（对 K＆LT; =分钟（ L1-1，L2-1）） K + 1 的两位数字产品（每个人都可以像81一样大）有助于数字<$ ç$ C> K 产品。
You see that the result must be at least (l1-1) + (l2-1) + 1 long, since the product of the most significant digits goes int result[(l1-1) + (l2-1)]. On the other hand, n1 < 10^l1 and n2 < 10^l2, so the product is < 10^(l1+l2) and you need at most l1+l2 digits.
But if you're working with char (signed or unsigned), that will quickly overflow in each digit, since (for k <= min(l1-1,l2-1)) k+1 products of two digits (each can be as large as 81) contribute to digit k of the product.
所以最好执行根据结果数字分组乘法，在一个更大的类型积累，并在写作的结果做数位进位传播。随着小尾数号
So it's better to perform the multiplication grouped according to the result digit, accumulating in a larger type, and doing carry propagation on writing the result digit. With little-endian numbers
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;
}
}
有关大端号，索引必须进行修改 - 你能明白这一点你自己，有希望 - 但原理是一样的。
For big-endian numbers, the indexing has to be modified - you can figure that out yourself, hopefully - but the principle remains the same.
事实上，结果不是用铅笔和纸跟踪指数后，很多不同的：
Indeed, the result isn't much different after tracking indices with pencil and paper:
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终结
added 0-terminators
请注意：这些都不是 NUL 封端的（无符号）字符阵列，所以我们必须保持长度信息（这是很好做的工作），因此这将是更好地共同存储的信息与一个结构数字数组。此外，由于写它仅适用于正数。与负数打交道是尴尬的，如果你只有原始的数组，所以另一点用于存储其他信息。
Note: these are not NUL-terminated (unsigned) char arrays, so we need to keep length information (that's good to do anyway), hence it would be better to store that info together with the digit array in a struct. Also, as written it only works for positive numbers. Dealing with negative numbers is awkward if you only have raw arrays, so another point for storing additional info.
保持位数为 0 +值不会使该计算意义上说，它是只用于打印方便，但只有当他们是 NUL 封端阵列。您可能需要增加一个插槽的 NUL 终止子即可。在这种情况下，参数 RL 其中我们存储产品的长度不是严格必要的。
Keeping the digits as '0' + value doesn't make sense for the computations, it is only convenient for printing, but that only if they were NUL-terminated arrays. You may want to add a slot for the NUL-terminator then. In that case, the parameter rl in which we store the length of the product is not strictly necessary.
这篇关于乘两个数组为int值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
