/*----------------------------------------------------------*/
/*                                                          */
/*         AUTHOR : Eric VIOLARD                            */
/*         E-MAIL : violard@icps.u-strasbg.fr               */
/*         ORGANISM : Université Louis Pasteur (Strasbourg) */
/*         CREATION : 23/11/02                              */
/*                                                          */
/* ---------------------------------------------------------*/
  
#include <grand_entier.h> 
#include <stdio.h> /* pour utiliser les fonctions printf et scanf */
 
/* --- Définition du type des grands entiers --- */

/* munis des opérations : 

  - construction d'un grand entier (de type grand_entier) 
    à partir d'un entier (de type int)
  - nombre de chiffres d'un grand entier
  - lecture d'un grand entier
  - écriture d'un grand entier
  - addition de 2 grands entiers
  - multiplication de 2 grands entiers

*/
 
grand_entier cons_grand_entier(int n)
     /* conversion d'une valeur de type int en une valeur de type grand_entier */
{
  grand_entier N; /* résultat */
  int quotient10=n; /* quotients des divisions successives de n par 10 (initialement n) */
  int i; /* indices du tableau */  

  /* on parcours tous les chiffres de N en commencant par le chiffre des unités */
  for(i=0;i<MAX_NB_CHIFFRES;i++)
    {
      N.chiffre[i]=quotient10%10; /* quotient10%10 est le chiffre courant de N */  
      quotient10=quotient10/10;   /* mise à jour de quotient10 */     
    }

  return N;
}

int nb_chiffres(grand_entier N)
     /* nombre de chiffres d'un grand entier */
{
  int i=MAX_NB_CHIFFRES; /* indices du tableau (initialement le plus grand indice) */

  /* on parcours chaque chiffre de N (en partant du chiffre le plus à gauche) */
  do
    i--; /* on passe au chiffre suivant */
  while(N.chiffre[i]==0 && i>0); /* tant que le chiffre est 0 */

  /* l'indice du premier chiffre différent de 0 détermine le nombre de chiffres de N */
  return i+1; 
}

grand_entier lecture_grand_entier()
     /* lecture d'un grand entier sur l'entrée standard */
{
  grand_entier N; /* résultat */
  char c; /* caractères lus */ 
  int i=0; /* indices du tableau */ 
  int nb_chiffres; /* nombre de chiffres du résultat */
  
  printf("Entrer un grand entier (terminé par un .) : \n");

  /* saisie de l'entier chiffre par chiffre (chaque chiffre étant représenté par un caractère) */
  /* on remplit le tableau dans l'ordre inverse de la représentation de l'entier */

  scanf(" %c",&c); 
  while(i<MAX_NB_CHIFFRES && c!='.')
    {    
    if((int)c>=(int)'0' && (int)c<=(int)'9')  /* on ne considère que les caractères entre '0' et '9' */ 
      {
      N.chiffre[i]=(int)c-(int)'0'; /* stocke un nouveau chiffre */
      i++; /* passe au chiffre suivant */
      }
    scanf(" %c",&c);
    }
  nb_chiffres=i;

  /* renversement du tableau */
  for(i=0;i<nb_chiffres/2;i++)
    {
      int tmp;

      tmp = N.chiffre[i];
      N.chiffre[i]=N.chiffre[(nb_chiffres-1)-i];
      N.chiffre[(nb_chiffres-1)-i]=tmp;
    }

  /* on complète par des 0 */
  for(i=nb_chiffres;i<MAX_NB_CHIFFRES;i++)
    N.chiffre[i]=0;

  return N;
}

void ecriture_grand_entier(grand_entier N)
     /* écriture d'un grand entier sur la sortie standard */
{
  int i=nb_chiffres(N)-1; /* indices du tableau (initialement l'indice du chiffre le plus à gauche) */

  /* on parcours chaque chiffre de N jusqu'au chiffre des unités */
  for(;i>=0;i--)
    printf("%d",N.chiffre[i]); /* écriture d'un chiffre */
  printf("\n");
}
 
grand_entier somme_grand_entier(grand_entier N1,grand_entier N2)
    /* addition (comme à la main) de 2 grands entiers N1 et N2 */
    /* pré-conditions : nb_chiffres(N1)+1 < MAX_NB_CHIFFRES && nb_chiffres(N2)+1 < MAX_NB_CHIFFRES */
{
  grand_entier N; /* résultat */
  int retenue=0; /* retenue (initialement pas de retenue) */
  int i; /* indices des tableaux */
 
  /* on parcours les chiffres en commencant par le chiffre des unités */
  for(i=0;i<MAX_NB_CHIFFRES;i++)
      {
	int tmp;

        tmp=N1.chiffre[i]+N2.chiffre[i]+retenue; /* on additionne 2 chiffres en ajoutant la précédente retenue */
        N.chiffre[i]=tmp%10; /* on calcule un nouveau chiffre du résultat */
	retenue=tmp/10; /* on retient la retenue pour la prochaine addition */
      }
    
  return N;
}

grand_entier multiple_grand_entier(grand_entier N,int k)
   /* multiplication (comme à la main) d'un grand entier N par un chiffre k */
   /* pré-conditions : 0 <= k <= 9 et nb_chiffres(N)+1 < MAX_NB_CHIFFRES  */
{
  grand_entier M; /* résultat */
  int retenue=0; /* retenue (initialement pas de retenue) */
  int i; /* indices du tableau */

  /* on parcours les chiffres en commencant par le chiffre des unités */
  for(i=0;i<MAX_NB_CHIFFRES;i++)
      {
	int tmp;

        tmp=k*N.chiffre[i]+retenue; /* on multiple le chiffre de N par k en ajoutant la précédente retenue */
        M.chiffre[i]=tmp%10; /* on calcule un nouveau chiffre du résultat */
        retenue=tmp/10;  /* on retient la retenue pour la prochaine multiplication */
      }  
  
  return M;
}


grand_entier puissance10_grand_entier(grand_entier N,int p)    
   /* calcul de N multiplié par (10 puissance p) */
   /* pré-conditions : nb_chiffres(N)+p < MAX_NB_CHIFFRES */
{
  grand_entier M; /* résultat */
  int i; /* indices du tableau */

  /* décalage des chiffres de p positions */
  for(i=MAX_NB_CHIFFRES-p-1;i>=0;i--)
      M.chiffre[i+p] = N.chiffre[i];

  /* ajoute p zéros à la suite des chiffres */
  for(i=0;i<p;i++)
      M.chiffre[i] = 0;

  return M;
}

grand_entier produit_grand_entier(grand_entier N1,grand_entier N2)
   /* produit de 2 grands entiers N1 et N2 */
   /* pré-conditions : nb_chiffres(N1)+nb_chiffres(N2) < MAX_NB_CHIFFRES  */
{
  /* on utilise la formule suivante : N1*N2 = N1*(c0+10*c1+100*c2+...) = N1*c0*10^0 + N1*c1*10^1 + N1*c2*10^2 + ... */

  grand_entier N = cons_grand_entier(0); /* les sommes partielles (initialement 0) */
  int i; /* indices du tableau */

  /* pour chacun des chiffres de N2 */ 
  for(i=0;i<MAX_NB_CHIFFRES-1;i++)
      
    /* on ajoute à N le résultat de (produit de N1 avec le ième chiffre de N2) x (10 puissance i) */
      N = somme_grand_entier(N,
          puissance10_grand_entier(
          multiple_grand_entier(N1,N2.chiffre[i]),i));    

  return N;
}