Große Dezimalzahlen mit der Fast-Fourier-Transformation (FFT) multiplizieren-js-Tutorial-php.cn

Multiplying Large Decimal Numbers Using Fast Fourier Transform (FFT)

Einführung

Das Multiplizieren großer Dezimalzahlen kann rechentechnisch eine Herausforderung sein, insbesondere wenn es um Zahlen mit vielen Ziffern oder mehreren Dezimalstellen geht. Herkömmliche Multiplikationsmethoden werden bei extrem großen Zahlen ineffizient. Hier kommt die schnelle Fourier-Transformation (FFT) zum Einsatz, die einen leistungsstarken und effizienten Algorithmus zum Multiplizieren großer Zahlen mit bemerkenswerter Geschwindigkeit bereitstellt.

Anwendung in der Multiplikation

FFT ermöglicht eine schnelle Multiplikation von Polynomen oder großen ganzen Zahlen, indem die Zahlen in den Frequenzbereich transformiert, eine punktweise Multiplikation durchgeführt und dann die inverse FFT angewendet wird.

Die Herausforderung der Multiplikation großer Zahlen

Herkömmliche Multiplikationsmethoden haben eine Zeitkomplexität von O(n²), wobei n die Anzahl der Ziffern ist. Bei sehr großen Zahlen wird dies rechenintensiv. Der FFT-basierte Multiplikationsalgorithmus reduziert diese Komplexität auf O(n log n), was sie bei großen Zahlen deutlich schneller macht.

Beweisübersicht für Cooley-Tukey-FFT

Zerlegung der Diskreten Fourier-Transformation (DFT):
- Die DFT ist definiert als:
  $X_{k} = \sum_{n = 0}^{N - 1} x_{n} \cdot e^{- 2 π i \cdot k n / N}, X_k = sum_{n=0}^{N-1} x_n cdot e^{-2pi i cdot kn / N},$ Xk = n=0∑N−1 xn⋅ e−2πi⋅kn /N,
  Wo $N N$ N ist die Größe des Eingangssignals.
- Die Cooley-Tukey-FFT unterteilt die Berechnung in kleinere DFTs der Größe $N / 2 N/2$ N/2 durch Trennung von Begriffen mit geradem Index und Begriffen mit ungeradem Index:
  $X_{k} = \sum_{n = 0}^{N / 2 - 1} x_{2 n} \cdot e^{- 2 π i \cdot (2 n) k / N} \sum_{n = 0}^{N / 2 - 1} x_{2 n 1} \cdot e^{- 2 π i \cdot (2 n 1) k / N} . X_k = sum_{n=0}^{N/2-1} x_{2n} cdot e^{-2pi i cdot (2n)k / N} sum_{n=0}^{N/2-1} x_{2n 1} cdot e^{-2pi i cdot (2n 1)k / N}.$ Xk = n=0∑N/2−1 x2n ⋅e −2πi⋅(2n)k/N n=0∑N/ 2−1x 2n 1⋅ e−2πi⋅(2n 1)k/N.
- Dies reduziert sich auf:
  $X_{k} = DFT gerader Terme W_{k} \cdot DFT ungerader Terme, X_k = text{DFT gerader Terme} W_k cdot text{DFT ungerader Terme},$ Xk =DFT von geraden Termen Wk⋅DFT ungerade Terme,
  Wo $W_{k} = e^{- 2 π i \cdot k / N} W_k = e^{-2pi i cdot k / N}$ Wk =e−2πi ⋅k/N .
Rekursive Struktur:
- Jede DFT der Größe $N N$ N wird in zwei DFTs der Größe aufgeteilt $N / 2 N/2$ N/2 , was zu einer rekursiven Struktur führt.
- Diese rekursive Division wird bis zum Basisfall der Größe fortgesetzt $N = 1 N = 1$ N=1 , an diesem Punkt ist die DFT einfach der Eingabewert.
Schmetterlingsoperationen:
- Der Algorithmus führt Ergebnisse kleinerer DFTs mithilfe der Butterfly-Operationen zusammen:
  $a^{'} = u W_{k} \cdot v, b^{'} = u - W_{k} \cdot v, a' = u W_k cdot v, quad b' = u - W_k cdot v,$ a′=u Wk⋅v,b′ =u−Wk⋅v,
  Wo $u u$ u Und $v v$ v sind Ergebnisse kleinerer DFTs und $W_{k} W_k$ Wk stellt die Wurzeln der Einheit dar.
