FWTを用いたビット演算畳み込み
概要
高速ウォルシュ変換（FWT）は、FFTが通常の畳み込みを効率的に計算するのと同様に、ビット演算に基づく畳み込み演算を高速化するための手法です。ビット演算畳み込みでは、二つの数列の要素どうしがビット演算の結果に対して寄与します。
具体的には、数列AとBに対して、S[k] = Σi⊕j=k A[i]×B[j] を計算します。ここで⊕はOR、AND、XORなどのビット演算を表します。
...
8月1日 09:20 投稿
奇想天外なアイデアがコードで現実になる場所
8月1日 09:20 投稿