Haskell の乗算は高速フーリエ変換を使ってると聞きました。 軽く確かめてみたら、だいたい O(n * log n) なので、多分そうなんだと思います。 でも、それを明示したドキュメントを見つけられず‥。 それにしても、よく作りこまれてるなぁ。 Prelude> signum $ (2^1000000) * (2^1000000) 1 (0.41 secs, 2093928 bytes) Prelude> signum $ (2^2000000) * (2^2000000) 1 (0.90 secs, 2156652 bytes) Prelude> signum $ (2^4000000) * (2^4000000) 1 (2.01 secs, 2094116 bytes) Prelude> signum $ (2^8000000) * (2^8000000) 1 (4.59 secs