ホームページ > ウェブフロントエンド > jsチュートリアル > 高速フーリエ変換 (FFT) を使用した大きな 10 進数の乗算

高速フーリエ変換 (FFT) を使用した大きな 10 進数の乗算

Mary-Kate Olsen
リリース: 2024-12-18 22:24:12
オリジナル
429 人が閲覧しました

Multiplying Large Decimal Numbers Using Fast Fourier Transform (FFT)

導入

大きな 10 進数の乗算は、特に桁数や小数点以下の桁数が多い数値を扱う場合、計算が困難になることがあります。従来の乗算方法は、数値が非常に大きい場合には非効率的になります。ここで高速フーリエ変換 (FFT) が役に立ち、大きな数を驚異的な速度で乗算するための強力かつ効率的なアルゴリズムを提供します。

掛け算への応用

  • FFT は、数値を周波数領域に変換し、点単位の乗算を実行してから逆 FFT を適用することにより、多項式または大きな整数の高速乗算を可能にします。

大きな数の掛け算への挑戦

従来の乗算方法の時間計算量は O(n²) (n は桁数) です。非常に大きな数の場合、計算コストが高くなります。 FFT ベースの乗算アルゴリズムは、この複雑さを O(n log n) に軽減し、大きな数に対して大幅に高速化します。

Cooley-Tukey FFT の証明の概要

  1. 離散フーリエ変換 (DFT) の分解:

    • DFT は次のように定義されます。
      Xk=n=0N1 xne2π ikn/N,X_k = sum_{n=0}^{N-1} x_n cdot e^{-2pi i cdot kn / N}, Xk = n=0N−1 xne−2πi⋅kn /N
      どこ NN N は入力信号のサイズです。
    • Cooley-Tukey FFT は、計算をより小さなサイズの DFT に分割します。 N/2N/2 N/2 偶数インデックスの用語と奇数インデックスの用語を分けることにより、次のようになります。
      Xk=n=0N/2 1x2ne2πi (2n )k/N n=0N / 21x2 n 1e2 πi(2n 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=0N/2−1 x2n e −2πi⋅(2n)k/N n=0N/ 2−1x2n 1e−2πi⋅(2n 1)k/N.
    • これは次のようになります。
      Xk=偶数項の DFT Wk奇数項の DFT X_k = text{偶数項の DFT} W_k cdotテキスト{奇数項の DFT}、 Xk =偶数項の DFT Wk奇数項の DFT
      どこ Wk=e2πik/N W_k = e^{-2pi i cdot k / N} Wk =e−2πi ⋅k/N .
  2. 再帰構造:

    • サイズの各 DFT NN N サイズが異なる 2 つの DFT に分割されます。 N/2N/2 N/2 、再帰的な構造につながります。
    • この再帰的な除算は、サイズの基本ケースが得られるまで継続されます。 N=1N = 1 N=1 この時点では、DFT は単なる入力値です。
  3. バタフライオペレーション:

    • アルゴリズムは、バタフライ演算を使用して、より小さな DFT からの結果をマージします。
      a'=u Wkv b'=uWkv,a' = u W_k cdot v、クワッド b' = u - W_k cdot v、 a'=u Wkv,b' =u−Wkv,
      どこ uu u そして vv v はより小さな DFT の結果であり、 WkW_k Wk 団結の根源を表します。
  4. ビット反転順列:

    • 入力配列は、インプレース計算を可能にするために、インデックスのバイナリ表現に基づいて並べ替えられます。
  5. 時間計算量:

    • 再帰の各レベルには、 NN N 単一根を含む計算、再帰の深さは次のとおりです。 ログ2(N)log_2(N) log2 (N) .
    • これにより、時間計算量は次のようになります。 O(N ログN)O(N log N) O(NlogN) .

逆FFT

  • 逆 FFT は似ていますが、以下を使用します。 e2πi kn/Ne^{2pi私は知りません / N} e 2πi⋅kn/N を基準として結果をスケールします 1/N1/N 1/N .

FFT乗算アルゴリズムを理解する

FFT 乗算アルゴリズムは、いくつかの重要なステップを通じて機能します。

  1. 数値の前処理

    • 入力数値を数字の配列に変換します
    • 整数部分と小数部分の両方を処理します
    • FFT 計算のために配列を最も近い 2 のべき乗にパディングします
  2. 高速フーリエ変換

    • FFT を使用して数値配列を周波数領域に変換します
    • これにより、乗算の問題が周波数領域でのより単純な点ごとの乗算に変換されます
  3. 周波数領域の乗算

    • 変換された配列の要素ごとの乗算を実行します
    • 効率的な計算のために複素数演算を利用する
  4. 逆 FFT と結果処理

    • 乗算された配列を時間領域に変換して戻します
    • ハンドル桁桁
    • 最後の 10 進数を再構築します

実装の主要なコンポーネント

複素数表現

1

2

3

4

5

6

7

8

9

10

11

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

}

ログイン後にコピー

Complex クラスは FFT 演算を実行するために重要であり、実数領域と虚数領域の両方で数値を操作できるようになります。

高速フーリエ変換機能

1

2

3

4

5

function fft(a, invert = false) {

  // Bit reversal preprocessing

  // Butterfly operations in frequency domain

  // Optional inverse transformation

}

ログイン後にコピー

FFT 関数はアルゴリズムの中核であり、時間領域と周波数領域の間で数値を効率的に変換します。

10 進数の処理

実装には、10 進数を処理するための高度なロジックが含まれています。

  • 整数部分と小数部分の分離
  • 小数点以下の合計桁数の追跡
  • 正しい小数点の位置で結果を再構築する

使用例の例

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

ログイン後にコピー

パフォーマンス上の利点

  • 時間計算量: 従来の手法の O(n²) と比較した O(n log n)
  • 精度: 小数点以下複数桁の非常に大きな数値を処理します
  • 効率: 大きな数の乗算が大幅に高速化

制限事項と考慮事項

  • 複素数表現には追加のメモリが必要です
  • 精度は浮動小数点演算の影響を受ける可能性があります
  • 従来の乗算と比較して実装が複雑です

結論

FFT 乗算アルゴリズムは、大きな数を効率的に乗算するための強力なアプローチを表します。周波数領域変換を活用することで、複雑な数学的演算を驚くべき速度と精度で実行できます。

実用的なアプリケーション

  • 科学コンピューティング
  • 財務計算
  • 暗号
  • 大規模数値シミュレーション

さらに読む

  • Cooley-Tukey FFT アルゴリズム
  • 整数論
  • 計算数学

コード

完全な実装は次のとおりで、高速フーリエ変換アプローチを使用して大きな 10 進数を乗算するための堅牢なソリューションを提供します。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

/**

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

  );

}

ログイン後にコピー

出力

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

ログイン後にコピー

1

2

3

4

5

6

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

ログイン後にコピー

以上が高速フーリエ変換 (FFT) を使用した大きな 10 進数の乗算の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:dev.to
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
著者別の最新記事
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート