Quando calcolo un fattoriale di grandi dimensioni, perché ottengo un numero negativo?

Question

Quindi, semplice procedura, calcola un numero fattoriale. Il codice è il seguente.

int calcFactorial(int num)
{
    int total = 1;

    if (num == 0)
    {
        return 0;
    }

    for (num; num > 0; num--)
    {
        total *= num;
    }

    return total;
}

Ora, questo funziona benissimo e dandy (ci sono certamente soluzioni più veloci ed eleganti, ma questo funziona per me) per la maggior parte dei numeri. Tuttavia, quando si inseriscono numeri più grandi come 250, per dirla senza mezzi termini, schizza fuori. Ora, la prima coppia fattoriale "bit" per 250 sono {250, 62250, 15126750, 15438000, 3813186000} come riferimento.

Il mio codice sputa {250, 62250, 15126750, 15438000, -481781296 } che è ovviamente disattivato. Il mio primo sospetto era forse che avevo violato il limite di un numero intero a 32 bit, ma dato che 2 ^ 32 è 4294967296 non credo. L'unica cosa che mi viene in mente è forse che viola un limite di firmato a 32 bit, ma non dovrebbe essere in grado di pensare a questo genere di cose? Se essere firmato è il problema, posso risolverlo rendendo l'intero senza segno, ma questa sarebbe solo una soluzione temporanea, poiché la prossima iterazione produce 938043756000 che è di gran lunga superiore al limite di 4294967296.

Quindi, il mio problema è il limite firmato? In tal caso, cosa posso fare per calcolare numeri grandi (anche se ho una classe "LargeInteger" che ho fatto qualche tempo fa che potrebbe essere adatto!) Senza riscontrare di nuovo questo problema?

Answer 1

2 ^ 32 non ti dà il limite per numeri interi con segno.

Il limite di numeri interi con segno è in realtà 2147483647 (se stai sviluppando su Windows usando gli strumenti MS, altre tooluites / piattaforme avrebbero i loro limiti che sono probabilmente simili).

Avrai bisogno di una libreria di grandi numeri C ++ come questa .

Answer 2

Oltre agli altri commenti, vorrei sottolineare due gravi bug nel tuo codice.

• Non hai alcuna protezione contro i numeri negativi.
• Il fattoriale di zero è uno, non zero.

Answer 3

Sì, hai raggiunto il limite. Un int in C ++ è, per definizione, firmato. E, no, C ++ non pensa mai. Se gli dici di fare qualcosa, lo farà, anche se ovviamente è sbagliato.

Valuta l'utilizzo di una libreria di numeri di grandi dimensioni. Ce ne sono molti in giro per C ++.

Answer 4

Se non si specifica firmato o non firmato, il valore predefinito è firmato. Puoi modificarlo usando un'opzione della riga di comando sul tuo compilatore.

Ricorda, C (o C ++) è un linguaggio di livello molto basso e fa esattamente ciò che gli dici di fare . Se gli dici di archiviare questo valore in un int firmato, è quello che farà. Tu come programmatore devi capire quando è un problema. Non è il lavoro della lingua.

Answer 5

Il mio calcolatore di Windows ( Start-Run-Calc ) me lo dice

hex (3813186000) =         E34899D0
hex (-481781296) = FFFFFFFFE34899D0

Quindi sì, la causa è il limite firmato. Poiché i fattoriali possono per definizione essere solo positivi e possono essere calcolati solo per numeri positivi, sia l'argomento che il valore di ritorno devono essere comunque numeri senza segno. (So ??che tutti usano int i = 0 in per i loop, così faccio I. Ma a parte questo, dovremmo usare variabili sempre senza segno se il valore non può essere negativo, è una buona pratica IMO).

Il problema generale con i fattoriali è che possono facilmente generare molto numeri grandi. Potresti usare un float, sacrificando così la precisione ma evitando il problema di overflow dell'intero.

Oh aspetta, secondo quanto ho scritto sopra, dovresti farlo diventare un float senza segno ;-)

Answer 6

Hai un problema di overflow. I fattoriali possono facilmente superare i limiti degli interi. Potresti cambiare la tua funzione per restituire un doppio, ma questo ti farà guadagnare un po 'più di spazio. Nelle applicazioni, è spesso necessario moltiplicare i fattoriali per numeri molto piccoli in cui il risultato finale si inserirà all'interno di un doppio, ma i passaggi intermedi no. Ecco un articolo che spiega come gestire questa situazione: http://www.johndcook.com/blog/2008/04/24/how-to-calculate-binomial-probabilities/

Answer 7

Se ricordo bene:

unsigned short int = max 65535

unsigned int = max 4294967295

unsigned long = max 4294967295

unsigned long long (Int64) = max 18446744073709551615

Fonte modificata:

Valori int / long max

Variabile moderna del compilatore