#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef int* reg;

double  PHI = 1.618034;
int  Ndits  = 10;
int  DPC    = 0;

int digits( int n )
{
  return 1 + n * log( PHI ) / log(10);
}

void add( reg d, reg x, reg y )
{ int ret=0;
  int i;
  for( i = 0; i < Ndits; i++) {
    ret = x[i] + y[i] + ret;
    if ( ret > 9  ) {
      d[i] = ret - 10;
      ret  = 1;
    }  
    else { d[i] = ret; ret = 0;}
  }
  DPC |= (ret > 0 );
}

void copie( reg d, reg s )
{
  int i;
  for( i = 0; i < Ndits; i++)
    d[i] = s[i];

}


void inc( reg x )
{ int i = 0;
  while ( ( i < Ndits) && x[i]==9 ) {
    x[i] = 0;
    i++;
  }
  if ( i < Ndits) x[i]++;
  else DPC = 1;
}

reg  zero( void )
{ reg res; 
  res = ( reg ) calloc( Ndits, sizeof(int) );
  return res;
}



 void print( int n, reg x )
{ int i = Ndits - 1; 
  printf("\nF(%d)=", n);
  while ( i > 0 && x[i] == 0 ) i--;
  while ( i >=0 ) {
    printf("%d", x[i]);
    i--;
  }
}




int main( int argc, char* argv[] )
{ 
  reg a, b, c;
  int n, i;
  n = atoi( argv[1] );
  Ndits = digits( n );
  a = zero();
  b = zero();
  c = zero();
  inc( b );
  
  printf("\nTaille des registres : %d", Ndits);
  for( i = 1; i < n; i++) {
    add( c, b , a);
    copie( a, b);
    copie( b, c);
  }
  if ( argc == 2)  print( i, b );
  if ( DPC ) printf("\nDepassement de capacite !");
  
  free(a); 
  free(b); 
  free(c);
  
  printf("\n");
  return 0;
}

/*
 * [langevin@ou812 tp2]$ time ./reg.exe 10000 s
 *
 * Taille des registres : 2279
 *
 * real    0m3.986s
 * user    0m3.979s
 * sys     0m0.007s
 *
 * [langevin@ou812 tp2]$ time ./reg.exe 20000 s
 *
 * Taille des registres : 4558
 * 
 * real    0m16.182s
 * user    0m16.181s
 * sys     0m0.006s
 *
 *===============================================
 * Le temps de calcul de F_N est quadratique en N.
 *===============================================
 *
 */