Licence 2 INFO/MATHS : TP 1 & 2

#include <stdio.h>
#include <stdlib.h>
 
/**
Fonction calculant la valeur absolue d'un entier
 */
int abs(int x)
{
  return x >= 0 ? x : -x ;
}
 
/**
Fonction calculant le max de deux entiers
 */
int max(int x, int y)
{
  return x >= y ? x : y ;
}
 
 
/**
Fonction calculant le min de deux entiers
 */
int min(int x, int y)
{
  return x >= y ? y : x ;
}
 
/**
Fonction renvoyant le signe d'un entier :
1 si positif, -1 si négatif, 0 si nul.
 */
int sgn(int x)
{
  return x == 0 ? 0 : (x > 0 ? 1 : -1) ;
}
 
 
/**
 Calcul du quotient et du reste de la division euclidienne "from scratch"
 */
void div_euc ( const int a, const int b, int qr[2] )
{
  if ( b == 0 )
    {
      printf( "Division par zéro" );
      exit( 1 );
    }
  int r = a;
  int q = 0;
  while ( r < 0 || r >= abs(b) )
    {
      q = q + sgn(r*b);
      r = r - sgn( r ) * abs( b );
    }
  qr[0] = q;
  qr[1] = r;
}
 
 
/**
Idem mais en "patchant" les opérateurs natifs % et /
 */
void div_euc2 ( const int a, const int b, int qr[2] )
{
   if ( b == 0 )
    {
      printf( "Division par zéro" );
      exit( 1 );
    }
   
  int q = a / b ;
  int r = a % b ;
 
  if (a >= 0 || r == 0)
    {
      qr[0] = q;
      qr[1] = r;
    }
  else
    {
      qr[0] = q - sgn( b );
      qr[1] = r + abs( b );
    }
}
 
 
 
/**
Fonction de test
 */
void test ( const int a, const int b )
{
  int qr[2] = {a,b};
  
  div_euc(a,b,qr);
  
  printf("From scratch : %d = %d * %d + %d\n",a,b,qr[0],qr[1]);
 
  div_euc2(a,b,qr);
  
  printf("Patch        : %d = %d * %d + %d\n",a,b,qr[0],qr[1]);
 
  printf("\n------------------------------\n");
}
 
 
// PGCD exo 1
 
 
/**
Calcul du PGCD avec l'algorithme d'Euclide
 */
void pgcd ( const int a, const int b, int* d )
{
  
  int aa = max(abs(a),abs(b)) ;
  int bb = min(abs(a),abs(b)) ;
 
  if ( aa == 0 )
    {
      fprintf(stderr, "PGCD non défini" );
      exit( 1 );
    }
  else
    {
      int qr[2] = {aa,bb} ;
  
      while ( bb > 0 )
        {
          div_euc (aa, bb, qr) ;
          aa = bb ;
          bb = qr[1] ;
        }
      *d = aa ;
    }
}
      
  
void testPGCD ( const int a, const int b )
{
  int i = 1;
  int* dd = &i;
  
  pgcd (a, b, dd );
  printf("PGCD( %d, %d ) = %d\n", a, b, *dd);
}
 
 
 
 
 
 
// bezout exo 4
 
 
void bezout ( const int a, const int b, int duv[3] )
{
  int aa = abs( a ) ;
  int bb = abs( b ) ;
  int u  = 1 ; 
  int v  = 0 ;
  int uu = 0 ;
  int vv = 1 ;
  int qr[2] = {aa, bb} ;
 
  while ( bb > 0 )
    {
      div_euc (aa, bb, qr);
      int q = qr[0] ;
      int r = qr[1] ;
      aa = bb ;
      bb = r ;
      int utmp = u - q*uu ;
      u  = uu ;
      uu = utmp ;
      int vtmp = v - q*vv ;
      v  = vv ;
      vv = vtmp ;
    }
  duv[0] = aa ;
  duv[1] = sgn(a) * u ;
  duv[2] = sgn(b) * v;
}
 
 
 
 
void bzt ( const int a, const int b, int duv[3] )
{
  int aa    = abs( a ) ;
  int bb    = abs( b ) ;
  int u     = 0 ; 
  int v     = 1 ;
  int g     = bb ;
  int qr[2] = {0, 0} ;
  int r, rr, q, qq ;
 
  do {
    div_euc( aa, g, qr );
    q = qr[0] ;
    r = qr[1] ;
    if ( r > 0 )
      {
        g = r ;
        u = 1 - q * u ;
        v = - q * v ;
      }
    div_euc( bb, g, qr );
    qq = qr[0] ;
    rr = qr[1] ;
    if ( rr > 0 )
      {
        g = rr ;
        u = - qq * u ;
        v = 1 - qq * v ;
      }
  }
  while ( ( r > 0 ) || ( rr > 0 ) ) ;
  duv[0] = g ;
  duv[1] = sgn(a) * u ;
  duv[2] = sgn(b) * v;
}
 
 
 
 
 
 
void testBezout ( const int a, const int b )
{
  int duv[3]  = {0,0,0} ;
  int dduv[3] = {0,0,0} ;
  
  bezout ( a, b, duv ) ;
  bzt ( a, b, dduv ) ;
  printf("Bezout : ( %d * %d ) + (%d * %d ) = %d\n", a, duv[1], b, duv[2], duv[0]);
  printf("Bzt    : ( %d * %d ) + (%d * %d ) = %d\n", a, dduv[1], b, dduv[2], dduv[0]);
  printf("\n------------------------------\n");
  
}
void inv_mod (const int n, const int x, int resultat[2] )
{
  int duv[3]      = {0,0,0} ;
 
  bezout (x, n, duv) ;
  
  if ( n > 0 )
    {
      int d = duv[0] ;
      if ( d == 1 )
        {
          int u = duv[1];
          int qr[2] = {0,0};
          div_euc(u, n, qr) ;
          resultat[0] = qr[1] ;
          resultat[1] = 0 ;
        }
      else
        {
          resultat[0] = d ;
          resultat[1] = 1 ;
        }
    }
    else
      {
        resultat[0] = -1 ;
        resultat[1] =  2 ;
      }
}
 
 
 
