Scala factorial on large numbers sometimes crashes and sometimes doesn't

Question

The following program, was compiled and tested, it sometimes return the result, and sometimes fills the screen with

java.lang.StackOverflowError
at scala.BigInt$.apply(BigInt.scala:47)
at scala.BigInt.equals(BigInt.scala:129)
at scala.runtime.BoxesRunTime.equals(Unknown Source)
at bigint$.factorial(fact2.scala:3)
at bigint$.factorial(fact2.scala:3)
...

The program:

object bigint extends Application {
  def factorial(n: BigInt): BigInt = if (n == 0) 1 else n * factorial(n-1)
  println("4391! = "+factorial(4391))
}

My questions:

Is it because there is a stack overflow on the JVM, which sometimes happens and sometimes doesn't?
Is this nondeterministic behavior considered a bug?
I assume Scala did not tail-recursed this? how can I make it tail-recurse this?

Details:

Scala compiler version 2.7.5.final -- Copyright 2002-2009, LAMP/EPFL Scala code runner version 2.7.5.final -- Copyright 2002-2009, LAMP/EPFL

java version "1.6.0_0" OpenJDK Runtime Environment (build 1.6.0_0-b11) OpenJDK Client VM (build 1.6.0_0-b11, mixed mode, sharing)

Ubuntu 2.6.24-24-generic

What do you mean by "couldn't see the first line of this"? Can you pipe the output into a file? — mats, Jul 27 '09 at 10:35
@msiemeri, strangely when I "scala bigint > file" it only works when the program doesn't crush. — Liran Orevi, Jul 27 '09 at 10:43
Did you try "scala bigint > file 2>&1" as well? With 2>&1 it redirects output of stderr to the stdout sink (which is, in this case, 'file'). — mats, Jul 27 '09 at 12:03

skaffman · Accepted Answer · 2009-07-27T10:57:01.653

13

Tail-call optimization will only work in Scala if the recursive call is the last statement in the function. It's very limited. The Scala book says:

[...] tail-call optimization is limited to situations in which a method or nested function calls itself directly as its last operation, without going through a function value or some other intermediary.

In your case, the recursive call is part of a larger expression, and is not itself the very last operation - the last operation here is the multiplication.

This article demonstrates how to make it work:

class Factorial {
  def factorial(n: Int): Int = {
    def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) acc
      else factorialAcc(n * acc, n - 1)
    }
    factorialAcc(1, n)
  }
}

edited Jul 27 '09 at 10:57

answered Jul 27 '09 at 10:20

skaffman

398,947
96
818
769

I'm not sure I understand, println isn't a part of the factorial function, or is it? – Liran Orevi Jul 27 '09 at 10:35
You're right, I misread your code (I've reformatted it to make it a bit clearer, and I'll update my answer). – skaffman Jul 27 '09 at 10:53
It worked, well done, also thanks for the link to the great article on the subject. – Liran Orevi Jul 28 '09 at 13:13

score 7 · Answer 2 · answered Sep 23 '09 at 08:33

7

In Scala 2.8 you can use the @tailrec annotation when you expect that tail call optimization should be used, and get a warning if it's not possible for the compiler to do so.

answered Sep 23 '09 at 08:33

Thanks, have you used it? not sure it was released yet. http://www.scala-lang.org/downloads – Liran Orevi Sep 23 '09 at 08:44

Renaud · Answer 3 · 2011-11-10T20:10:18.243

If you really have large numbers, there are many approximations, for example this one in Scala that uses prime factorization:

class SwingFactorial(n: Int) {

  def name() = "SwingFactorial"

  def value(): BigInt =
    {
      if (n < 0)
         {
          throw new IllegalArgumentException(
          "Factorial: n has to be >= 0, but was " + n)
         }

      ndiv2OddFact = BigInt(1)
      ndiv4OddFact = ndiv2OddFact

      return oddFactorial(n) << (n - MathFun.bitCount(n))
    }

  private def oddFactorial(n: Int): BigInt =
    {
      val oddFact =
      if (n < Small.oddFactorial.length)
        {
          BigInt(Small.oddFactorial(n))
        }
      else
        {
          val of = oddFactorial(n / 2)
          (of * of) * oddSwing(n)
        }

      ndiv4OddFact = ndiv2OddFact
      ndiv2OddFact = oddFact
      return oddFact
    }

  private def oddSwing(n: Int): BigInt =
    {
      if (n < Small.oddSwing.length)
      {
        return BigInt(Small.oddSwing(n))
      }

      val len = if ((n % 4) != 2) (n - 1) / 4 + 1 else (n - 1) / 4
      val high = n - ((n + 1) & 1)
      val ndiv4 = n / 4
      val oddFact = if (ndiv4 < Small.oddFactorial.length)
            BigInt(Small.oddFactorial(ndiv4)) else ndiv4OddFact

      return product(high, len) / oddFact
    }

    private def product(m: Int, len: Int): BigInt =
    {
      if (len == 1) return BigInt(m) 
      if (len == 2) {val M = m.toLong; return BigInt(M * (M - 2))}

      val hlen = len >>> 1
      return product(m - hlen * 2, len - hlen) * product(m, hlen)
    }

  private var ndiv4OddFact = BigInt(1)
  private var ndiv2OddFact = BigInt(1)
}

Usage:

var fs = new SwingFactorial(n)
val a = fs.value()

Scala factorial on large numbers sometimes crashes and sometimes doesn't

3 Answers3

Linked