Scala fattoriale sui grandi numeri a volte si blocca e, a volte non si

Question

Il seguente programma, è stato compilato e testato, a volte restituire il risultato, e, a volte riempie lo schermo con

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

Il programma:

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

le mie domande:

• è perché c'è un overflow dello stack sulla JVM, che a volte accade e someti mes non lo fa?
• Questo comportamento non deterministico è considerato un errore?
• Presumo che Scala non si sia comportato in modo anomalo? come posso farlo tail-recurse this?

Dettagli:

Scala versione del compilatore 2.7.5.final - Copyright 2002-2009, LAMP/EPFL Scala codice di versione corridore 2.7.5.final - copyright 2002-2009 , LAMP/EPFL

versione java "1.6.0_0" OpenJDK Runtime Environment (build 1.6.0_0-b11) OpenJDK client VM (build 1.6.0_0-b11, modalità mista, condivisione)

Ubuntu 2.6.24-24-generic

Answer 1

ottimizzazione Tail-chiamata funziona solo a Scala se la chiamata ricorsiva è l'ultima istruzione nella funzione. È molto limitato Il libro Scala dice:

[...] ottimizzazione tail-call è limitata alle situazioni in cui una funzione metodo o nidificato in sé chiamate direttamente come la sua ultima operazione, senza passare per un valore di funzione o qualche altro intermediario.

Nel tuo caso, la chiamata ricorsiva fa parte di un'espressione più grande e non è l'ultima operazione - l'ultima operazione qui è la moltiplicazione.

This article dimostra come farlo funzionare:

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

Answer 2

In Scala 2.8 è possibile utilizzare l'annotazione @tailrec quando ci si aspetta che l'ottimizzazione chiamata coda deve essere utilizzato, e ottenere un avviso se non è possibile per il compilatore per farlo.

Answer 3

Se davvero avete grandi numeri, ci sono molti approximations, ad esempio, questo uno a Scala che utilizza fattorizzazione in numeri primi:

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