clojure - 尽管使用 BigInt，但 Clojure 计算中的溢出

Question

尽管使用了大整数，但以下闭包计算会溢出：

(defn binomial-coefficient [n k]
  (let [rprod (fn [a b] (reduce * (range a (inc b))))]
    (/ (rprod (- n k -1) n) (rprod 1 k))))

(binomial-coefficient 100N 50N)

我无法弄清楚溢出发生在哪里。例如，单独执行rprod似乎有效。

注意：二项式系数代码取自Rosetta Code。

Answer 1

问题是您使用(rprod 1 k)整数1而不是 bigint调用1N：

(defn binomial-coefficient [n k]
  (let [rprod (fn [a b] (reduce * (range a (inc b))))]
    (/ (rprod (- n k -1) n) (rprod 1N k))))

(binomial-coefficient 100N 50N)

问题在于range功能：

=> (range 1 10N)
(1 2 3 4 5 6 7 8 9)
=> (range 1N 10)
(1N 2N 3N 4N 5N 6N 7N 8N 9N)

另一种解决方案是使用*',-'而inc'不是普通的*, -andinc运算符，因为它们具有对任意精度的内置支持并且永远不会溢出：

(defn binomial-coefficient [n k]
  (let [rprod (fn [a b] (reduce *' (range a (inc' b))))]
    (/ (rprod (-' n k -1) n) (rprod 1 k))))

(binomial-coefficient 100 50)