/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
   fattoriale.c
   Programma per il calcolo di tutte le cifre del fattoriale di un
   intero positivo (dato come argomento sulla linea di comando).
   >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* =================================================================
   Definiamo ora il tipo "interone_pos" che serve per rappresentare un 
   intero positivo con un numero elevato di cifre.  
   Ogni interone_pos consiste in un array "cifrone" di maxc interi ognuno 
   dei quali viene usato per contenere 8 cifre decimali. 
   La variabile numc indica quante  elementi di "cifrone" contengono 
   effettivamente delle cifre del numero.  Vedere esempio qui sotto.
   ================================================================= */
typedef struct {
  int *cifrone;         // contiene elenco cifrone
  int numc;             // numero cifrone;
  int maxc;             // dimensione dell'array cifrone[]
} interone_pos;

/* =========================================================================
   Esempio: 
   se la variabile n contiene il numero 234562819388170012 (diciotto cifre) 
   avremo: 
   n.cifrone[0] = 88170012
   n.cifrone[1] = 45628193
   n.cifrone[2] = 23
   n.numc = 3
   naturalmente l'array cifrone deve contenere almeno 3 elementi, quindi
   deve essere n.maxc >= 3.
   ========================================================================= */

// costante 10^8
#define diecialla8 (100000000)  

// prototipi 
interone_pos moltiplica_ip(interone_pos, int);
void stampa_ip(interone_pos);
void aggiunge_cifra(interone_pos *a);


int main(int argc, char *argv[])
{
  int i,n;
  interone_pos nfatt;

  /* ---- verifica che ci sia esattamente un parametro ------ */
  if(argc!=2) {
    printf("Calcola tutte le cifre di n!\n");
    printf("USO:\n       fattoriale2 n\n");
    exit(1);
  }
  /* ----- controlla che n sia un valore accettabile ---- */
  n = atoi(argv[1]);
  if(n<1 || n>=diecialla8) {
    printf("n deve essere positivo e minore di %d!\n",diecialla8);
    exit(2);
  } 
  // ----------------------------------------------------------------
  // creo l'interone nfatt allocandogli 3 cifre 
  nfatt.maxc = 3;
  nfatt.cifrone = (int *) calloc(nfatt.maxc,sizeof(int));
  if(nfatt.cifrone==NULL) {
    printf("Memoria insufficiente\n");
    exit(3);
  }
  // ----- inizializzo a 1 nfatt ------
  nfatt.cifrone[0]=1;
  nfatt.numc = 1;   
  /* ---------- calcola il fattoriale ---------- */
  for(i=2;i<=n;i++)
    nfatt = moltiplica_ip(nfatt, i);
  printf("%d fattoriale e`:\n", n);
  stampa_ip(nfatt);
  return 0;
}

/* **********************************************************
   moltiplica l'interone_pos contenuto in a per il fattore n
   usiamo il fatto che lavorando il base b il riporto e' sempre < b
   (Nota: sarebbe stato possibile passare un puntatore
    all'interone_pos a, e resituire void)
   ********************************************************** */
interone_pos moltiplica_ip(interone_pos a, int n)
{
  int i;
  long long riporto, somma, nn;

  // verifica che ci sia spazio per una nuova cifra
  if(a.numc == a.maxc) 
    aggiunge_cifra(&a);
  // esegue la moltiplicazione
  nn = (long long) n;           /* converte n in long long */
  riporto=0;
  for(i=0;i<a.numc;i++) {
    somma = riporto + ( nn * a.cifrone[i]);
    a.cifrone[i] = (int) (somma % diecialla8);
    riporto = somma/diecialla8;
  }
  if(riporto!=0) {
    // devo mettere il riporto in una nuova cifra 
    if(a.numc==a.maxc || riporto>= diecialla8) {
      printf("Errore da qualche parte!\n");
      exit(12);
    }
    else {
      a.cifrone[a.numc] = (int) riporto;  // nuova cifrona
      a.numc++;                           // aumenta numero cifrone
    }
  }
  return a;
}


// aggiunge lo spazio per una cifra
void aggiunge_cifra(interone_pos *a) 
{
  a->maxc += 1;     // la scrittura a->maxc e' equivalente a (*a).maxc 
  a->cifrone = (int *) realloc(a->cifrone,a->maxc*sizeof(int));
  if(a->cifrone==NULL) {
    printf("Memoria insufficiente\n");
    exit(11);
  }
}

/* *********************************************************
   stampa interone_pos contenuto in a
   (Nota: sarebbe stato possibile passare solo un puntatore ad a)
   ********************************************************** */
void stampa_ip(interone_pos a)
{
  int i;
  printf("%d",a.cifrone[a.numc-1]);
  for(i=a.numc-2;i>=0;i--)
    printf("%08d",a.cifrone[i]);
  printf("\n");
}