[C] calcolo fattoriale

[Ben Echmeyer]

Salve, ho un problema nello scrivere un programma in cosole che calcoli il fattoriale, quando lo avvio lo calcola esatto fino a 12 ma con numeri più alti da risultati sbagliati oppure "0", questo è codice che ho usato:

#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
long int fattoriale(int n);

using namespace std;
long int a, n;
int scelta;

int main(void)
{
    do{
        printf("Inserire un numero per calcolarne il fattoriale \n");
        scanf("%i", &a);
        printf("Risultato: %i\n", fattoriale(a));
        printf("premere 0 per uscire o un numero qualsiasi per ripere il programma\n");
        scanf("%i", &scelta);
    }
    while(scelta!=0);
}

long int fattoriale(int n)
{
    if(n==0) return(1);
    else return n* fattoriale(n-1);
}

Sapete indicarmi l'errore? grazie in anticipo

[Mettiu_]

Ciao, il tipo long int in C mi pare sia su 32 bit ma il risultato di 13 fattoriale non entra in 32 bit... Puoi provare ad utilizzare double (8 byte di solito) anzichè long int così allarghi l'intervallo di valori "calcolabili"

[Ben Echmeyer]

non ci avevo pensato! grazie!

[clockover]

Fatti restituire un unsigned long e stai apposto per un bel pezzo

[tecno789]

Originariamente inviato da clockover

Fatti restituire un unsigned long e stai apposto per un bel pezzo

quoto, è sicuramente quello il problema!

[WarDuck]

In C long è a 32 bit, long long è presente dallo standard C99 e ti consente di memorizzare interi a 64bit.

Alternativamente puoi usare un double.

[clockover]

Originariamente inviato da WarDuck

In C long è a 32 bit, long long è presente dallo standard C99 e ti consente di memorizzare interi a 64bit.

Alternativamente puoi usare un double.

hai ragione... long long è a 64 bit

comunque meglio sempre usare un metodo iterativo che uno ricorsivo, anche se il fattoriale ricorsivo si fa con una riga

[marco.r]

Originariamente inviato da clockover

hai ragione... long long è a 64 bit

comunque meglio sempre usare un metodo iterativo che uno ricorsivo, anche se il fattoriale ricorsivo si fa con una riga

e perche' mai ?

[tecno789]

Originariamente inviato da marco.r

e perche' mai ?

perchè la ricorsione spreca più memoria, serve un record di attivazione per ogni chiamata , il che vuol dire che il metodo iterativo produce meno garbage anche se è molto più lungo!

[clockover]

Il metodo iterativo è più veloce... sempre. Nel caso del fattoriale non c'è nessun problema, ma diciamo che in generale è preferibile sempre un metodo iterativo. Inoltre per metodi (o funzioni) che richiedono uno stack elevato si rischia anche di occupare troppa memoria e far crashare il programma.

[clockover]

Originariamente inviato da tecno789

perchè la ricorsione spreca più memoria, serve un record di attivazione per ogni chiamata , il che vuol dire che il metodo iterativo produce meno garbage anche se è molto più lungo!

appunto

[Rsk]

Originariamente inviato da tecno789

perchè la ricorsione spreca più memoria, serve un record di attivazione per ogni chiamata , il che vuol dire che il metodo iterativo produce meno garbage anche se è molto più lungo!

Altrimenti si può fare così

Tail recursive

long fact(long res, long n){
if n==1 return res
return fact(res*n,n-1)
}

[GByTe87]

Originariamente inviato da tecno789

...il metodo iterativo produce meno garbage anche se è molto più lungo!

int n = 6, f;
for (f = n, n--; n > 0; f *= n--);

Due righe.

[L4ky]

Puoi recuperare ancora un bit facendo:

unsigned long long int x;

[tecno789]

Originariamente inviato da GByTe87

int n = 6, f;
for (f = n, n--; n > 0; f *= n--);

Due righe.

bravo.. io sono riuscito a farlo solo in 3
peccato che la ricorsione sia solo 1

comunque era ironico

[marco.r]

Originariamente inviato da tecno789

perchè la ricorsione spreca più memoria, serve un record di attivazione per ogni chiamata , il che vuol dire che il metodo iterativo produce meno garbage anche se è molto più lungo!

Non e' detto. L'unico difetto puo' essere l'esaurimento dello stack, evitabile se il linguaggio e/o il compilatore supporta le ottimizzazioni per la tail recursion (se ricordo bene gcc dovrebbe farlo).
Per quel che riguarda le performance, anche in un esempio semplice come il fattoriale oltre ad un certo punto la cpu passa ben poco tempo nella creazione e cancellazione dello stack di attivazione, quanto a gestire numeri di lunghezza arbitraria.
Non mi viene in mente un esempio piu' semplice al momento, ma se a qualcuno viene in mente possiamo vedere.

[tecno789]

Originariamente inviato da marco.r

Non e' detto. L'unico difetto puo' essere l'esaurimento dello stack, evitabile se il linguaggio e/o il compilatore supporta le ottimizzazioni per la tail recursion (se ricordo bene gcc dovrebbe farlo).
Per quel che riguarda le performance, anche in un esempio semplice come il fattoriale oltre ad un certo punto la cpu passa ben poco tempo nella creazione e cancellazione dello stack di attivazione, quanto a gestire numeri di lunghezza arbitraria.
Non mi viene in mente un esempio piu' semplice al momento, ma se a qualcuno viene in mente possiamo vedere.

il problema non si pone per quanto riguarda le performance visto che il programma è abbastanza corto, ma si pone per la memoria. Ora prendi lo stesso programma fatto in modo iterativo e in modo ricorsivo, compilali e avviali e guarda quanta memoria utilizzano, noterai con molto piacere che quello con la ricorsione utilizza un pò più di memoria, se hai una ram da 512 kb devi stare molto attento

[marco.r]

Originariamente inviato da tecno789

il problema non si pone per quanto riguarda le performance visto che il programma è abbastanza corto, ma si pone per la memoria. Ora prendi lo stesso programma fatto in modo iterativo e in modo ricorsivo, compilali e avviali e guarda quanta memoria utilizzano, noterai con molto piacere che quello con la ricorsione utilizza un pò più di memoria, se hai una ram da 512 kb devi stare molto attento

Una chiamata ricorsiva con tail call ottimizzata consuma spazio costante sullo stack. Ovviamente occorre che ci sia effettivamente la tail call, e nel caso del fattoriale non e' molto pratico. Ma visto che se ne faceva un discorso generale...

[tecno789]

Originariamente inviato da marco.r

Una chiamata ricorsiva con tail call ottimizzata consuma spazio costante sullo stack. Ovviamente occorre che ci sia effettivamente la tail call, e nel caso del fattoriale non e' molto pratico. Ma visto che se ne faceva un discorso generale...

capisco...no ma infatti non ho detto niente, ho esposto quanto da me studiato e cerco sempre di imparare cose nuove, quello che tu mi hai detto non lo sapevo.

[demos88]

Per il calcolo del fattoriale bisognerebbe usare una variabile intera perchè per definizione il fattoriale è una funzione da naturale a naturale quindi un unsigned long sarebbe la scelta più coerente "matematicamente".
Tuttavia anche con un unsigned long, raggiungi l'overflow molto presto.
Il long double è assolutamente più capiente in quanto la virgola mobile usa una notazione approssimata esprimendo il valore come mantissa e esponente. Però proprio questa approssimazione, che tipicamente non è esatta nemmeno per valori interi, ti darà un risultato del fattoriale approssimato.
L'alternativa è usare librerie ad-hoc come http://gmplib.org/