void testInv ( const int x, const int n )
{
  int resultat[2]  = {0,0} ;
  
  inv_mod ( x, n, resultat ) ;
  printf("Diagnostic : %d, u : %d \n", resultat[1], resultat[0]);
  printf("\n------------------------------\n");
  
}
 
 
 
 
///////////////////////////////////////////////////////////////////
//
//           T P 2
//
//////////////////////////////////////////////////////////////////
 
 
 
// Exo 1
 
 
void multi_pgcd ( const int n , int* a , int d[1] )
{
  pgcd ( a[0], a[1], d) ;
  for (int i = 2 ; i < n ; i++ )
    pgcd( d[0] , a[i] , d ) ;
}
 
 
  
void testPGCDmult ( const int n, int * a )
{
  int d[1] = {1};
  
  multi_pgcd (n, a, d );
  printf("PGCD_mult = %d\n",  d[0]);
}
 
 
 
 
// Exo 2
 
void puissance ( const int n , const int x , const int p , int z[2] )
{ 
  if ( (n > 0) && (p >= 0) )
    {
      int qr[2] = {0 , 0} ;
      div_euc ( x , n , qr ) ;
      int tmp    = qr[1] ;
      int pp    = p ;
      int res   = 1 ;
      z[1]      = 0 ;
      while (pp > 0)
        {
          if ( pp % 2 == 0 )
            {
              div_euc (tmp  * tmp , n , qr ) ;
              tmp = qr[1] ;
              pp  = pp / 2 ;
            }
          else
            {
              div_euc ( res * tmp , n , qr ) ;
              res = qr[1] ;
              pp  = pp - 1 ;
            }
        }
      z[0] = res ;
    }
  else
    {
      if ( n <= 0 )
        {
          fprintf(stderr, "modulo négatif\n ") ;
          z[1] = 1 ;
        }
      else
        {
          fprintf(stderr, "puissance négative\n ") ;
          z[1] = 2 ;
        }
    }
}
 
 
void testPower ( const int n , const int x , const int p )
{
  int z[2] = { 0 , 0 } ;
  puissance ( n ,  x , p , z ) ;
  if ( z[1] == 0 )
    printf ("%d ^ %d [ %d ] = %d\n", x , p , n , z[0] ) ;
}
 
 
 
 
// exo 3
 
void affichage ( const int n , long int* x )
{
  printf ( "%ld" , x[n - 1] ) ;
  for ( int i = n - 2 ; i >= 0 ; i-- )
    {
      printf( ":%09ld" , x[i] );
    }
  printf("\n");
}
 
 
 
 
 
 
 
 
 
 
 
// exo 4
 
