CODEWITHSUNDEEP
clojurelazy-evaluationinteger-overflow
Chetan
Chetan

Reputation: 48011

Integer overflow using lazy sequences in Clojure

I'm just learning to use lazy sequences in Clojure, and I'm not sure what I'm doing wrong in the following code:

(defn sum [seqn]
  (reduce + seqn))

(defn fib
  ([] (concat [0 1] (fib 0 1)))
  ([a b] (lazy-seq (cons (+ a b) (fib b (+ a b))))))

(defn up-to [n seqn]
  (filter (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) => ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)

The numbers being summed shouldn't be larger than 100, so what is causing the integer overflow?

Upvotes: 8

Views: 771

Answers (2)

Jan
Jan

Reputation: 11726

Filtering an infinite seq produces an infinite seq and reducing over this causes filter to keep looking for another matching item even after the predicate stops returning true.

Replace filter with take-while. The infinite sequence generated by (fib) will cause filter to run forever, but before that it will break due to the ArithmeticException you're experiencing. take-while will stop further evaluation of the list after the (fn [x] (< x n)) predicate evaluates to false.

(defn up-to [n seqn]
  (take-while (fn [x] (< x n)) seqn))

(sum (up-to 100 (fib))) ;; => 232

Upvotes: 5

Arthur Ulfeldt
Arthur Ulfeldt

Reputation: 91554

starting with clojure 1.3.0 numbers don't auto-promote to bigInt/bigDecimal.

to fix this use +' instead

your 100th fibinachi number is too large for an integer 

user> (nth (fib) 100)
354224848179261915075N

Upvotes: 5

Related Questions