用int值将两个数组相乘

suppose I have n1 and n2 I want to multiply them for example I have array

假设有n1和n2我想把它们相乘比如有数组

n1={1,2,3};

and in

而在

n2={5,6}   

they are two integers in n1 we have the 123 and in n2 56

它们是n1的两个整数123和n2的56

123*56=6888

then in result I should have

那么结果我应该

result = {6,8,8,8}    

here is the incomplete algorithm which I thought

这是我认为不完整的算法

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

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

我怎么写呢?我不知道在完成内部循环后存储的位置我应该在数组中存储num然后再计算…我该怎么写?我在这里搜索了整个溢出，但是没有在c代码中找到它。

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

我们的目标是计算大数字整数有8个字节，换句话说64位，这样它们就可以存储2pow64-1也就是19位，这将有助于计算比19位大得多的数字

7 个解决方案

#1

It would be slightly easier if your digit-arrays were little-endian. Then your example multiplication would look

如果您的digit数组是little-endian，则会稍微简单一些。然后你的例子乘法会是这样的

 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
============

The product of n1[i] and n2[j] would contribute to result[i+j]. The main loop could roughly look like

n1[i]和n2[j]的乘积对结果[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

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.

您可以看到，结果必须至少为(l1-1) + (l2-1) + 1长，因为最重要数字的乘积是int结果[(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位有贡献。

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

Edit: added 0-terminators

编辑:添加0-terminators

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.

注意:这些不是空终止(未签名的)char数组，因此我们需要保留长度信息(这是很好的做法)，因此最好将这些信息与结构中的数字数组一起存储。而且，正如写的那样，它只适用于正数。如果您只有原始数组，那么处理负数就会很尴尬，所以这是存储其他信息的另一个要点。

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.

将数字保持为“0”+值对计算来说是没有意义的，它只对打印很方便，但只有在它们是空终止的数组时才会这样。那么，您可能想要为空终止符添加一个插槽。在这种情况下，我们存储产品长度的参数rl并不是必须的。

#2

Definitely an interesting problem.

肯定是一个有趣的问题。

Here was my thought:

这是我的想法:

• For the given array, append each value to the end of a string. Thus you construct a string of the numbers in order. {1,2,3} = "123"
• 对于给定的数组，将每个值附加到字符串的末尾。因此，您可以按顺序构造一个数字串。{ 1,2,3 } = " 123 "
• Then, you use a "ToInteger" method that you can find in one of the C libraries. Now you have your number to multiply with.
• 然后，使用“ToInteger”方法，您可以在C库中找到它。现在你有你的数字乘以。

With this logic, you can probably look up how the "ToInteger" or "ToString" methods work with numbers, which would lead to an answer.

有了这个逻辑，您可能会查找“ToInteger”或“ToString”方法如何处理数字，这将导致一个答案。

#3

Think how you would do it on paper, since you are simulating multiplying two decimal numbers. For starters, I think you'd go from least significant to most significant digit, so you'd be counting down the indexes (2, 1, 0 for the larger array; 1, 0 for the smaller). Also, you'd somehow have to arrange that when you multiply by n2[0] (the 5 in 56), you start adding at the tens place, not the units.

想想如何在纸上做，因为你模拟的是两个十进制数。首先，我认为你会从最不重要的数字变成最重要的数字，所以你会对索引进行计数(对于较大的数组来说是2,1,0;小的是1 0)同时，你也需要安排，当你乘以n2[0](56的5)，你开始在十位上加，而不是单位。

#4

You won't find complete C code for your problem at SO. Your first approach isn't that bad. You could do the following:

你找不到完整的C代码来解决你的问题。你的第一个方法不是那么糟糕。你可以这样做:

1. Multiply n1 and n2, conversion is done by mulitplication and addition, i. e. a{1,2,3} -> 1*100 + 2*10 + 3*1, easy to implement
2. 将n1和n2相乘，通过多重化和加法进行转换，即a{1,2,3} -> 1*100 + 2*10 + 3*1，易于实现
3. Count the digits of your multiplication result (use division inside a loop)
4. 计算乘法结果的位数(在循环中使用除法)
5. While looping through the digits you can store them back into another array
6. 在对数字进行循环时，可以将它们存储回另一个数组中

If you can't or if you don't want to deal with dynamic array allocation, then think about how big your array for storage must be beforehand and perform a static allocation.

如果您不能或不想处理动态数组分配，那么请考虑您的数组在存储前必须有多大，并执行静态分配。

Edit

编辑

Based on the discussion another approach:

在讨论的基础上，另一种方法:

Suppose, that r = n1 * n2

假设r = n1 * n2

1. Create a n*m 2D array, where
   • n = number of digits in n2
   • n = n2中的位数
   • m = number of digits in n1 + 1
   • m = n1 + 1中的位数
2. 创建一个n*m 2D数组，其中n = n2 m中的位数= n1 + 1中的位数
3. Within a loop multiply each digit of n1 with one of the elements of n2, store the result in the array, store the result per-digit in the 2D-array, don't forget to add the carry to each digit
4. 在一个循环中，将n1的每个数字与n2的一个元素相乘，将结果存储在数组中，将结果存储在2d数组中，不要忘记为每个数字添加进位
5. Repeat 2 with all other digits of n2
6. 用n2的所有其他数字重复2次
7. Now the array is filled and you'll have to add each digits like you would do it on paper, store each result within a target array, take care of the carry again
8. 现在数组已经被填满了，你需要像在纸上那样添加每个数字，将每个结果存储在一个目标数组中，再次处理进位

There is one thing left in the algorithm: Determine the size of the target array, based on the informations within the intermediate array, you can think about this by using pencil and paper ;)

算法中还剩下一件事:根据中间数组中的信息确定目标数组的大小，你可以用铅笔和纸来考虑;

#5

This code isn't optimized, nor does it account for generic lengths of arrays/numbers, but it should give you the general idea of how to implement the algorithm:

这段代码没有优化，也没有说明数组/数字的一般长度，但它应该让您大致了解如何实现该算法:

(This is similar to string-to-int or int-to-string algorithms, just add the ASCII offset to each item of the array and you have it.)

(这类似于字符串到int或intto -string算法，只需将ASCII偏移量添加到数组的每一项中，就可以得到它。)

#include <stdio.h>
#include <stdint.h>

#define N1_N  3
#define N2_N  2
#define MAX_N 4 /* maximum array length allowed */

void     print_array     (const uint8_t* array, size_t size);
uint32_t array_to_ulong  (const uint8_t* array, size_t size);
size_t   ulong_to_array  (uint8_t*       array, size_t size, uint32_t val);

int main()
{
  uint8_t  n1[N1_N] = {1,2,3};
  uint8_t  n2[N2_N] = {5,6};
  uint8_t  n3[MAX_N];
  size_t   n3_size = MAX_N;
  uint32_t n1_int;
  uint32_t n2_int;
  uint32_t result;


  print_array(n1, N1_N);
  printf(" * ");
  print_array(n2, N2_N);

  n1_int = array_to_ulong (n1, N1_N);
  n2_int = array_to_ulong (n2, N2_N);

  result = n1_int * n2_int;
  printf(" = %d = ", result);

  n3_size = ulong_to_array (n3, n3_size, result);
  print_array(n3, n3_size);

  getchar();

  return 0;
}

void print_array (const uint8_t* array, size_t size)
{
  size_t i;

  printf("{");
  for(i=0; i<size; i++)
  {
    printf("%d", array[i]);
    if(i != size-1)
    {
      printf(", ");
    }
  }

  printf("}");
}

uint32_t array_to_ulong (const uint8_t* array, size_t size)
{
  uint32_t result = 0;
  uint32_t multiplier = 1;
  size_t   i;

  for(i=1; i<=size; i++)
  {
    result += array[size-i] * multiplier;
    multiplier *= 10;
  }


  return result;
}

size_t ulong_to_array (uint8_t* array, size_t size, uint32_t val)
{
  size_t i;

  for(i=1; i<=size && val!=0; i++)
  {
    array[size-i] = val % 10;
    val /= 10;
  }

  return i-1;
}

#6

12345 * 6789 is: 12345 * 6 * 1000 + 12345 * 7 * 100 + 12345 * 8 * 10 + 12345 * 9 * 1

12345 * 6789为:12345 * 6 * 1000 + 12345 * 7 * 100 + 12345 * 8 * 10 + 12345 * 9 * 1

and that is: 1 * 6*1000 * 10000 + 2 * 6*1000 * 1000 + 3 * 6*1000 * 100 + 4 * 6*1000 * 10 + 5 * 6*1000 * 1 + 1 * 7*100 * 10000 + 2 * 7*100 * 1000 + 3 * 7*100 * 100 + 4 * 7*100 * 10 + 5 * 7*100 * 1 + 1 * 8*10 * 10000 + 2 * 8*10 * 1000 + 3 * 8*10 * 100 + 4 * 8*10 * 10 + 5 * 8*10 * 1 + 1 * 9*1 * 10000 + 2 * 9*1 * 1000 + 3 * 9*1 * 100 + 4 * 9*1 * 10 + 5 * 9*1 * 1

这就是:1 * 6 * 1000 * 10000 + 2 * 6 * 1000 * 1000 + 3 * 6 * 1000 * 100 + 4 * 6 * 1000 * 10 + 5 * 6 * 1000 * 1 + 1 * 7 * 100 * 10000 + 2 * 7 * 100 * 1000 + 3 * 7 * 100 * 100 + 4 * 7 * 100 * 10 + 5 * 7 * 100 * 1 + 1 * 8 * 10 * 10000 + 2 * 8 * 10 * 1000 + 3 * 8 * 10 * 100 + 4 * 8 * 10 * 10 + 5 * 8 * 10 * 1 + 1 * 9 * 1 * 10000 + 2 * 9 * 1 * 1000 + 3 * 9 * 1 * 100 + 4 * 9 * 1 * 10 + 5 * 9 * 1 * 1

so the algorith is multiply each value by each value and add (cumulate) it to the appropriate result array element (1000 is 10^3 so array element 3 (array starting by zero)).

所以algorith每个值乘以每个值和(累积)添加到适当的结果数组元素(1000是10 ^ 3所以数组元素3(零)数组开始)。

then move thru the result array and shift for results bigger than 10 the div by ten to the left (starting by the far right)

然后通过结果数组移动，并将结果向左移动10个div(从最右边开始)

#7

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000

char * multiply(char [],char[]);
int main(){
    char a[MAX];
    char b[MAX];
    char *c;
    int la,lb;
    int i;
    printf("Enter the first number : ");
    scanf("%s",a);
    printf("Enter the second number : ");
    scanf("%s",b);
    printf("Multiplication of two numbers : ");
    c = multiply(a,b);
    printf("%s",c);
    return 0;
}

char * multiply(char a[],char b[]){
    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la,lb;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    la=strlen(a)-1;
        lb=strlen(b)-1;

        for(i=0;i<=la;i++){
                a[i] = a[i] - 48;
        }

        for(i=0;i<=lb;i++){
                b[i] = b[i] - 48;
        }

    for(i=lb;i>=0;i--){
         r=0;
         for(j=la;j>=0;j--){
             temp[k++] = (b[i]*a[j] + r)%10;
             r = (b[i]*a[j]+r)/10;
         }
         temp[k++] = r;
         x++;
         for(y = 0;y<x;y++){
             temp[k++] = 0;
         }
    }

    k=0;
    r=0;
    for(i=0;i<la+lb+2;i++){
         sum =0;
         y=0;
         for(j=1;j<=lb+1;j++){
             if(i <= la+j){
                 sum = sum + temp[y+i];
             }
             y += j + la + 1;
         }
         c[k++] = (sum+r) %10;
         r = (sum+r)/10;
    }
    c[k] = r;
    j=0;
    for(i=k-1;i>=0;i--){
         mul[j++]=c[i] + 48;
    }
    mul[j]='\0';
    return mul;
}