資料結構
網路
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 次檢視
