1

次のクロージャー計算は、大きな整数を使用しているにもかかわらずオーバーフローします。

(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から取得されました。

4

1 に答える 1

4

問題は、bigint ではなく(rprod 1 k)整数で呼び出していることです。11N

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

代替の解決策は、通常の, and演算子の代わりに*', -'andを使用することです。これは、任意の精度を組み込みでサポートし、オーバーフローしないためです。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)
于 2013-10-31T15:57:02.530 に答える