#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

mpz_t *mpz_array(int number_of_elements);
void mpz_init_array(mpz_t *array,int number_of_elements);
void fraction_expansion(mpz_t *fraction,int expansions);
mpz_t *sqrt_of_two(int expansions);
int main()
{
      char numerator[385],denominator[385];
      int expansions=0,counter=0;
      mpz_t *fraction;

      for(;expansions<=1000;expansions++)
      {
            fraction=sqrt_of_two(expansions);
            gmp_sprintf(numerator,"%Zd",fraction[0]);
            gmp_sprintf(denominator,"%Zd",fraction[1]);
            if(strlen(numerator)>strlen(denominator))
                  counter++;
            free(fraction);
      }
      printf("\n\t%i\n\n",counter);

      return 0;
}
mpz_t *mpz_array(int number_of_elements)
{
      mpz_t *array;

      array=malloc(number_of_elements*sizeof(mpz_t));
      mpz_init_array(array,number_of_elements);

      return array;
}
void mpz_init_array(mpz_t *array,int number_of_elements)
{
      int element=0;

      for(;element<number_of_elements;element++)
            mpz_init(array[element]);
}
void fraction_expansion(mpz_t *fraction,int expansions)
{
      mpz_t product;
      mpz_init_set_si(product,2);

      if(expansions)            
            fraction_expansion(fraction,expansions-1);
      if(expansions%2==0)
      {
            mpz_mul(product,product,fraction[1]);     // 2*denominator
            mpz_add(fraction[0],fraction[0],product); // numerator+=2*denominator
      }
      else
      {
            mpz_mul(product,product,fraction[0]);
            mpz_add(fraction[1],fraction[1],product);
      }
}
mpz_t *sqrt_of_two(int expansions)              // The function approximates the square
{                                               // root of  two  with a  fraction  whose
      mpz_t *fraction=mpz_array(2);             // quotient is  exact  at  least  to the
      mpz_set_si(fraction[0],1);                // first decimal digit (with the minimum
      mpz_set_si(fraction[1],2);                // number of iterations).

      fraction_expansion(fraction,expansions);  // The function  returns the numerator
      if(mpz_cmp(fraction[0],fraction[1])>0)    // and the denominator(not necessarily
      {                                         // in this order) of the fraction that
            mpz_t auxiliary;                    // approximates  the  decimal  part of 
            mpz_init(auxiliary);                // the square  root  of  two  with the 
                                                // specified number of iterations.
            mpz_set(auxiliary,fraction[0]);     // Must be  checked  the  order of the
            mpz_set(fraction[0],fraction[1]);   // returned  elements   (the  fraction
            mpz_set(fraction[1],auxiliary);     // have to be lesser of one).
      }
      mpz_add(fraction[0],fraction[0],fraction[1]);

      return fraction;
}