Bit-Umkehr-Permutation:
- Das Eingabearray wird basierend auf der binären Darstellung von Indizes neu geordnet, um eine direkte Berechnung zu ermöglichen.
Zeitkomplexität:
- Auf jeder Ebene der Rekursion gibt es $N N$ N Berechnungen mit Einheitswurzeln und die Tiefe der Rekursion sind $\log_{2} (N) log_2(N)$ log2 (N) .
- Dies ergibt eine zeitliche Komplexität von $O (N \log N) O(N log N)$ O(NlogN) .

Inverse FFT

Die inverse FFT ist ähnlich, verwendet jedoch $e^{2 π i \cdot k n / N} e^{2pi i cdot kn / N}$ e 2πi⋅kn/N als Basis und skaliert das Ergebnis um $1 / N 1/N$ 1/N .

Den FFT-Multiplikationsalgorithmus verstehen

Der FFT-Multiplikationsalgorithmus durchläuft mehrere Schlüsselschritte:

Vorverarbeitung der Zahlen
- Konvertieren Sie die eingegebenen Zahlen in Ziffernarrays
- Verarbeitet sowohl ganzzahlige als auch dezimale Teile
- Füllen Sie die Arrays für die FFT-Berechnung auf die nächste Potenz von 2 auf
Schnelle Fourier-Transformation
- Konvertieren Sie die Zahlenfelder mittels FFT in den Frequenzbereich
- Dadurch wird das Multiplikationsproblem in eine einfachere punktweise Multiplikation im Frequenzbereich umgewandelt
Frequenzbereichsmultiplikation
- Elementweise Multiplikation der transformierten Arrays durchführen
- Verwenden Sie komplexe Zahlenoperationen für effiziente Berechnungen
Inverse FFT und Ergebnisverarbeitung
- Transformieren Sie das multiplizierte Array zurück in den Zeitbereich
- Behandeln Sie Ziffernträger
- Rekonstruieren Sie die letzte Dezimalzahl

Schlüsselkomponenten der Implementierung

Darstellung komplexer Zahlen

class Complex {
  constructor(re = 0, im = 0) {
    this.re = re;  // Real part
    this.im = im;  // Imaginary part
  }

  // Static methods for complex number operations
  static add(a, b) { /* ... */ }
  static subtract(a, b) { /* ... */ }
  static multiply(a, b) { /* ... */ }
}

Nach dem Login kopieren

Die Complex-Klasse ist für die Durchführung von FFT-Operationen von entscheidender Bedeutung und ermöglicht uns die Manipulation von Zahlen sowohl im realen als auch im imaginären Bereich.

Schnelle Fourier-Transformationsfunktion

function fft(a, invert = false) {
  // Bit reversal preprocessing
  // Butterfly operations in frequency domain
  // Optional inverse transformation
}

Nach dem Login kopieren

Die FFT-Funktion ist der Kern des Algorithmus und transformiert Zahlen effizient zwischen Zeit- und Frequenzdomänen.

Umgang mit Dezimalzahlen

Die Implementierung umfasst eine ausgefeilte Logik für den Umgang mit Dezimalzahlen:

Ganzzahl- und Dezimalteile trennen
Verfolgung der gesamten Dezimalstellen
Rekonstruktion des Ergebnisses mit der korrekten Dezimalpunktplatzierung

Beispielanwendungsfälle

// Multiplying large integers
fftMultiply("12345678901234567890", "98765432109876543210")

// Multiplying very large different size integers
fftMultiply("12345678901234567890786238746872364872364987293795843790587345", "9876543210987654321087634875782369487239874023894")

// Multiplying decimal numbers
fftMultiply("123.456", "987.654")

