Factorial, type hints and tail recursion in Clojure 1.3.0-alpha4 – ArithmeticException integer overflow?!

If there’s anything I could’ve noticed changed lately in my professional interests since I’ve started programming in Clojure, that’s a gradually rising wish, or I’d say a sort of a desire, to learn more about programming language concepts. It’s not that long ago when I had to write an application in Haskell, OCaml or SML and I could find nothing “groovy” in pursuing my skills in this area. I bet they were a bit too much academic and somehow too less productive with no way to run atop JVM. Functional languages didn’t take my heart and stayed as a relic of the computer science studies of mine. Until Clojure emerged. I’m really fond of the choice.

While I was reading the blog entry Y Combinator in Clojure I stumbled upon the code I could understand in theory, but I don’t think I could write one myself. It looked a bit like the code I’ve seen in the clojure.contrib.monads namespace – simple in theory not so in practice. There’s a function Y that accepts a function F of a single parameter that’s a function of a variable number of input parameters. The Y function returns a function of a single parameter that’s also a function that returns another one. I meant to write it again myself (without looking back at the blog entry), but after a quarter or so I was mentally tired and completely lost. It however planted a idea to try out something easier, I believed.

This time I made an attempt to verify my skills of Clojure in a problem – to write the Factorial function for any arbitrarily high numerical value. I read up quite a bit about tail-call optimization (TCO) that’s not available in JVM (and hence neither is in Clojure), but when recursive calls occur in a tail position it’s possible to reuse a stack avoiding StackOverflowError. I once learnt that tail recursions are easier to write with accumulators. I opened a REPL and begun typing.

$ clj
CLOJURE_DIR:  /Users/jacek/apps/clojure
CLOJURE_CONTRIB_JAR:  /Users/jacek/apps/clojure-contrib-1.3.0-alpha4.jar
Clojure 1.3.0-alpha4
user=> (defn factorial [n] (* n (factorial (- n 1))))
#'user/factorial
user=> (factorial 3)
StackOverflowError   clojure.lang.Numbers.minus (Numbers.java:1811)

The first error I run into was because the recursion didn’t have the stop condition. Easy to fix.

user=> (defn factorial [n]
  (if (<= n 0)
    1 
    (* n (factorial (- n 1)))))
#'user/factorial
user=> (factorial 3)
6
user=> (factorial 100)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1581)

This time the function run well until it was provided with a bigger number. At that time I didn’t know it was about the type used, but thought it was the stack error which I’d expected.

I changed the function to leverage variable input parameters and tail recursion so the call to factorial was the last call on the stack (cf. Recursive Looping). That’s where I expected the optimization would kick in.

user=> (defn factorial
  ([n]
    (factorial n 1)) 
  ([n acc]
    (if (<= n 0) 
      acc 
      (factorial (dec n) (* acc n)))))
#'user/factorial
user=> (factorial 100)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1581)
user=> (.printStackTrace *e)
java.lang.ArithmeticException: integer overflow
	at clojure.lang.Numbers.throwIntOverflow(Numbers.java:1581)
	at clojure.lang.Numbers.multiply(Numbers.java:1850)
	at clojure.lang.Numbers$LongOps.multiply(Numbers.java:509)
	at clojure.lang.Numbers.multiply(Numbers.java:174)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$factorial.invoke(NO_SOURCE_FILE:7)
	at user$eval12.invoke(NO_SOURCE_FILE:8)
	at clojure.lang.Compiler.eval(Compiler.java:6201)
	at clojure.lang.Compiler.eval(Compiler.java:6168)
	at clojure.core$eval.invoke(core.clj:2680)
	at clojure.main$repl$read_eval_print__5619.invoke(main.clj:179)
	at clojure.main$repl$fn__5624.invoke(main.clj:200)
	at clojure.main$repl.doInvoke(main.clj:200)
	at clojure.lang.RestFn.invoke(RestFn.java:422)
	at clojure.main$repl_opt.invoke(main.clj:266)
	at clojure.main$main.doInvoke(main.clj:361)
	at clojure.lang.RestFn.invoke(RestFn.java:437)
	at clojure.lang.Var.invoke(Var.java:409)
	at clojure.lang.AFn.applyToHelper(AFn.java:169)
	at clojure.lang.Var.applyTo(Var.java:518)
	at clojure.main.main(main.java:37)
