Optimal algorithm to calculate the result of a continued fraction

A开发者_Go百科 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?

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).

I'd like to elaborate a bit on DVK's excellent answer. I'll stick with his notation f(d,s) to denote the sought value for depth d.

If you calculate the value f(d,s) for large d, you'll notice that the values converge as d increases.

Let φ=f(∞,s). That is, φ is the limit as d approaches infinity, and is the continued fraction fully expanded. Note that φ contains a copy of itself, so that we can write φ=1+1/φ. Multiplying both sides by φ and rearranging, we get the quadratic equation

φ² - φ - 1 = 0

which can be solved to get

φ = (1 + √5)/2.

This is the famous golden ratio.

You'll find that f(d,s) is very close to φ as d gets large.

But wait. There's more!

As DVK pointed out, the formula for f(d,s) involves terms from the Fibonacci sequence. In particular, it involves ratios of successive terms of the Fibonacci sequence. There is a closed form expression for the nth term of the sequence, namely

(φⁿ-(1-φ)ⁿ)/√5.

Since 1-φ is less than one, (1-φ)ⁿ gets small as n gets large, so a good approximation for the nth Fibonacci term is φⁿ/√5. And getting back to DVK's formula, the ratio of successive terms in the Fibonacci sequence will tend to φⁿ⁺¹/φⁿ = φ.

So that's a second way of getting to the fact that the continued fraction in this question evaluates to φ.

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

(In other words - loop it!)

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