// Handling different decimal places
fftMultiply("1.23", "45.6789")

// Handling different decimal places with large numbers
fftMultiply("1234567890123456789078623874687236487236498.7293795843790587345", "98765432109876543210876348757823694.87239874023894")

Nach dem Login kopieren

Leistungsvorteile

Zeitkomplexität: O(n log n) im Vergleich zu O(n²) traditioneller Methoden
Präzision: Verarbeitet extrem große Zahlen mit mehreren Dezimalstellen
Effizienz: Deutlich schneller bei Multiplikationen großer Zahlen

Einschränkungen und Überlegungen

Erfordert zusätzlichen Speicher für komplexe Zahlendarstellungen
Die Genauigkeit kann durch Gleitkomma-Arithmetik beeinflusst werden
Komplexere Implementierung im Vergleich zur herkömmlichen Multiplikation

Abschluss

Der FFT-Multiplikationsalgorithmus stellt einen leistungsstarken Ansatz zur effizienten Multiplikation großer Zahlen dar. Durch die Nutzung von Frequenzbereichstransformationen können wir komplexe mathematische Operationen mit bemerkenswerter Geschwindigkeit und Präzision durchführen.

Praktische Anwendungen

Wissenschaftliches Rechnen
Finanzielle Berechnungen
Kryptographie
Groß angelegte numerische Simulationen

Weiterführende Literatur

Cooley-Tukey FFT-Algorithmus
Zahlentheorie
Computermathematik

Code

Die vollständige Implementierung folgt und bietet eine robuste Lösung für die Multiplikation großer Dezimalzahlen mithilfe des Ansatzes der schnellen Fourier-Transformation.

/**
 * Fast Fourier Transform (FFT) implementation for decimal multiplication
 * @param {number[]} a - Input array of real numbers
 * @param {boolean} invert - Whether to perform inverse FFT
 * @returns {Complex[]} - Transformed array of complex numbers
 */
class Complex {
  constructor(re = 0, im = 0) {
    this.re = re;
    this.im = im;
  }

  static add(a, b) {
    return new Complex(a.re + b.re, a.im + b.im);
  }

  static subtract(a, b) {
    return new Complex(a.re - b.re, a.im - b.im);
  }

  static multiply(a, b) {
    return new Complex(a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re);
  }
}

function fft(a, invert = false) {
  let n = 1;
  while (n < a.length) n <<= 1;
  a = a.slice(0);
  a.length = n;

  const angle = ((2 * Math.PI) / n) * (invert ? -1 : 1);
  const roots = new Array(n);
  for (let i = 0; i < n; i++) {
    roots[i] = new Complex(Math.cos(angle * i), Math.sin(angle * i));
  }

  // Bit reversal
  for (let i = 1, j = 0; i < n; i++) {
    let bit = n >> 1;
    for (; j & bit; bit >>= 1) {
      j ^= bit;
    }
    j ^= bit;
    if (i < j) {
      [a[i], a[j]] = [a[j], a[i]];
    }
  }

  // Butterfly operations
  for (let len = 2; len <= n; len <<= 1) {
    const halfLen = len >> 1;
    for (let i = 0; i < n; i += len) {
      for (let j = 0; j < halfLen; j++) {
        const u = a[i + j];
        const v = Complex.multiply(a[i + j + halfLen], roots[(n / len) * j]);
        a[i + j] = Complex.add(u, v);
        a[i + j + halfLen] = Complex.subtract(u, v);
      }
    }
  }

  if (invert) {
    for (let i = 0; i < n; i++) {
      a[i].re /= n;
      a[i].im /= n;
    }
  }

  return a;
}

/**
 * Multiply two decimal numbers using FFT
 * @param {string} num1 - First number as a string
 * @param {string} num2 - Second number as a string
 * @returns {string} - Product of the two numbers
 */
