乘以最多20个30位数字

Question

我被赋予了一个任务,可以将多达20个数字乘以30个数字.我想出了一个算法,通过在具有二次复杂度的两个循环中输入两个数字的数字,将两个数字乘以30位数.(我认为接近30位数的最佳方法是将数字的数字存储在具有20个数字的2D整数数组中,并且每个数字中的每一个都有30个空闲插槽来填充这些插槽中的数字)结果将存储在30位数组.现在这里是我的问题和问题:

1. 如何一次乘以超过2位数的30位数？我应该使用哪种循环？我想出了如何只乘以2个30位数字.

2. 从你的用户那里得到你想要数字的数字是另一个问题,比如在获取数字时你必须知道这些数字中的每一个都有最多30个数字来填充,如果我想从用户那里得到数字52我不要输入52和28之后的零,就像52本身一样:

输入:520000000000000000000000000000错误

输入:52是正确的,如果我们没有在52本身之后输入28个零.

这是我的算法将2个数字乘以30位数:

for (i = 29; i >= 0; i--)
 {
    for (j = 29, carry_in = 0; j >= 0; j--) 
    {
        n =number_1[i] * number_2[j] + result[i] + carry_in;
        carry_in = n / 10;
        result[i] = (n % 10);
    }
    result[i] += carry_in;
 }

Answer 1

您应该实现Karatsuba算法.您应该将函数编写为a int* multiply(int* a, int* b),将累加变量初始化main为20个数字之一,然后multiply在累积变量和剩余的19个数字之间循环.

另一方面,您的结果上限为600位,这相对较小,实际上Karatsuba将与所有已知(基于FFT)的乘法算法一样快,具有更好的渐近时间复杂度.如果你有一个非常大的数字(> 10 ^ 4位数),我会使用Schönhage-Strassen或其衍生产品,如Fürer.