StackOverflowError computing factorial di un BigInteger?

Sto provando a scrivere un programma Java per calcolare un fattoriale di un numero elevato. Sembra che BigInteger non sia in grado di contenere un numero così grande.StackOverflowError computing factorial di un BigInteger?

Il seguente è il codice (semplice) che ho scritto.

public static BigInteger getFactorial(BigInteger num) { 
     if (num.intValue() == 0) return BigInteger.valueOf(1); 

     if (num.intValue() == 1) return BigInteger.valueOf(1); 

     return num.multiply(getFactorial(num.subtract(BigInteger.valueOf(1)))); 
    }

Il numero massimo il programma di cui sopra maniglie in 5022, dopo che il programma getta un StackOverflowError. Ci sono altri modi per gestirlo?

fonte

2012-01-24 vinoth

Questo non può essere il più grande per i tipi di dati BigInteger. Dove viene generata l'eccezione StackOverflow? Pubblica un codice più pertinente. – JonH

Sì, utilizzare l'algoritmo iterativo. BigInteger sta andando bene, getFactorial ha appena mangiato tutto lo stack space. – harold

@harold (+1) - un altro esempio del perché ritengo che la ricorsione sia una tecnica dannosa per insegnare agli studenti universitari, almeno nelle lingue senza ricorsione a coda. È un esercizio intellettuale, ma alla fine non è utile per qualcosa di interessante. – CPerkins

Il problema qui sembra proprio un stack overflow da troppo recursion (5000 chiamate ricorsive sembra circa il giusto numero di chiamate per spegnere una Java call stack) e non una limitazione di BigInteger. Riscrivere la funzione fattoriale in modo iterativo dovrebbe risolvere questo problema. Ad esempio:

public static BigInteger factorial(BigInteger n) { 
    BigInteger result = BigInteger.ONE; 

    while (!n.equals(BigInteger.ZERO)) { 
     result = result.multiply(n); 
     n = n.subtract(BigInteger.ONE); 
    } 

    return result; 
}

Spero che questo aiuti!

fonte

2012-01-24 18:59:59 templatetypedef

Codice modificato per utilizzare le costanti statiche 'BigInteger.ONE' e' ZERO'. – tskuzzy

Durante la classe dell'algoritmo, mi sono ricordato di una tecnica che utilizzava Push/Pop su una pila per evitare l'eccezione StackOverflow quando si implementava la funzione [Ackermann] estremamente estremamente recursiva (http://en.wikipedia.org/wiki/Ackermann_function) in Java, in particolare per 'A (4,1)' che ha richiesto circa 28 minuti per l'esecuzione su Core2Duo T7250. –

@ ee.- Quello che stai descrivendo sta sostituendo lo stack di runtime con uno stack esplicito. Questo può essere fatto funzionare, sebbene la complessità della maggior parte degli algoritmi scritti in questo modo sia spesso superiore alla versione ricorsiva. – templatetypedef

Il problema non è BigInteger, è l'utilizzo di una chiamata al metodo ricorsivo (getFactorial()).

fonte

2012-01-24 19:00:26 jtahlborn

Prova a modificare, un algoritmo iterativo:

public static BigInteger getFactorial(int num) { 
    BigInteger fact = BigInteger.valueOf(1); 
    for (int i = 1; i <= num; i++) 
     fact = fact.multiply(BigInteger.valueOf(i)); 
    return fact; 
}

fonte

2012-01-24 19:14:22

I Guava librerie da Google hanno un'implementazione altamente ottimizzata di fattoriale che emette BigIntegers. Check it out. (Fa più bilanciati moltiplica e ottimizza i semplici spostamenti.)

fonte

2012-01-24 20:50:59

Le implementazioni inganne di fattoriali non funzionano in situazioni reali.

Se si ha una necessità seria, la cosa migliore da fare è scrivere una funzione gamma (o la funzione ln(gamma)) che funzionerà non solo per i numeri interi ma anche per i numeri decimali. Memorizza i risultati in modo da non dover continuare a ripetere i calcoli utilizzando uno WeakHashMap e sei in affari.

fonte

2012-01-24 23:16:07 duffymo

StackOverflowError computing factorial di un BigInteger?

risposta

Problemi correlati