如何使阶乘更快？

Question

我在Clojure中制作简单的阶乘程序。

(defn fac [x y] 
    (if (= x 1) y (recur (- x 1) (* y x))) 
) 

(def fact [n] (fac n 1)) 

它如何做得更快？如果可以以更快的方式完成。

Answer 1

你可以在这里找到许多快速阶乘算法：http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

如上评论，Clojure是不是那个最好的语言。考虑使用C，C++，ForTran。

要小心使用的数据结构，因为阶乘增长非常快。

Answer 2

用自己的fact功能的帮助下（或任何其他），我们可以定义这个极快的版本：

(def fact* (mapv fact (cons 1 (range 1 21)))) 

这将给在范围参数正确的结果，从1至20中恒时间。超出这个范围，你的版本也不会给出正确的结果（即有一个整数溢出(fact 21)）。

编辑：这里有一个改进的实现，并不需要另一个fact实施，不溢出和定义过程中要快很多，因为它不计算从头在查找表中的每个条目：

(def fact (persistent! (reduce (fn [v n] (conj! v (*' (v n) (inc n)))) 
           (transient [1]) 
           (range 1000)))) 

编辑2：对于不同的快速解决方案，即不建立查找表，最好使用已经高度优化的库。 Google的通用实用程序库Guava包含一个阶乘实现。

通过添加Leiningen相关性添加至您的项目：[com.google.guava/guava "15.0"]。然后您需要(import com.google.common.math.BigIntegerMath)，然后可以拨打电话(BigIntegerMath/factorial n)。

Answer 3

这是我最喜欢的：

(defn fact [n] (reduce *' (range 1 (inc n)))) 

的'告诉Clojure中使用的BigInteger透明，以避免溢出。