analytics

Thursday, May 10, 2012

Estimating square roots, generalized continued fraction expression for every square root

If you look at this formula:
You can see that this equation always holds no matter the a. So you can do something like the following to figure out the square root of a number, here for example is finding the square root of 10 using the top formula:

The two sides will equal exactly when you iterate an infinite number of times substituting in what is already on the right side for the square root of 10 that appears on the right side. The above is 6 iterations and shows that square root of 10 is somewhere near: 3.0983... which is close to the real value of 3.162...


Thus there is one general continued fraction expression for every square root.

Normally the discussion of continued fractions explores each square root as having a different form, such as on wikipedia http://en.wikipedia.org/wiki/Square_root


The have tables of how this looks for every different possible square root:

But this idea I've had gives the same form for every square root.

2 comments:

  1. If A is the closest integer root to X and B=(X - A*A) then A plus (B over (2A plus (B over (2A ...)))) is another form. It has the advantage over yours that for general numbers it doesn't have to consume as many pairs in order to start emitting terms. But it has the disadvantage that you still need an integer square root to get started, whereas yours does not have this preliminary calculation.

    Of course, if I were to always estimate the integer square root as "1", well... you be the judge if our continued fractions are then the same. :)

    ReplyDelete
  2. I was looking for a sequence of rational numbers converging to a square root, and your example is straightforward.

    ReplyDelete