無理数基底離散加重変換

数学において、無理数基底離散重み付き変換( IBDWT ) は、無理数基底を用いた高速フーリエ変換の変種であり、 1990 年代初頭にリチャード・クランドール(リード大学)、バリー・ファギン(ダートマス大学)、ジョシュア・ドエニアス( NeXT Software ) ^{[ 1 ]}によってMathematica を使用して開発されました。これは、現代のコンピュータ上で大規模なモジュラー乗算を高速かつ実用的に実装することを意味し、漸近的には非モジュラーFFT 乗算の2倍の速さです。^{[ 2 ] [ 3 ]}

これは特に、グレートインターネットメルセンヌ素数探索で使用されています。

IBDWT法は、メルセンヌ素数のルーカス・レーマー判定法（メルセンヌ数を法とする繰り返し二乗を必要とする）に適用される。${\displaystyle M_{p}=2^{p}-1}$）は、クランドールとフェイギンによって開発された4つの主要な要素に基づいています。^{[ 4 ]}

• バランスのとれた基数表現: 数字に符号を付けることができます (例: の範囲)${\displaystyle -W/2\leq x_{j}<W/2}$）誤差範囲が縮小する。^{[ 4 ]}
• 可変基数桁表現:各桁を許可します${\displaystyle x_{j}}$独自の基地を持つ${\displaystyle W_{j}}$[ ^{4 ]​}
• 重み付き巡回畳み込み：乗算は離散重み付き変換（DWT）を使用して実行されます。^{[ 4 ]}
• 無理数基数：変換に使用される基数は無理数です。^{[ 4 ]}

このアプローチでは、配列をゼロパディングする必要がなくなり、モジュロ乗算を実行します。${\displaystyle M_{p}}$直接。^{[ 4 ]}積を計算するアルゴリズム${\displaystyle xy{\pmod {M_{p}}}}$内容は以下のとおりです。^{[ 4 ]}

1. 実行長（信号長）を選択してください${\displaystyle N<p}$[ ^{4 ]​}
2. 数値の変数基数表現を確立します。たとえば、${\textstyle x=\sum _{j=0}^{N-1}x_{j}2^{\lceil pj/N\rceil }}$[ ^{4 ]}倍精度演算を使用する場合、各項は通常16ビットから20ビットの間になります。各項の最大サイズは、少なくともPercival 2003の貢献以前は、経験的に決定されていまし^た。^{[ a ]}
3. 重み信号を定義する${\displaystyle a}$各コンポーネント${\displaystyle a_{j}=2^{\lceil pj/N\rceil -pj/N}}$区間[1, 2)の浮動小数点数で近似される。^{[ 4 ]}
4. 両方の数値について順方向DWTを計算します。${\displaystyle {\mathcal {X}}\leftarrow DWT_{(N,a)}x}$そして${\displaystyle {\mathcal {Y}}\leftarrow DWT_{(N,a)}y}$これは実際には標準的なDFT（FFTなど）を使用して計算されます。${\displaystyle DWT_{(N,a)}x\triangleq DFT_{(N)}(ax)}$[ ^{4 ]​}
5. 変換された配列の各要素の積を計算します。$\displaystyle {\mathcal {Z}}\leftarrow {\mathcal {X}}{\mathcal {Y}}}$[ ^{4 ]​}
6. 逆離散ウェーブレット変換を計算します。${\displaystyle z\leftarrow DWT_{(N,a)}^{-1}{\mathcal {Z}}}$これは次のように計算されます。${\displaystyle z=a^{-1}DFT_{(N)}^{-1}({\mathcal {Z}})}$[ ^{4 ]​}
7. 結果として得られた各要素を最も近い整数に丸めます。${\displaystyle z\leftarrow {\text{round}}(z)}$必要に応じて、丸め誤差が 0.4 以下であることを確認します (0.4 以上は、各項に詰め込まれた整数ビットが多すぎることを示します)。^{[ 4 ]}
8. 結果の桁数を調整する${\displaystyle \{z_{n}\}}$可変基数基数表現を復元する。このステップでは、繰り上がりと借り入れを処理する。1ステップの部分繰り上がりで十分である。^{[ 4 ]}

倍精度IBDWTは、Great Internet Mersenne Prime Searchのx86クライアントPrime95で、Lucas–LehmerテストとFermat primaryテストにおけるモジュラ乗算を実行するために使用されています。Prime95のIBDWTライブラリgwnumは、 PrimeGridのLLR2やPRSTなどのプログラムでも使用されています。Pentium 4以降のx86 CPUは倍精度浮動小数点演算能力が非常に高いため、IBDWTを使用して数値を乗算する方が、より単純な整数FFT（NTT）を使用するよりもはるかに高速であるため、IBDWTが選択されています。

倍精度IBDWTは、Glucasの形で他のCPUアーキテクチャにも移植されています。また、CUDALucas、GPUowl、PRPLLの形でGPUにも移植されています。^{[ 4 ]}

^{IBDWTは、整数演算を法とする2 64} -2 ³² +1、つまり数論的変換を用いて行うこともできます。このアプローチは、Nick Craig-WoodがARMPrimeで初めて実証しました。^{[ 5 ]}これもGPUに移植され、倍精度演算能力は低いものの32ビット整数演算能力は許容範囲内のコンシューマー向けGPU、特に2020年代のNvidiaモデル（32ビット整数乗算速度は「1:1」または「1:2」だが、倍精度演算速度は32ビット浮動小数点比で「1:64」）の代替手段となっています。^{[ 6 ]}