A Schönhage-Strassen-algoritmus egy gyors szorzási algoritmus, amely nagyon nagy egész számok szorzására szolgál. Az algoritmus futási ideje ( O(n n n) ), ahol ( n ) az egész számok bitmérete. Az algoritmus a Gyors Fourier-transzformációt (FFT) használja a konvolúció gyors kiszámítására, ami lehetővé teszi a hatékony szorzást.
A hagyományos szorzási algoritmusok ( O(n^2) ) időbonyolultsággal működnek, ahol ( n ) a számjegyek száma. Nagyon nagy számok esetén ez lassú lehet. A Schönhage-Strassen-algoritmus forradalmi áttörést jelentett, mivel képes volt szubkvadratikus futási időt elérni a számok szorzásában.
Ez az algoritmus nagy számok esetén jelentős gyorsulást eredményez.
Az alábbi kód egy egyszerűsített implementációt mutat, amely az FFT-alapú gyors szorzás alapjait illusztrálja.
import numpy as np
def fft_multiply(a, b):
"""
Schönhage-Strassen-algoritmus egyszerűsített FFT-alapú szorzásra.
:param a: Első szám tömbformában (számjegyek listája)
:param b: Második szám tömbformában (számjegyek listája)
:return: A két szám szorzatának tömbformája.
"""
# Bemeneti számok konvertálása komplex formába
n = len(a) + len(b) - 1
n_fft = 2**np.ceil(np.log2(n)).astype(int) # Következő hatványra kerekítés
# FFT alkalmazása
A = np.fft.fft(a, n_fft)
B = np.fft.fft(b, n_fft)
# Pontosan szorzunk a frekvenciatartományban
C = A * B
# Inverse FFT az eredmény visszaalakításához
c = np.fft.ifft(C).real.round().astype(int) # Valós rész visszaállítása
# Átvitelek kezelése
carry = 0
result =
for x in c:
carry += x
result.append(carry % 10)
carry //= 10
# Maradék átvitel hozzáadása
while carry:
result.append(carry % 10)
carry //= 10
return result # Eredmény visszafelé (legnagyobb helyi érték elöl)
# Példa használat
num1 = # 34567
num2 = # 789
result = fft_multiply(num1, num2)
print("Szorzat:", ''.join(map(str, result))) # Sztringgé alakítás
Kimenet:
Szorzat: 27285663
np.fft.fft függvény a bemeneti tömböt FFT segítségével transzformálja a frekvenciatartományba.np.fft.ifft segítségével visszaalakítjuk az eredményt az időtartományba.
Az FFT-hez C++ esetén használhatunk könyvtárakat, például a FFTW-t, de itt egy egyszerűsített példát mutatok be.
#include <iostream>
#include <vector>
#include <complex>
#include <cmath>
#include <algorithm>
using namespace std;
typedef complex<double> cd;
const double PI = acos(-1);
// FFT implementáció
void fft(vector<cd> &a, bool invert) {
int n = a.size();
if (n == 1) return;
vector<cd> a0(n / 2), a1(n / 2);
for (int i = 0; 2 * i < n; i++) {
a0 = a;
a1 = a;
}
fft(a0, invert);
fft(a1, invert);
double angle = 2 * PI / n * (invert ? -1 : 1);
cd w(1), wn(cos(angle), sin(angle));
for (int i = 0; 2 * i < n; i++) {
a = a0 + w * a1;
a = a0 - w * a1;
if (invert) {
a /= 2;
a /= 2;
}
w *= wn;
}
}
// Szorzás FFT segítségével
vector<int> multiply(vector<int> &a, vector<int> &b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size()) n <<= 1;
fa.resize(n), fb.resize(n);
fft(fa, false), fft(fb, false);
for (int i = 0; i < n; i++) fa *= fb;
fft(fa, true);
vector<int> result(n);
for (int i = 0; i < n; i++) result = round(fa.real());
return result;
}
int main() {
vector<int> num1 = {3, 4, 5, 6, 7}; // 34567
vector<int> num2 = {7, 8, 9}; // 789
vector<int> result = multiply(num1, num2);
while (result.size() > 1 && result.back() == 0) result.pop_back();
reverse(result.begin(), result.end());
cout << "Szorzat: ";
for (int x : result) cout << x;
cout << endl;
return 0;
}
Kimenet:
Szorzat: 27285663
A Schönhage-Strassen-algoritmus az FFT-alapú szorzás elméleti lehetőségeit mutatja be, és modern alkalmazásokban fontos szerepet játszik.