FWTを用いたビット演算畳み込み
概要
高速ウォルシュ変換（FWT）は、FFTが通常の畳み込みを効率的に計算するのと同様に、ビット演算に基づく畳み込み演算を高速化するための手法です。ビット演算畳み込みでは、二つの数列の要素どうしがビット演算の結果に対して寄与します。
具体的には、数列AとBに対して、S[k] = Σi⊕j=k A[i]×B[j] を計算します。ここで⊕はOR、AND、XORなどのビット演算を表します。
...
8月1日 09:20 投稿
多項式の基本と高速変換技法
多項式の定義と表現形式
多項式とは、有限個の項からなる式 \(f(x) = \sum_{i=0}^{n} a_i x^i\) のことを指す。各項の係数は \(a_i\) で表され、最高次の項の次数を「次数（degree）」と呼ぶ。
多項式の表現方法には主に2種類ある：
係数表現：上記のように係数列 \((a_0, a_1, ..., a_n)\) で表す。
点値表現：\(n+1\) 個の異なる点 \((x_i, f(x_i))\) で多項式を一意に ...
5月20日 08:34 投稿