nil

It wasn’t the case though. I quickly figured out that it worked fine until 21 was given.

user=> (factorial 20)
2432902008176640000
user=> (factorial 21)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1581)

A bit of brainstorming and I found out that the problem was with type (int) overflow not the stack. That reminded me about an article I read about the changes in Clojure 1.3 for Enhanced Primitive Support. I added the type hints and it worked fine. That was it!

user=> (defn factorial
  ([^double n]
    (factorial n 1)) 
  ([n acc]
    (if (<= n 1) 
      acc 
      (factorial (dec n) (* acc n)))))
#'user/factorial
user=> (factorial 21)
5.109094217170944E19
user=> (factorial 100)
9.332621544394418E157

After a while of fiddling I could find that it’s valid for longs and doubles only as the following error says.

user=> (defn factorial
  ([^int n]
    (factorial n 1)) 
  ([n acc]
    (if (<= n 1) 
      acc 
      (factorial (dec n) (* acc n)))))
CompilerException java.lang.IllegalArgumentException: Only long and double primitives are supported, compiling:(NO_SOURCE_PATH:15) 

Try it out yourself. It’s so easy with Clojure REPL. Ping me if you’re stuck and need help.

Ouch, wait, it looks it’s not over…

user=> (factorial 100000)
StackOverflowError   clojure.lang.Numbers.lte (Numbers.java:251)

While I’m at the StackOverflowError let’s have a look at the StackOverflow site. There is indeed a solution – Clojure: Simple factorial causes stack overflow. I wish I had figured out the solution myself (with no Googling or such). I like the reduce-based solution the most!

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

But hey, it now yields ArithmeticException integer overflow!

user=> (defn factorial [n] (reduce * (range 1 (inc n))))
#'user/factorial
user=> (factorial 100000)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1581)

I’m confused. Any help?

Be Sociable, Share!
This entry was posted in Languages.

5 Responses to Factorial, type hints and tail recursion in Clojure 1.3.0-alpha4 – ArithmeticException integer overflow?!

  1. konfetti says:

    Clojure 1.3 default operators are no longer auto-promoting. That’s the reason for an error.

    clojure.core/*
    ([] [x] [x y] [x y & more])
    Returns the product of nums. (*) returns 1. Does not auto-promote
    longs, will throw on overflow. See also: *’

    Try instead *’, should work without any problems:
    (defn factorial [n] (reduce *’ (range 1 (inc n))))

    • Dude says:

      That is stupid as hell. I don’t use Clojure because I want to specify types, I use Clojure because it CAN be dynamic and I don’t have to worry about stupid shit like that. Way to go Rich Hickey for fucking that up.

  2. Brian Goslinga says:

    As konfetti pointed out, the main math operations do not autopromote in 1.3. However, they are still polymorphic and bigints are contagious. You can rewrite your last definition as (defn factorial [n] (reduce * (range 1N (inc n)))) to get the behavior you expect.

    I’m also wondering which part of “ArithmeticException integer overflow” made you think it was a problem with the stack and not a problem with the math.

  3. Hopefully the other two comments will clear up your exception. I know you wrote this as a study in recursion/TCO rather than as a piece of real code, but I have a suggestion. For such large values of N, a real-world program would likely want to use Stirling’s formula — an approximation of the factorial that can be computed in constant time.

    That link provides a Clojure implementation, but I suggest you look it up on Wikipedia and implement it yourself first. :)

Leave a Reply

%d bloggers like this: