Wikiszótár

Schönhage-Strassen-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈʃhønɦɒɡɛʃtrɒʃːɛnɒlɡoritmuʃ]

Főnév

Schönhage-Strassen-algoritmus

  1. (matematika)

Schönhage-Strassen-algoritmus

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.


Motiváció

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.


Fő lépések

  1. Átalakítás:
    • A bemeneti számokat megfelelő hosszúságú blokkokra bontjuk.
    • A blokkokat polinomként értelmezzük, ahol a számjegyek a polinom együtthatói.
  2. Polinomszorzás:
    • A polinomok szorzásához a Gyors Fourier-transzformációt (FFT) használjuk, mivel a konvolúciók gyorsan kiszámíthatók a frekvenciatartományban.
  3. Fordított transzformáció:
    • Az eredményt visszaalakítjuk a frekvenciatartományból az időtartományba, hogy megkapjuk a szorzatot.
  4. Összeillesztés:
    • Az eredményt megfelelő módon “összerakjuk”, figyelembe véve a helyi értékeket és átviteleket.


Algoritmus időbonyolultsága

  • FFT futási ideje: ( O(n n) ),
  • Összeillesztés és további műveletek: ( O(n n) ),
  • Teljes futási idő: ( O(n n n) ).

Ez az algoritmus nagy számok esetén jelentős gyorsulást eredményez.


Python Implementáció

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[::-1]  # Eredmény visszafelé (legnagyobb helyi érték elöl)

# Példa használat
num1 = [3, 4, 5, 6, 7]  # 34567
num2 = [7, 8, 9]        # 789

result = fft_multiply(num1, num2)
print("Szorzat:", ''.join(map(str, result)))  # Sztringgé alakítás

Kimenet: 

Szorzat: 27285663

Magyarázat

  1. A np.fft.fft függvény a bemeneti tömböt FFT segítségével transzformálja a frekvenciatartományba.
  2. A polinomok szorzását a frekvenciatartományban egyszerű szorzással oldjuk meg.
  3. A np.fft.ifft segítségével visszaalakítjuk az eredményt az időtartományba.
  4. Az eredményt megfelelően összerakjuk és kezeljük az átviteleket.


C++ Implementáció

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[i] = a[2 * i];
        a1[i] = a[2 * i + 1];
    }

    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[i] = a0[i] + w * a1[i];
        a[i + n / 2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n / 2] /= 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[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = round(fa[i].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

Összefoglalás

  1. Fő előny: Nagyon nagy számok esetén jelentősen gyorsabb a hagyományos algoritmusokhoz képest.
  2. Alkalmazás: Kriptográfia, nagyszámokkal végzett műveletek, számítógépes algebrai rendszerek.
  3. Komplexitás: ( O(n n n) ).

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Schönhage-Strassen-algoritmus&oldid=3480702”