Optimal algorithm to calculate the result of a continued fraction

Question

A continued fraction is a series of divisions of this kind:

depth   1    1+1/s

depth   2    1+1/(1+1/s)

depth   3    1+1/(1+1/(1+1/s))
  .     .      .           
  .     .      .      
  .     .      . 

The depth is an integer, but s is a floating point number.

What would be an optimal algorithm (performance-wise) to calculate the result for such a fraction with large depth?

Answer 1

Smells like tail recursion(recursion(recursion(...))).

(In other words - loop it!)

Answer 2

I would start with calculating 1/s, which we will call a.

Then use a for-loop, as, if you use recursion, in C, you may experience a stack overflow.

Since this is homework I won't give much code, but, if you start with a simple loop, of 1, then keep increasing it, until you get to 4, then you can just go to n times.

Since you are always going to be dividing 1/s and division is expensive, just doing it one time will help with performance.

I expect that if you work it out that you can actually find a pattern that will help you to further optimize.

You may find an article such as this: http://www.b-list.org/weblog/2006/nov/05/programming-tips-learn-optimization-strategies/, to be helpful.

I am assuming by performance-wise you mean that you want it to be fast, regardless of memory used, btw.

You may find that if you cache the values that you calculated, at each step, that you can reuse them, rather than redoing an expensive calculation.

I personally would do 4-5 steps by hand, writing out the equations and results of each step, and see if any pattern emerges.

Update:

GCC has added tail recursion, and I never noticed it, since I try to limit recursion heavily in C, from habit. But this answer has a nice quick explanation of different optimizations gcc did based on the optimization level.

http://answers.yahoo.com/question/index?qid=20100511111152AAVHx6s

Answer 3

Hint: unroll each of these formulas using basic algebra. You will see a pattern emerge.

I'll show you the first steps so it becomes obvious:

f(2,s) = 1+1/s = (s+1)/s
f(3,s) = 1+1/f(2,s) = 1+(s/(s+1)) = (1*(s+1) + s)/(s+1) = (2*s + 1) / (s + 1)
         /* You multiply the first "1" by denominator */
f(4,s) = 1+1/f(3,s) = 1+(s+1)/(2s+1) = (1*(2*s+1) + (s+1))/(2*s+1) = (3*s + 2) / (2*s + 1)
f(5,s) = 1+1/f(4,s) = 1+(2s+1)/(3s+2) = (1*(3*s+2) + (2s+1))/(3*s+2) = (5*s + 3) / (3*s + 2)

...

Hint2: if you don't see the obvious pattern emerging form the above, the most optimal algorithm would involve calculating Fibonacci numbers (so you'd need to google for optimal Fibonacci # generator).