Effettuare il calcolo del fattoriale di un numero è un’operazione semplice e presto fatta su qualsiasi calcolatore. Bastano poche righe di codice e in pochi istanti si ottiene il risultato.

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

Questa funzione ha un problema, anzi per essere precisi, un limite. La grandezza del numero.

Trattandosi infatti di moltiplicazioni si arriva subito a “sforare” la grandezza dell’unsigned long e l’overflow è alle porte immediatamente:

% fact
Inserisci un intero
10
Il fattoriale di 10 è 3628800      <----- OK
% fact
Inserisci un intero
18
Il fattoriale di 18 è 3396534272   <----- SBAGLIATO
% fact
Inserisci un intero
30
Overflow!

Possiamo dunque provare ad aumentare la grandezza del tipo applicato al risultato; proviamo con un intero a 64 bit:

typedef __int64 uint64;

uint64 fatt64 (uint64 n)
{
  if(n==1||n==0)
    return (1);
  else
    n*=fatt64(n-1);
  return(n);
}
% fact64
Inserisci un intero
10
Il fattoriale64 di 10 è 3628800  <----- OK

% fact64
Inserisci un intero
18
Il fattoriale64 di 18 è 6402373705728000  <----- OK

% fact64
Inserisci un intero
20
Il fattoriale64 di 20 è 2432902008176640000  <----- OK

% fact64
Inserisci un intero
30
Overflow!

Meglio di prima ma il problema non è ancora risolto.

Come fare?

Insegnamo al nostro programma a fare le moltiplicazioni. Anche prima sapeva farle. Non lui però, attenzione. Il processore sa fare le moltiplicazioni, il programma dice solamente al processore di farle. I registri del processore però sono limitati, anche il nostro programma quindi lo è.

Metodo

Creiamo una lista dinamica doppiamente concatenata in cui ogni elemento rappresenta il singolo numero del risultato e poi diciamo al nostro programma di moltiplicare i numeri tra di loro, proprio come ci hanno insegnato alle scuole elementari. In questo modo, teoricamente parlando, la lunghezza del risultato è solo limitata dalla quantità di memoria a disposizione!.

 for(n = 1; n <= N; n++)
 {
   remain = carry = 0;

   /* Processa gli elementi uno ad uno fino alla fine della lista */
   for (p = factList.head; p->next != NULL; p = p->next) {
     result = p->data * n + carry;
     if(result >= 10){
       remain = result % 10;
       carry = result / 10;
       p->data = remain;
     }
     else{
       p->data = result;
     }
     carry = result / 10;
   }

   result = p->data * n + carry;


   while(result >= 10){
         p->data = result % 10;  /* resto */
         result = result / 10;
         addNodeListNode(&factList, newNode(0));
     p = p->next;
   }

Et voilà:

% anyfact
Inserisci il numero:10
3628800

oppure

3.6288E6
% anyfact
Inserisci il numero:18
6402373705728000

oppure

6.4023E15
% anyfact
Inserisci il numero: 20
2432902008176640000

oppure

2.4329E18
% anyfact
Inserisci il numero:30
265252859812191058636308480000000

oppure

2.6525E32
% anyfact
Inserisci il numero:70
11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000

oppure

1.1978E100

E così via…

Nota: Questo metodo può ovviamente essere adattato a qualsiasi tipo di operazione basata su moltiplicazioni molto grandi (elevazione a potenza…).

Allegati