CODEWITHSUNDEEP
performancealgorithmclojure
boucekv
boucekv

Reputation: 1230

How to make factorial faster?

I make simple factorial program in Clojure. 

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

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

How can it be done faster? If it can be done some faster way.

Upvotes: 1

Views: 439

Answers (3)

Rörd
Rörd

Reputation: 6681

With the help of your own fact function (or any other), we can define this extremely fast version:

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

This will give the right results for arguments in the range from 1 to 20 in constant time. Beyond that range, your version doesn't give correct results either (i.e. there's an integer overflow with (fact 21)).

EDIT: Here's an improved implementation that doesn't need another fact implementation, does not overflow and should be much faster during definition because it doesn't compute each entry in its lookup table from scratch:

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

EDIT 2: For a different fast solution, i.e. without building up a lookup table, it's probably best to use a library that's already highly optimized. Google's general utility library Guava includes a factorial implementation.

Add it to your project by adding this Leiningen dependency: [com.google.guava/guava "15.0"]. Then you need to (import com.google.common.math.BigIntegerMath) and can then call it with (BigIntegerMath/factorial n).

Upvotes: 2

Nicolas Modrzyk
Nicolas Modrzyk

Reputation: 14197

Here is my favorite: 

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

The ' tells Clojure to use BigInteger transparently so as to avoid overflow.

Upvotes: 2

Vitaly Olegovitch
Vitaly Olegovitch

Reputation: 3547

You can find many fast factorial algorithms here: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

As commented above, Clojure is not the best language for that. Consider using C, C++, ForTran.

Be careful with the data structures that you use, because factorials grow really fast.

Upvotes: 2

Related Questions