Multiplication de grands nombres décimaux à l'aide de la transformation de Fourier rapide (FFT)

Introduction

La multiplication de grands nombres décimaux peut être un défi de calcul, en particulier lorsqu'il s'agit de nombres comportant de nombreux chiffres ou plusieurs décimales. Les méthodes de multiplication traditionnelles deviennent inefficaces pour des nombres extrêmement grands. C'est ici que la transformée de Fourier rapide (FFT) vient à la rescousse, fournissant un algorithme puissant et efficace pour multiplier de grands nombres avec une vitesse remarquable.

Application en multiplication

• FFT permet une multiplication rapide de polynômes ou de grands entiers en transformant les nombres dans le domaine fréquentiel, en effectuant une multiplication ponctuelle, puis en appliquant la FFT inverse.

Le défi de la multiplication en grand nombre

Les méthodes de multiplication traditionnelles ont une complexité temporelle de O(n²), où n est le nombre de chiffres. Pour de très grands nombres, cela devient coûteux en calcul. L'algorithme de multiplication basé sur la FFT réduit cette complexité à O(n log n), ce qui la rend nettement plus rapide pour les grands nombres.

Aperçu de la preuve pour Cooley-Tukey FFT

1. Décomposition de la transformée de Fourier discrète (TFD) :

   • Le DFT est défini comme :
     $$X_k=\sum _{n=0}^{N-1}{x}_n\cdot e^{-2\pi \mathrm{je}\cdot kn\mathrm{/}N},$$Xk ​= n=0∑N−1​ xn​⋅ e−2πi⋅kn /N,
     où $N$N est la taille du signal d'entrée.
   • La FFT Cooley-Tukey divise le calcul en DFT plus petites de taille $N\mathrm{/}2$N/2 en séparant les termes pairs et impairs :
     $$X_k=\sum _{n=0}^{N\mathrm{/}2-1}{x}_{2n}\cdot e^{-2\pi i\cdot (2n)k\mathrm{/}N}\sum _{n=0}^{N\mathrm{/}2-1}{x}_{2n1}\cdot e^{-2\pi i\cdot (2n1)k\mathrm{/}N}\mathrm{.}$$Xk ​= n=0∑N/2−1​ x2n​ ⋅e −2πi⋅(2n)k/N n=0∑N/ 2−1​x 2n 1​⋅ e−2πi⋅(2n 1)k/N.
   • Cela se réduit à :
     $$X_k=\text{DFT de termes pairs}{W}_k\cdot \text{DFT de termes impairs},$$Xk​ =DFT de termes pairs Wk​⋅DFT de termes impairs,
     où $W_k=e^{-2\pi i\cdot k\mathrm{/}N}$Wk​ =e−2πi ⋅k/N .

2. Structure récursive :

   • Chaque DFT de taille $N$N est divisé en deux DFT de taille $N\mathrm{/}2$N/2 , conduisant à une structure récursive.
   • Cette division récursive se poursuit jusqu'au cas de base de taille $N=1$N=1 , auquel cas la DFT est simplement la valeur d'entrée.

3. Opérations Papillons :

   • L'algorithme fusionne les résultats de DFT plus petites à l'aide des opérations papillon :
     $$a^{\mathrm{\prime }}=u{W}_k\cdot v,b^{\mathrm{\prime }}=u-W_k\cdot v,$$un′=u Wk​⋅v,b′ =u−Wk​⋅v,
     où $u$u et $v$v sont les résultats de DFT plus petits et $W_k$Wk​ représente les racines de l'unité.

4. Permutation d'inversion de bits :

   • Le tableau d'entrée est réorganisé en fonction de la représentation binaire des indices pour permettre le calcul sur place.

5. Complexité temporelle :

   • A chaque niveau de récursivité, il y a $N$N calculs impliquant des racines de l'unité, et la profondeur de la récursion est ${\mathrm{journal}}_2(N)$log2 ​(N) .
   • Cela donne une complexité temporelle de $O(N\mathrm{journal}N)$O(NlogN) .

FFT inverse

• La FFT inverse est similaire mais utilise $e^{2\pi i\cdot kn\mathrm{/}N}$e 2πi⋅kn/N comme base et met à l'échelle le résultat en $1\mathrm{/}N$1/N .

Comprendre l'algorithme de multiplication FFT

L'algorithme de multiplication FFT fonctionne en plusieurs étapes clés :

1. Prétraitement des nombres

   • Convertir les nombres saisis en tableaux de chiffres
   • Gérer les parties entières et décimales
   • Remplissez les tableaux à la puissance 2 la plus proche pour le calcul FFT

2. Transformée de Fourier rapide

   • Convertissez les tableaux de nombres dans le domaine fréquentiel à l'aide de FFT
   • Cela transforme le problème de multiplication en une multiplication ponctuelle plus simple dans le domaine fréquentiel

3. Multiplication du domaine de fréquence

   • Effectuer une multiplication élément par élément des tableaux transformés
   • Utiliser des opérations sur des nombres complexes pour un calcul efficace

4. FFT inverse et traitement des résultats

   • Retransformez le tableau multiplié dans le domaine temporel
   • Poignée porte-chiffres
   • Reconstruire le nombre décimal final

Éléments clés de la mise en œuvre

Représentation des nombres complexes

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) { /* ... */ }
}

La classe Complex est cruciale pour effectuer des opérations FFT, nous permettant de manipuler des nombres dans les domaines réels et imaginaires.

Fonction de transformation de Fourier rapide

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

La fonction FFT est au cœur de l'algorithme, transformant efficacement les nombres entre les domaines temporel et fréquentiel.

Gestion des nombres décimaux

L'implémentation inclut une logique sophistiquée pour gérer les nombres décimaux :

• Séparation des parties entières et décimales
• Suivi du nombre total de décimales
• Reconstruire le résultat avec le placement correct de la virgule décimale

Exemples de cas d'utilisation

// 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")

Avantages en termes de performances

• Complexité temporelle : O(n log n) par rapport à O(n²) des méthodes traditionnelles
• Précision : gère des nombres extrêmement grands avec plusieurs décimales
• Efficacité : Nettement plus rapide pour les multiplications de grands nombres

Limites et considérations

• Nécessite de la mémoire supplémentaire pour les représentations de nombres complexes
• La précision peut être affectée par l'arithmétique à virgule flottante
• Mise en œuvre plus complexe par rapport à la multiplication traditionnelle

Conclusion

L'algorithme de multiplication FFT représente une approche puissante pour multiplier efficacement de grands nombres. En tirant parti des transformations du domaine fréquentiel, nous pouvons effectuer des opérations mathématiques complexes avec une vitesse et une précision remarquables.

Applications pratiques

• Informatique scientifique
• Calculs financiers
• Cryptographie
• Simulations numériques à grande échelle

Lectures complémentaires

• Algorithme FFT de Cooley-Tukey
• Théorie des nombres
• Mathématiques computationnelles

Code

La mise en œuvre complète suit, fournissant une solution robuste pour multiplier de grands nombres décimaux à l'aide de l'approche de transformée de Fourier rapide.

/**
 * 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+$/, "")
  );
}

Sortir

// 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));

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!