PROJECT EULER SOLUTION # 57

Solution to problem number 57 of Project Euler.

Question # 57

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.
In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Solution # 57

/**********************************************************************************/

#include<stdio.h>

#include<time.h>

#include<conio.h>

#include<math.h>

#include<stdlib.h>

int n[1000],d[1000],tmp[1000];

void new_d();

void new_n();

int countDigits(int*);

int main()

{

       int i,j,k,counter=0;

       for(i=0;i<1000;i++)

              n[i]=d[i]=tmp[i]=0;

       n[999]=3;

       d[999]=2;

       for(k=1;k<1000;k++)

       {

             

              new_d();

              new_n();

              for(j=0;j<1000;j++)

                     d[j]=tmp[j];

              if(countDigits(n)>countDigits(d))

                     counter++;

       }

       printf("\nANSWER = %d\n",counter);

       printf("\nEXECUTION TIME = %f\n",clock()/(float)CLK_TCK);

       system("pause");

}

void new_n()

{

       int i;

       for(i=0;i<1000;i++)

              n[i]=d[i]+tmp[i];

       for(i=999;i>0;i--)

       {

              if(n[i]>9)

              {

                     n[i]%=10;

                     n[i-1]+=1;

              }

       }

}     

/* this function stores the

new denominator in tmp array*/

void new_d()

{

       int i;

       for(i=0;i<1000;i++)

              tmp[i]=n[i]+d[i];

       for(i=999;i>0;i--)

       {

              if(tmp[i]>9)

              {

                     tmp[i]%=10;

                     tmp[i-1]+=1;

              }

       }

}     

int countDigits(int *arr)

{

       int i;

       for(i=0;i<1000;i++)

              if(arr[i]!=0)

                     break;

       return (1000-i);

}

/**********************************************************************************/