読者です 読者をやめる 読者になる 読者になる

Zodiacの黙示録

いかにも大学生といったような邪気(イノセンス)に満ちたブログ

そうだ俺が怠惰の罪だ

そういえば

この記事は

PMOB Advent Calendar 2016 - Adventarの8日目の記事です。

  • 前の記事

web.matsub.tech

  • 次の記事[🍆]

おはよう

おはよう。さっき起きたよ。

流石にヤバイ。単位大丈夫かしら。

それとね。僕はね、

C言語なんて書きたくない!!!」

「ポインタなんて知るか!!!しね!!!」

うーん。ポインタでごちゃごちゃやってるの読みにく過ぎる。

あれだ、でもちゃんとやるよ。

ただ、もうちょっと時間がいるな。

その前に、大学にちゃんと行かないとね。

それはそうと、ウィリアム・ギブスンの「ニューロマンサー」を、

今読んでいてはまってるんですけど、

サイバーパンク最高か。

お尻を出した子一等賞って感じである。

Haskellはいいぞ

Haskellの特殊な機能というわけではなくて、Haskellに有る機能、

便利な機能が集約されている。

つい最近、「一瞬でHaskellで円周率を一億桁計算する」みたいな、

そういう記事を見つけた。

一億桁を630秒くらいで計算してやるとかいうものであった。

これ↓

Haskellで円周率1億桁を計算する、あるいは円周率計算にHaskellの多倍長整数の改良を見る - 純粋関数空間


でもね、俺のPCでコンパイルして実行したら、390秒だった。

めっちゃ速かった。

恐らくだけど、ByteStringとか使ってbit列扱えるやつとか、

並列処理で速くなるっしょ!って

思ってたんだけど、

どうやらかなり複雑な実装されてるっぽい(わからなかった)

多倍長整数の演算がgmpによって実装されており、高速であるらしい。

並列処理もしてない。

並列化は意味なくて、やってもあんまり速くならないらしい。

そもそもの乗算、これは、FFTで実装されているらしいが、

これ自体を並列化しないと意味がないっぽい。

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だからなのだろうか。

おわり。

ではでは。