FFT(高速フーリエ変換)

調べ調べ。
読み読み。
作り作り。

OS自作入門、思ったより軽いノリでおもろい。
整数計画法、興味深し。
フーリエ変換、ネットで見た方が早かったりする。

無循環無理数圧縮というより数列解析か。
僕にはもっと高高圧縮法が必要なんだ・・・
もっと多くのエロ画像を蒐集する為に！

うーん。

X*Yの領域をg*g格子に分割する。
互いに衝突する矩形ユニットがu体ある時、
単純な当たり判定を行う回数は、1/2*u*u。
一方、マッピングを施した場合、
ユニットサイズがx*yであるとすると、
1格子あたりに含まれる平均ユニット数は、
U=(g+x)*(g+y)*u/(X*Y) 。
さらに、当たる側のユニットの矩形判定が
"またがっている"平均格子数は、
G=1+((x*(X/g)*Y)+(y*(Y/g)*x))*2/(X*Y) 。
U*Gが1ユニットが当たり判定を行う確率で、
このマッピングではユニットIDを保持しないので、
(u-1)回の判定を行う。
これをユニットu体分行うわけだから、総判定回数は、
U*G*(u-1)*u 。
単純な当たり判定と比較すると、
U*G*(u-1)*u=1/2*u*u 。
U*G*(u-1)-1/2*u=0 。
こいつを関数ソフトにつっこんで、
X=5120，Y=3840，x=14，y=5，u=256のgの関数として表示すると・・・

http://members4.tsukaeru.net/boo/070921.png

意味不明グラフできた＼(＾o＾)／

6*6マッピングで最大124回分の判定を減らせるんだって。
し、信じられるカー！

んーしかし100％ありえないと言い切れない結果かー・・・
bool配列で確保して約136kb。
まあ効率自体はg=172(166b)から上回るから
あえて最大効率を求める必要もないんだけど。
いや、それ以前にね。

一番怪しいのはGか。
矩形判定だから、最大4つの格子にまたがる可能性があって、
2つにまたがるのは格子境界のx*Y面積が境界数分、
あとy方向の分で・・・うーん。

1じゃないのか。1*(X*Y-((x*(X/g)*Y)+(y*(Y/g)*x)))/X*Y か。
これ1じゃないよな。いや分かってたけど、
式長くなるの嫌できっと1だと思い込もうとしていた。
お前あるまじきwww

変わんないな。
最大効率が1ずつ減ってg=5で-125回になった。
ギャグかー！