Как сделать факториал быстрее?

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)).

EDIT: Вот улучшенная реализация, которая не нуждается в другой fact реализации, не переполнить и должна быть намного быстрее во время определения, поскольку он не вычисляет каждую запись в своей поисковой таблице с нуля:

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

EDIT 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 прозрачно для того, чтобы избежать переполнения.