极客笔记Java 实现Schonhage-Strassen乘法算法来计算两个数的乘积
当我们需要乘以大的小数时，Schonhage-Strassen算法非常有用。由于Java支持1018位整数大小，如果我们需要乘以超过1018位的数字，我们需要使用Schonhage-Strassen算法，因为它是最快的乘法算法之一。
它使用两个数字的基本乘法规则。它首先执行线性卷积，然后进行进位以获得最终结果。
问题陈述 - 我们已经给出了mul1和mul2两个大的十进制数，并且需要实现Schonhage-Strassen算法来计算两个数的乘积。
示例
输入
mul1 = 320; = 760;
输出
243200
描述 - 它已经乘以了这两个数字。
输入
mul1 = 32012233; = 76031232;
输出
1612188928
解释 - 它对两个大的十进制数进行了乘法运算。
方法1
在这种方法中，我们首先编写一个函数来计算线性卷积。然后，我们将以这样的方式添加所有线性卷积的结果值，以便我们可以前置进位添加到下一个元素中。
这里，我们解释了一种用于编写Schonhage-Strassen算法的Java代码的逐步算法。
算法
步骤1 - 执行perfromMultiplication()函数。在该函数中，首先执行getLinConvolution()函数。
步骤2 - 在getLinConvolution()函数中，使用findTotalDigits()函数计算给定数字的总位数。
步骤2.1 - 在findTotalDigits()函数中，将’cnt’初始化为零以存储数字的总位数。
步骤2.2 - 在num_int大于零之前进行迭代。
步骤2.3 - 在循环中，将num_int除以10。还要增加cnt的值1。
步骤2.4 - 最后，返回’cnt’的值。
步骤3 - 定义’tmp_mul1’并存储mul1数的值。还定义lcon_len变量以存储我们需要使用的数组的长度，以存储线性卷积。
步骤4 - 开始遍历mul2的数字。在循环中，将tmp_mul1的值存储到mul1，然后使用另一个嵌套循环来遍历mul1的数字。
步骤5 - 通过将(mul2 % 10) * (mul1 % 10)添加到当前值，更新数组中的(p + q)索引处的值。
步骤6 - 现在，我们有了线性卷积，需要对列表进行进位操作。因此，调用addCarry()函数。
步骤7 - 初始化用于存储乘积、进位和基数的变量。
步骤8 - 开始遍历列表。将’C’添加到列表中第i个索引值中。
步骤9 - 在’predocut_res’中添加B * (linConvoList[i] % 10)，其中B是基数值。
步骤10 - 将linConvoList除以10，并使用它更新’C’的值。
步骤11 - 将基数乘以10。
步骤12 - 完成所有循环迭代后，将C*B添加到乘积结果中，以将最终进位添加到列表中。最后，打印出两个十进制数的乘积结果。
示例
import java.io.*;
public class Main {
// for storing the LinearConvolution
static int[] linConvoList;
// to store length of the LinearConvolution
static int lcon_len;
// function to count total digits in given number
static int findTotalDigits(long num_int) {
// Initial digits
int cnt = 0;
// Make iterations until num_int is greater than zero
while (num_int > 0) {
num_int /= 10;
cnt++;
}
// return cnt value
return cnt;
}
static void getLinConvolution(long mul1, long mul2) {
// count digits in mul1
int mul1Digits = findTotalDigits(mul1);
// count digits in mul2
int mul2Digits = findTotalDigits(mul2);
// to store temporary value of mul1
long tmp_mul1 = mul1;
// Initialize the length of the linear convolution
lcon_len = mul1Digits + mul2Digits - 1;
// Initialize the list
linConvoList = new int[lcon_len];
// Filling the linConvoList array
for (int p = 0; p < mul2Digits; p++, mul2 /= 10) {
// Reset the value of mul1 for each iteration of mul2
mul1 = tmp_mul1;
for (int q = 0; q < mul1Digits; q++, mul1 /= 10) {
// multiply digit of mul1 and mul2
linConvoList[p + q] += (int) ((mul2 % 10) * (mul1 % 10));
}
}
System.out.print("The values stored in the linear convolution array are: ");
for (int p = lcon_len - 1; p >= 0; p--) {
System.out.print(linConvoList[p] + " ");
}
System.out.println();
}
static void addCarry() {
// initialize product to 0
long product_res = 0;
// Initialize variables for carry and base
int C = 0, B = 1;
// Traverse the list
for (int i = 0; i < lcon_len; i++) {
linConvoList[i] += C;
// performing operations
product_res = product_res + (B * (linConvoList[i] % 10));
// Divide the linConvoList[i] by 10 to get carry
C = linConvoList[i] / 10;
// Multiply the base by 10
B *= 10;
}
// Add the final carry if it exists
product_res += C * B;
System.out.println("\nThe Product of mul1 and mul2 is: " + product_res+ "\n");
}
// Multiplication starts here
static void performMultiplication(long mul1, long mul2) {
// To get the LinearConvolution
getLinConvolution(mul1, mul2);
// Add carry to the LinearConvolution
addCarry();
}
// Driver method
public static void main(String[] args) {
long mul1, mul2;
// long numbers to multiply
mul1 = 320;
mul2 = 760;
performMultiplication(mul1, mul2);
}
}
输出
The values stored in the linear convolution array are: 21 32 12 0 0
The Product of mul1 and mul2 is: 243200
时间复杂度： - O(M + N)，其中M是mul1中总数字数，N是mul2中总数字数。
空间复杂度： - O(M + N)，因为需要存储线性卷积。
在代码中，程序员可以观察到Schonhage-Strassen算法与我们在数学中所做的普通乘法相同。程序员可以观察线性卷积的结果来理解算法。
此外，程序员应该尝试编写算法来对两个大数进行求和，以进行更多的练习。