数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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.3 - 最后，返回'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添加到乘积结果中，以将最终进位添加到列表中。最后，打印product_res，它是两个十进制数的乘积。
示例
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算法的工作原理与我们在数学中进行的普通乘法相同。程序员可以观察线性卷积的结果来理解算法。
此外，程序员应该尝试编写算法来对两个大数求和，以进行更多练习。
151 次查看
