尽管使用了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似乎有效。

注意：二项式系数码取自罗塞塔码。

Answer 1

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

(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'代替普通的*、-和inc运算符，因为它们内置了对任意精度的支持，并且永不溢出：

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