title: Algorithm Challenge: Generate Continued Fractions for a float
body: <p><em>(<strong>EDIT</strong>: In response to grumpy comments, No it isn't homework. I am working on pitch detection, taking an array of potential harmonic peaks,  and attempting to construct candidates for fundamental frequency. So, it is actually a very practical question.)</em> </p>
  
  <p>Consider the best fractional approximations for (eg) pi,  ordered by increasing denominator: 3/1, 22/7, 355/113, ...</p>
  
  <p>Challenge: create a <em>tidy</em> C algorithm that will generate the n'th quotient approximation a/b for a given float, returning also the discrepancy.</p>
  
  <p>calcBestFrac(float frac, int n, int * a, int * b, float * err) {...}</p>
  
  <p>The best technique I believe is <strong>continued fractions</strong></p>
  
  <p>Take away the fractional part of pi, and you get 3<br>
  Now, the remainder is 0.14159... = 1/7.06251..</p>
  
  <p>So the next best rational is 3 + 1/7 = 22/7<br>
  Take away the 7 from 7.06251 and you get 0.06251.. Roughly 1/15.99659..</p>
  
  <p>Call it 16, then the next best approximation is<br>
  3 + 1/(7 + 1/16) = 355/113</p>
  
  <p>However, this is far from trivial to convert into clean C code.   I will post if I get something tidy.  In the meanwhile, someone may enjoy it as a brainteaser.</p>