使用字符串进行非常大的数字的乘法

Question

我正在尝试编写一个 C 程序，该程序在不直接使用乘法运算符的情况下执行两个数字的乘法，并且它应该考虑足够大的数字，以便即使这两个数字的通常加法也不能通过直接加法来执行。

当我尝试（并且成功地）编写一个使用字符串执行加法的 C 程序时，我受到了这一点的激励，我执行了以下操作：

#include<stdio.h>
#define N 100000
#include<string.h>
void pushelts(char X[], int n){
int i, j;
for (j = 0; j < n; j++){
    for (i = strlen(X); i >= 0; i--){
        X[i + 1] = X[i];
    }
        X[0] = '0'; 
    }
}

int max(int a, int b){
    if (a > b){ return a; }
    return b;
}

void main(){
    char E[N], F[N]; int C[N]; int i, j, a, b, c, d = 0, e;
    printf("Enter the first number: ");
    gets_s(E);
    printf("\nEnter the second number: ");
    gets_s(F);
    a = strlen(E); b = strlen(F); c = max(a, b);
    pushelts(E, c - a); pushelts(F, c - b);
    for (i = c - 1; i >= 0; i--){
        e = d + E[i] + F[i] - 2*'0';
        C[i] = e % 10; d = e / 10;
    }
    printf("\nThe answer is: ");
    for (i = 0; i < c; i++){
        printf("%d", C[i]);
    }
    getchar();
}

它可以将任意两个“N”位数字相加。现在，我将如何使用它来执行大数乘法？首先，我编写了一个函数，用于执行将作为字符串输入的数字与数字 n 的乘法（即 0 <= n <= 9）。很容易看出这样的函数是如何编写的；我将其称为（*）。现在的主要目的是将两个数字（作为字符串输入）相乘。我们可以将第二个 k 位数字（假设是 a1a2.....ak）视为：

a1a2...ak = a1 x 10^(k - 1) + a2 x 10^(k - 2) + ... + ak-1 x 10 + ak

因此，两个数字的乘法可以使用为加法设计的解决方案和函数（*）来实现。

如果第一个数字是 x1x2.....xn，第二个数字是 y1y2....yk，则：

x1x2...xn x y1y2...yk = (x1x2...xn) x y1 x 10^(k-1) + .....

现在函数 (*) 可以将 (x1x2...xn) 与 y1 相乘，乘以 10^(k-1) 只是在数字旁边添加 k-1 个零；最后我们将所有这 k 项相加以获得结果。但困难在于只知道每个数字包含多少位数字，以便每次在设计用于将它们加在一起的循环内执行加法。我曾考虑过做一个空数组，并每次将 (x1x2....xn) 乘以 yi x 10^(i-1) 所获得的结果添加到其中，但就像我说过的那样，我无法精确计算所需的边界，我不知道每次应该在每个获得的结果前面添加多少个零，以便使用上述算法将其添加到空数组中。当我必须进行多次从 char 类型到 int 类型的转换（反之亦然）时，就会出现更多困难。也许我把事情变得比应有的更复杂了；我不知道是否有更简单的方法来做到这一点，或者是否有我不知道的工具。我是编程初学者，除了基本工具之外我不知道更多。

有人可以提出解决方案、想法或算法吗？谢谢。

Answer 1

我在 SPOJ 上做小阶乘问题时开发了一个算法。

该算法基于小学乘法方法。在学生时代，我们通过将第一个数字的每个数字与第二个数字的最后一位数字相乘来学习两个数字的乘法。然后将第一个数字的每个数字与第二个数字的倒数第二个数字相乘，依此类推，如下所示：

               1234
               x 56
         ------------
               7404
             +6170-   // - is denoting the left shift    
         ------------
              69104  

实际发生了什么：

1. num1 = 1234，num2 = 56，左移 = 0；
2. char_array[] = num1 中的所有数字
3. 结果数组[]
4. 而（数字2）
   • n = num2%10
   • 数字2 /= 10
   • 进位 = 0，i = 左移，j = 0
   • while(char_array[j])
     i.
     ii.部分结果 = char_array[j]*n + 进位 部分结果 += 结果数组[i]
     iii. result_array[i++] =partial_result%10
     iv. 进位 = 部分结果/10
   • 左移++
5. result_array按相反顺序 打印。

num1您应该注意，如果且不num2超出其数据类型的范围，则上述算法有效。如果您想要更通用的程序，那么您必须读取char数组中的两个数字。逻辑将是相同的。将num1and声明num2为char数组。查看实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char num1[200], num2[200];
    char result_arr[400] = {'\0'};
    int left_shift = 0;

    fgets(num1, 200, stdin);
    fgets(num2, 200, stdin);

    size_t n1 = strlen(num1);
    size_t n2 = strlen(num2);   

    for(size_t i = n2-2; i >= 0; i--)
    {
        int carry = 0, k = left_shift;
        for(size_t j = n1-2; j >= 0; j--)
        {
            int partial_result = (num1[j] - '0')*(num2[i] - '0') + carry;
            if(result_arr[k])
                partial_result += result_arr[k] - '0';
            result_arr[k++] = partial_result%10 + '0';
            carry = partial_result/10;  
        }
        if(carry > 0)
            result_arr[k] = carry +'0'; 
        left_shift++;
    }
    //printf("%s\n", result_arr);

    size_t len = strlen(result_arr);
    for(size_t i = len-1; i >= 0; i-- )
        printf("%c", result_arr[i]);
    printf("\n");   
}

这不是标准算法，但我希望这会有所帮助。

Answer 2

您可以按如下所示重新使用字符串添加代码（使用 user300234 的 384 x 56 示例）：

Set result="0" /* using your character-string representation */
repeat:
    Set N = ones_digit_of_multiplier /* 6 in this case */
    for (i = 0; i < N; ++i)
      result += multiplicand  /* using your addition algorithm */
    Append "0" to multiplicand /* multiply it by 10 --> 3840 */
    Chop off the bottom digit of multiplier /* divide it by 10 --> 5 */
    Repeat if multiplier != 0.