CODEWITHSUNDEEP
clojureinteger-arithmetic
Sjlver
Sjlver

Reputation: 1295

Overflow in Clojure computation despite using BigInt

The following closure computation overflows despite the use of big integers:

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

I could not figure out where the overflow happens. For example, executing rprod by itself seems to work.

NB: the binomial coefficient code was taken from Rosetta Code.

Upvotes: 1

Views: 139

Answers (1)

Leonid Beschastny
Leonid Beschastny

Reputation: 51470

The problem is that you're calling (rprod 1 k) with an integer 1 and not a 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)

The problem lays in range function:

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

Alternative solution is to use *', -' and inc' instead of ordinary *, - and inc operators, because they have build-in support for arbitrary precision and never overflow:

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

Upvotes: 4

Related Questions