function fftMultiply(num1, num2) {
  // Handle zero cases
  if (num1 === "0" || num2 === "0") return "0";

  // Parse and separate integer and decimal parts
  const parseNumber = (numStr) => {
    const [intPart, decPart] = numStr.split(".");
    return {
      intPart: intPart || "0",
      decPart: decPart || "",
      totalDecimalPlaces: (decPart || "").length,
    };
  };

  const parsed1 = parseNumber(num1);
  const parsed2 = parseNumber(num2);

  // Combine numbers removing decimal point
  const combinedNum1 = parsed1.intPart + parsed1.decPart;
  const combinedNum2 = parsed2.intPart + parsed2.decPart;

  // Total decimal places
  const totalDecimalPlaces =
    parsed1.totalDecimalPlaces + parsed2.totalDecimalPlaces;

  // Convert to digit arrays (least significant first)
  const a = combinedNum1.split("").map(Number).reverse();
  const b = combinedNum2.split("").map(Number).reverse();

  // Determine result size and pad
  const resultSize = a.length + b.length;
  const fftSize = 1 << Math.ceil(Math.log2(resultSize));

  // Pad input arrays
  while (a.length < fftSize) a.push(0);
  while (b.length < fftSize) b.push(0);

  // Convert to complex arrays
  const complexA = a.map((x) => new Complex(x, 0));
  const complexB = b.map((x) => new Complex(x, 0));

  // Perform FFT
  const fftA = fft(complexA);
  const fftB = fft(complexB);

  // Pointwise multiplication in frequency domain
  const fftProduct = new Array(fftSize);
  for (let i = 0; i < fftSize; i++) {
    fftProduct[i] = Complex.multiply(fftA[i], fftB[i]);
  }

  // Inverse FFT
  const product = fft(fftProduct, true);

  // Convert back to integer representation
  const result = new Array(resultSize).fill(0);
  for (let i = 0; i < resultSize; i++) {
    result[i] = Math.round(product[i].re);
  }

  // Handle carries
  for (let i = 0; i < result.length - 1; i++) {
    if (result[i] >= 10) {
      result[i + 1] += Math.floor(result[i] / 10);
      result[i] %= 10;
    }
  }

  // Remove leading zeros and convert to string
  while (result.length > 1 && result[result.length - 1] === 0) {
    result.pop();
  }

  // Insert decimal point
  const resultStr = result.reverse().join("");
  if (totalDecimalPlaces === 0) {
    return resultStr;
  }

  // Handle case where result might be shorter than decimal places
  if (resultStr.length <= totalDecimalPlaces) {
    return "0." + "0".repeat(totalDecimalPlaces - resultStr.length) + resultStr;
  }

  // Insert decimal point
  return (
    resultStr.slice(0, -totalDecimalPlaces) +
    "." +
    resultStr.slice(-totalDecimalPlaces).replace(/0+$/, "")
  );
}

Nach dem Login kopieren

Ausgabe

// Example Usage - Self verify using Python
console.log(
  "Product of integers:",
  fftMultiply("12345678901234567890", "98765432109876543210")
);
console.log("Product of decimals:", fftMultiply("123.456", "987.654"));
console.log("Product of mixed decimals:", fftMultiply("12.34", "56.78"));
console.log(
  "Product with different decimal places:",
  fftMultiply("1.23", "45.6789")
);
console.log(
  "Product with large integers:",
  fftMultiply(
    "12345678901234567890786238746872364872364987293795843790587345",
    "9876543210987654321087634875782369487239874023894"
  )
);
const num1 = "1234567890123456789078623874687236487236498.7293795843790587345";
const num2 = "98765432109876543210876348757823694.87239874023894";
console.log("Product:", fftMultiply(num1, num2));

Nach dem Login kopieren

Product of integers: 1219326311370217952237463801111263526900
Product of decimals: 121931.812224
Product of mixed decimals: 700.6652
Product with different decimal places: 56.185047
Product with large integers: 121932631137021795232593613105722759976860134207381319681901040774443113318245930967231822167723255326824021430
Product: 121932631137021795232593613105722759976860134207381319681901040774443113318245.93096723182216772325532682402143

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonGroße Dezimalzahlen mit der Fast-Fourier-Transformation (FFT) multiplizieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!