ようするにnum_rand回のループなんだから、状態空間をnum_rand/2進んだ状態までワープさせてやれば、
0からnum_rand/2とnum_rand/2からnum_randを並列に計算できる。
と考えていた時期があって、色々と考えてみた。
行列の冪をlog(n)でやる例のアレ
一番最初に考える方法は、行列Bと状態ベクトルxに対して
でワープできるじゃん。
まあでも、普通にやると行列の積が次元の3乗かかるんだよな。
行列の対角化
行列の冪を計算するときって、普通は対角化するじゃん。
固有多項式が原始だから、GF(2^19937)での根が固有値でーとかやってたら、
固有値の冪を固有多項式で割った余りを計算すればいいんだな。
ケーリーハミルトン
とか馬鹿なことやってないで、
を固有多項式で割った後でXにBを代入すればいいんじゃん。
多項式の積は畳み込みだからフーリエ変換だな。この場合の正規直行基底は何にすればいいんだ…
円周率の計算では、メルセンヌ素数とCRTを使った数論変換を使ってた記憶があるのだが…
このへんで諦めた。
