そうだ俺が怠惰の罪だ
おはよう
おはよう。さっき起きたよ。
流石にヤバイ。単位大丈夫かしら。
それとね。僕はね、
「C言語なんて書きたくない！！！」
「ポインタなんて知るか！！！しね！！！」
うーん。ポインタでごちゃごちゃやってるの読みにく過ぎる。
あれだ、でもちゃんとやるよ。
ただ、もうちょっと時間がいるな。
その前に、大学にちゃんと行かないとね。
それはそうと、ウィリアム・ギブスンの「ニューロマンサー」を、
今読んでいてはまってるんですけど、
サイバーパンク最高か。
お尻を出した子一等賞って感じである。
Haskellはいいぞ
Haskellの特殊な機能というわけではなくて、Haskellに有る機能、
便利な機能が集約されている。
つい最近、「一瞬でHaskellで円周率を一億桁計算する」みたいな、
そういう記事を見つけた。
一億桁を630秒くらいで計算してやるとかいうものであった。
これ↓
Haskellで円周率1億桁を計算する、あるいは円周率計算にHaskellの多倍長整数の改良を見る - 純粋関数空間
でもね、俺のPCでコンパイルして実行したら、390秒だった。
めっちゃ速かった。
恐らくだけど、ByteStringとか使ってbit列扱えるやつとか、
並列処理で速くなるっしょ！って
思ってたんだけど、
どうやらかなり複雑な実装されてるっぽい（わからなかった）
多倍長整数の演算がgmpによって実装されており、高速であるらしい。
並列処理もしてない。
並列化は意味なくて、やってもあんまり速くならないらしい。
そもそもの乗算、これは、FFTで実装されているらしいが、
これ自体を並列化しないと意味がないっぽい。
実装どうやってされてんの？
ってここで思ったわけで、ちょっと調べた。
以下が実装なのか？
Springerの「Intelligent Computer Mathematics」を参考にした。
-- Implementation of Cooley-Tukey algorithm in Haskell fft :: [Complex Double] -> [Complex Double] fft f = mix [fft (l @+ r), fft ((l @- r)@* w)] where (l, r) = splitAt (length f `div` 2) f mix = concat . transpose (@+) f g = zipWith (+) f g -- @-, @* analog -- w is list of powers of an n-th primitive root of unit -- FFT-based multiplication modulo x^n - 1 in Haskell (%*%) :: (Num a) => [a] -> [a] -> [a] (%*%) f g = unlift $ ifft ((fft $ lift f) @* (fft $ lift g)) -- where lift :: (Num a) => [a] -> [Complex Double] -- unlift :: [Complex Double] -> [Int] -- ifft is the inverse fft, basicly thesame fft with -- different twiddle factors. -- And (@*) is still element-wise multiplication
Haskellの乗算はめっちゃ速い。
Computing the factorialで考えると、
NaiveC++よりNaiveHaskellの方が全然速いくらいである。
FFTだからなのだろうか。
おわり。
ではでは。