int somme ( const int n , long int* x , const int p , long int* y , long int* z )
{
  int i ;
  long int t   = 1000000000 ;
  long int ret = 0 ;
  long int s   = 0 ;
  long int* nb_min ;
  long int* nb_max ;
  int t_mini ;
  int t_maxi ;
  if ( n >= p )
    {
      nb_min = y ;
      nb_max = x ;
      t_mini  = p ;
      t_maxi  = n ;
    }
  else
    {
      nb_min = x ;
      nb_max = y ;
      t_mini  = n ;
      t_maxi  = p ;
    }
  
  for ( i = 0 ; i < t_mini ; i++ )
    {
      s    = nb_min[i] + nb_max[i] + ret ;
      z[i] = s % t ;
      ret  = s / t ;
    }
 
  for ( i = t_mini; i < t_maxi ; i++ )
    {
      s = nb_max[i] + ret ;
      z[i] = s % t ;
      ret = s / t ;
    }
 
  if ( ret == 0 )
    {
      return t_maxi ;
    }
  else
    {
      z[t_maxi] = ret ;
      return t_maxi + 1 ;
    }
}
 
 
// exo 5
 
int produit ( const int n , long int* x , const int p , long int* y , long int* z )
{
  long int t   = 1000000000 ;
  long int ret = 0 ;
  long int s   = 0 ;
 
  for ( int k = 0 ; k < n + p ; k++ )
    z[k] = 0 ;
  
  for ( int i = 0 ; i < n ; i++ )
    {
      for ( int j = 0 ; j < p ; j++ )
          z[i + j] += x[i] * y[j] ;
    }
 
  for ( int k = 0 ; k < n + p - 1; k++ )
    {
      s    = z[k] + ret ;
      z[k] = s % t ;
      ret  = s / t ;
    }
 
  if ( ret == 0 )
    {
      return n + p - 1 ;
    }
  else
    {
      z[n + p - 1] = ret ;
      return n + p ;
    }
}
 
 
 
 
 
  
 
int main (void)
{ 
 
  // TP 1
 
  
  /* test(  17,  3 ); */
  /* test(  17, -3 ); */
  /* test( -17,  3 ); */
  /* test( -17, -3 ); */
 
  /* test(  18,  3 ); */
  /* test(  18, -3 ); */
  /* test( -18,  3 ); */
  /* test( -18, -3 ); */
 
 
  /* testPGCD(17,3); */
  /* testPGCD(-112,12); */
  /* testPGCD(0,112); */
  /* testPGCD(112,0); */
  /* //testPGCD(0,0); */
 
  /* testBezout(19,15); */
  /* testBezout(-19,15); */
  /* testBezout(19,-15); */
  /* testBezout(19,0); */
 
  /* testInv(5,2); */
  /* testInv(-5,2); */
  /* testInv(15,3); */
  /* testInv(15,-3); */
  /* testInv(5,0); */
  /* testInv(0,5); */
 
 
  // TP 2
 
  // exo1
  
  /* int a[5] = {18 , 15 , 27 , 36 , 72} ; */
  /* testPGCDmult( 5 , a) ; */
 
  /* int b[2] = { 27 , 36} ; */
  /* testPGCDmult( 2 , b) ; */
 
  /* int c[3] = {18 , 24, 0} ; */
  /* testPGCDmult( 1 , c) ; */
 
 
  // exo 2
 
  /* testPower( 3 , 2 , 11121214 ) ; */
  /* testPower( -3 , 2 , 11121214 ) ; */
  /* testPower( 3 , -2 , 11121214 ) ; */
  /* testPower( 3 , 2 , -11121214 ) ; */
 
 
  // exo 3
 
  /* long int x[3] = { 123456789 , 456 , -789 } ; */
  /* affichage ( 3 , x ) ; */
  /* long  int xx[1] = { 123456789 } ; */
  /* affichage ( 1 , xx ) ; */
 
  /* // exo 4 */
 
  long int na[5] = { 1234, 123456789 , 123456789, 123456789 , 123000000 } ;
  long int nb[8] = { 987654321, 987654321 , 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 } ;
  long int ns[14] = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0} ;
 
  int t = somme ( 5 , na , 8 , nb , ns ) ;
  printf("na = \n");
  affichage( 5 , na ) ;
  printf("nb = \n");
  affichage( 8 , nb ) ;
  printf("na + nb = \n");
  affichage( t , ns ) ;
  printf("na * nb = \n");
  int tt = produit  ( 5 , na , 8 , nb , ns ) ;
  affichage( tt , ns ) ;
 
  
  return 0;
}