200秒，可以做什么？——测测你的电脑精确计算能力

无心人

import Time
  
  factl :: Integer -> Integer
  factl n = product [1..n]
  
  facthi :: Integer -> Integer -> Integer
  facthi n m = if (n == m) then n else
               if (n > m)  then 1 else
                 (facthi n (n + (div (m - n) 2))) * (facthi (n + (div (m - n) 2) + 1) m)

  facth n = facthi 1 n

  main = do
           t <- getClockTime
           let f = facth 100000
           print (mod f (2^31-1))
           print (t)
           t <- getClockTime
           print t

竟然瞬间返回， 时间在1秒内
看来Haskell也不是废柴啊
如果运行1000000！是6秒
数量级和HugeCalc是一样的， 呵呵

mathe

你的程序里面好像只看到100000而不是1000000

无心人

我改成1000000运行过一次啊
老大

gxqcn

你给出代码的算法，就阶乘本身来说，与先完全因数分解后再计算复杂度确实相当，
但后者仍将快那么一点，因为可以充分调用平方运算。

在同样的机器上，HugeCalc 计算 1000000! 需要多长时间。

无心人

你给我打包个测试程序

gxqcn

直接下载：http://www.emath.ac.cn/download/Factorial.zip
或更全的：http://www.emath.ac.cn/download/HugeCalc_sfx.exe

无心人

1.27左右
21.23未带FFT优化的

gxqcn

Haskell 有这个表现看来还是不错的，至少其大数乘法是用了些高级算法的。

无心人

haskell用的是GMP库

gxqcn

原来如此啊。
我说咋也这么强呢（虽然还不及 HugeCalc）