Clojure Koan Factorial Function Implementations

Question

I'm learning clojure and going through the clojure-koan exercises. One of the exercises is about implementing a factorial function. While I was playing around I noticed:

My recursive implementation seems to work for large numbers:

(defn factorial-1 [n]
   (loop [n n f 1]
      (if (= n 1)
          f
          (recur (dec n) (* f n)))))

Calling (factorial-1 1000N) in a REPL yields a number: 402387260077093773...

However when I try the following lazy sequence approach:

(defn factorial-2 [n]
   (reduce * 1 (range 1 (inc n))))

Calling (factorial-2 1000N) in a REPL yields an error:

ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)

Why does the seemingly lazy sequence approach result in an integer overflow error?

Answer 1

You never actually use any bigints in your multiplications, despite passing 1000N, because you only use that number to determine the end of your computation. You start multiplications at 1, and multiply by 1, then 2, and so on. If you modify your definition of factorial-2 to use a bigint, you get the expected behavior:

(defn factorial-2 [n]
  (reduce * 1N (range 1 (inc n))))

Answer 2

Or you can simply use *' function.

(defn factorial-3 [n]
  (reduce *' (range 1 (inc n))))

*' function supports arbitrary precision. It will return Long if the number is in the range of Long. If the range exceeds the Long range, it will return BigInt.