Talk:Continued fraction
|
|
According to the quite long tradition in number theory notation for a continued fraction is in between < and > brackets, so I do belive there's no need useing [ and ] brackets.
XJam [2002.04.02] 2 Tuesday (0)
I have seen brackets more often. I don't think it makes much of a difference though. AxelBoldt
I can barely follow this page. Firstly, the way it reads, it says that by choosing suitable values, a fraction can be made to equal or at least approach any number. So what? It is in no way clear as to how these numbers are chosen, and the demonstration of finding a series that converges on Pi makes no sense at all. It's like something is being assumed in the discussion that I'm not privy to. Also I wonder if anyone could add to it and say why the theorem was created in the first place - what problem did it solve?
- As a minor contributor to this page, I decide to attempt a response to the comment above. A continued fraction is just another way to represent a number - on a par with the decimal system or Egyptian fractions. There is a clearly defined way to calculate the elements an in the continued fraction representation of any given number; this method is demonstrated in the π example, but it might help if the article explained it more directly. The continued fraction representation for some numbers is finite; for others it is infinite. The continued fraction representation for some numbers exhibits a pattern; for others it is apparently random. Continued fractions are of interest to mathematicians because they arise in the Euclidean algorithm for finding the greatest common denominator of two numbers, and they can be used to find the "best" rational approximations to a given number (this is mentioned in the π example, but again could perhaps be made clearer). Gandalf61 13:23, May 18, 2004 (UTC)
- I agree that the page needs some better explanation for the general reader. A lot of wikipedia's math articles explain the what but not the why. I will try to add some better explanation this week. -- Dominus 14:16, 18 May 2004 (UTC)
- I have added a section that tries to explain why continued fractions are considered to be interesting. -- Dominus 15:10, 18 May 2004 (UTC)
It looks like there's an error in the "Infinite continued fractions" section. The final step listed seems to be missing an a0 from the pn-1 generation. I think the real sequence should be the following:
- <math>
\frac{a_0}{1},\qquad \frac{a_0a_1+1}{a_1},\qquad \frac{ a_2(a_0a_1+1)+a_0}{a_2a_1+1},\qquad \frac{a_3(a_2(a_0a_1+1)+a_0)+(a_0a_1+1)}{a_3(a_2a_1+1)+a_1} <math>
Anyone else agree? -- Rckenned 15:41, 14 Jul 2004 (UTC)
- I agree - and I have fixed it. Gandalf61 16:33, Jul 14, 2004 (UTC)
- Seems that it is not totally fixed: the recursive formulae for h_n and k_n are wrong. The h_{n-1} and k_{n-1} need to be exchanged. Dscho 16:44, 8 Jun 2005 (UTC)
| Contents |
Looking a bit bare
The page seems to be missing a lot of fundamental theorems to continued fractions and continued fraction expansions. I will try my best over the upcoming Easter holiday to get my notes out and starting putting some useful ones up (and some of the proofs if they are small enough). Also it is very much lacking examples and approaches to finding continued fractions, I will try my best to add some of these as well. Can anyone think of anything else that needs adding? Because I just finished a course in this so a lot of the material is fresh in my mind. zurtex
Need for an expanded definition
A few comments.
The definition of continued fractions here is too narrow. First of all, continued fraction theory is divided into analytic and arithmetic theory. The entry here is devoted entirely to arithmetic theory. In analytic theory, which is the focus of about half of the research, the numerators are not confined to being one. In fact, it is best to consider a continued fraction to be a formal expression of indeterminates (with numberator and denominator indeterminates.) For an infinite continue fraction, the indeterminates are taken in a complete normed field so that convergence can be defined. Continued fractions with elements from p-adic fields, formal Laurent series fields etc, have all been considered. These all fall outside of even the analytic and arithmetic categories I have mentioned above. With just formal indeterminates, continued fractions are even studied combinatorially. See the work of Flajolet, for example. BTW, for information purposes, I will mention that analytic theory refers to complex analysis, that is, calculus in the complex plane. So in this HUGE area of research, the elements of the continued fractions are assumed to be complex numbers. (Indeed, continued fractions are often viewed as products of fractional linear transformations, which are beautifully understood in the context of the complex plane.)
The associated entry on "generalized continued fractions" is even more naive. The expressions there are what are generally refered to as continued fractions, only the elements of the expression are not confined to being integers; indeed even in some of the examples given, for instance for exp(x), x is given as being complex, contraticting the earlier statement that the elements of the continued fraction being integers. I could go on about that entry, but I wont. Suffice it to say that today in mathematics, generalized continued fractions refer to several different things, among them: matrix continued fractions-- see the work of Levrie, and branched or branching continued fractions.
I wish I had time to write a complete entry on continued fractions, but I do not.
Here are some book suggestions for those enthusiastic about updating this entry. PLEASE have a look at the following books:
The best reference on the subject is:
1) "Continued Fractions with Applications", by Lisa Lorentzen and Haakon Waadeland, North Holland, 1992. (This covers analytic theory and a bit of arithmetic theory.)
On the arithmetic side, a great reference is:
2) "Continued Fractions" by Andrew M. Rockett and Peter Szusz. World Scientific, 1992. (This is a relatively up-to-date treatment of arithmetic theory.)
Older but good references are:
3) "Continued Fractions Analytic Theory and Applications", by William B. Jones and W.J. Thron. Addison-Wesley, 1980. (Analytic theory and history covered here.)
4) "Analytic Theory of Continued Fractions" by H.S. Wall. Chelsea, 1973. (Analytic theory).
5) "Die Lehre Von Den Kettenbruchen" Band I, II, by Oskar Perron, B.G. Teubner, 1954. (These two volumes cover both analytic and arithmetic theory and were written by the world's foremost expert on continued fractions of that day, also, I might add, a mathematician of great renown.)
Well, take care all. I am happy that people have taken the trouble to write an entry in wikipedia on continued fractions, a subject that has been near and dear to my heart for over 26 years.
- Hi, yes,I agree the definition should be expanded. And several more quick remarks:
- Please sign & date, don't post anonymously.
- If this has really been near-n-dear for 26 years, surely you have a few hours to spare for your true love?
- I'll copy the references over.
linas 03:22, 5 Jan 2005 (UTC)
Sorry for not signing or dating my comment.
I am q-analogue on Wikipedia. The date of my comment was (I believe Jan 4 2005).
To write up a full encyclopediac entry would take me, I believe, about 2 hours a day for a month or so. This is because the field is vast and certain parts technical. To work in the gradation from elementary description (usefull to most wikipedia users) to full technical coverage would be a big undertaking. Another obsticle is that I am not familiar with how to "typset" within the software of Wikipedia. Indeed, it took me the better part of 15 minutes to figure out how to put in my first comments. Maybe I need to look at the tutorials again, its been a few months. Anyway, I am certainly willing to help on this entry and would like to see it improved. Continued fractions are a great entry point into mathematical discovery and research, they are at once elementary enough that they can be understood by many people, while at the same time there are still a ton of unsolved problems about them vexing professional mathematicians today. Also, they have applications to a great many applied subjects.
Anyway, I would be happy to devote a few hours to this entry. I'm just not sure how to do that....
q-analogue
Jan 5, 2005
wormarmalade@gmail.com
Hi q-analogue.
I'll pitch in here. I wrote most of generalized continued fraction. I'm sure that anything you write will be of value. Just write what you want to, and if it's not brilliant prose (or probably even if it is!), wikipedians such as myself and linas will rehash it and revise it. Don't worry about formatting. Noone will mind if things aren't quite right.
Don't worry about any of your writing having bits missing, and don't worry about not writing a perfectly formed mathematical treatise off the bat. Just write a little bit and see what happens. Be bold! The beauty of wiki is that someone will fill in the bits. Just write what you want, when you get a minute.
(you can sign of with four tildes together to datestamp your comments).
best
Robinh 13:36, 5 Jan 2005 (UTC)
Hi, that sounds good to me.
I'll start with the usual definitions. I am used to useing LaTeX, so my mathematics will be in that form. Hope someone can read it. I will put side comments, not part of the article, in double parentheses which will contain further information that needs to be linked in, etc, or stuff I don't know how to do with the wiki format or html, or just comments on what I write.
A continued fraction is an expression of the form
(*) b_0 + \frac{a_1}{b_1 + \frac{a_2}{b_2+\frac{a_3}{b_3+\dots}}},
((Notes: The expression requires an equation number in place of the (*) I have used. Also, in the articles so far you have a_i=1 and b_i = a_i in my expression. Some books do this, but the case b_i=1 occurs just as often in continued fractions, and having the a's and b's inverted looks strange to the eye. The way I have written it is predominant.))
where the sequences \{a_i\} and \{b_i\} are usually taken to be elements of a field ((link to wikipedia article defining fields)), or are taken to be inderminates. Usually, the field is assumed to be complete ((wiki link needed)) and equipped with a norm ((wiki link needed)). In most cases, the sequences are complex numbers. ((wiki link needed)). The sequences \{a_i\} and \{b_i\} are refered to as the elements of the continued fraction (*).
Regular or simple continued fractions are the case in which a_i=1 and the b_i are natural numbers, with the exception of b_0, which is allowed to be 0.
((Note, the article on cfs so far in wiki is really about regular continued fractions.))
There exists a considerable body of research on how to give meaning to (*). The standard approach is to define the sequence of approximants \{f_n\} to (*) to be the rational functions ((wiki link needed))
(**) f_n= b_0 + \frac{a_1}{b_1 + \frac{a_2}{b_2+\frac{a_3}{b_3+\dots \frac{a_n}{b_n}}}}.
The continued fraction (*) is then said to converge if \lim_{n\to\infinity} f_n exists. When this limit exists, it is defined to be the value of the continued fraction (*). A more encompassing defintion of convergence in the case of complex elements was given by Lisa Lorentzen (ne Jacobsen) in 1986 who created the idea of general convergence of continued fractions. ((Her seminal paper "General convergence for continued fractions" was published in Transactions of the American Mathematical Society in Volume 294, no 2, pages 477-485. Her name on the paper is Lisa Jacobsen.))
An expression such as the right hand side of (**) is usually refered to as a finite continued fraction.
((Well, that covers the basic defintions with the exception of convergents. I'll try to add more in a bit.))
q-analogue
Q-analogue 21:42, 5 Jan 2005 (UTC)
Couple of quick notes.
Diagonal dots should be used in place of \dots. Also, for regular continued fractions, b_0 is allowed to be negative when one is considering the regular continued fractions of negative real numbers.
q-analogue Q-analogue 21:52, 5 Jan 2005 (UTC)
A note on a topic of brackets for regular continued fractions. Square brackets are indeed more usual in publications today. Just look at a few issues of the Journal of Number Theory or Acta Arithmeticae. Angle brackets are used, but they are in the minority.
Q-analogue 09:17, 6 Jan 2005 (UTC)
Gandalf claims that 3.245 is [ 3 ; 4 , 12 , 4]
While I claimed that 3.245 is [ 3 ; 4 , 12 , 4, 1]
Can someone please resolved this dispute.
Please ignore this. I did the calculations myself and Gandalf was right and I was wrong. [ 3 ; 4 , 12 , 4] = 649/200 = 3.245 exact [ 3 ; 4 , 12 , 4, 1] = 808/249 = 3.24497992
Ohanian 23:49, 2005 Apr 5 (UTC)
Is there an algorithm for converting continued fractions into fractions?
For example: [ 3 ; 4 , 12 , 4 ] -> 649/200
The reason I asked is that I wanted to do
addition, subtraction , multiplication and division
with continued fractions.
Ohanian 05:06, 2005 Apr 6 (UTC)
- There is such an algorithm, but you can do arithmetic on continued fractions without first turning them into fractions. I have been meaning to write a Wikipedia article about this for some time. Until then, you could take a look at [Arithmetic With Continued Fractions (http://www.plover.com/~mjd/cftalk/)], which also has references to more detailed explanations. Dominus 16:02, 6 Apr 2005 (UTC)
| <math>X_{old} = \frac{N_{old}}{D_{old}}<math> | (1) | Let <math>X_{old}<math> be a rational number. ie <math>X_{old}=\frac{649}{200}<math> | |
| <math>X_{new} = \frac{N_{new}}{D_{new}}<math> | (2) | Let <math>X_{new}<math> be a different rational number. | |
| <math>X_{old} = P + \frac{1}{X_{new}}<math> | (3) | Let <math>X_{old}<math> be related to <math>X_{new}<math> by an integer value <math>P\,\!<math> | |
| (3)+(2) | <math>X_{old} = P + 1 \div \frac{N_{new}}{D_{new}}<math> | ||
| <math>X_{old} = P + \frac {D_{new}}{N_{new}}<math> | |||
| <math>X_{old} = \frac { N_{new} \cdot P + D_{new} }{N_{new}}<math> | (4) | ||
| <math>P = N_{old} \,\, \mathbf{intdiv} \,\, D_{old}<math> | (5) | Let <math>P\,\!<math> be integer value of <math>X_{old}<math> ie. <math>P=3<math> if <math>X_{old}=\frac{649}{200}<math> | |
| (1) + (4) | <math>N_{old}= N_{new} \cdot P + D_{new} <math> | (6) | |
| (1) + (4) | <math>D_{old}= N_{new} <math> | ||
| <math>N_{new} = D_{old} <math> | (7) | ||
| (6) + (7) | <math>N_{old}= D_{old} \cdot P + D_{new} <math> | ||
| <math>N_{old} - D_{old} \cdot P = D_{new} <math> | |||
| <math>D_{new} = N_{old} - D_{old} \cdot P <math> | (8) | ||
| (2) + (7) + (8) | <math>X_{new} = \frac{D_{old}}{ N_{old} - D_{old} \cdot P }<math> | (9) |
This then leads to a recursive algorithm of turning a rational number (649/200) into continued fraction [3;4,12,4] by recursively calculating P using (5) and the new value of X using (9).
Ohanian 08:57, 2005 Apr 14 (UTC)
More fun with continued fractions of <math>\pi<math>
The continued fractions of <math>\pi<math> is
[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, ... ]
I notice that the good rational representation of the continued fractions of <math>\pi<math> are those just before a term of a large number. For example just before 292.
[3; 7, 15, 1 ] = 355/113
So I wanted to find where (which terms) the large numbers are in the continued fraction terms of <math>\pi<math>
So far, my python program returns....
$ python pi.py ======================================= Calculating the terms of pi using 4/pi = [(1,1),(3,4),(5,9),(7,16), ... ] New record 3 at 0 term New record 7 at 1 term New record 15 at 2 term New record 292 at 4 term New record 436 at 307 term New record 20776 at 431 term New record 78629 at 28421 term New record 179136 at 156381 term New record 528210 at 267313 term New record 12996958 at 453293 term
Ohanian 03:58, 2005 Apr 17 (UTC)
Simple and not simple
Please expand on the simple continued fraction (unity numerators) to include non unity numerators.
- Check out Generalized continued fraction.--Niels Ø 19:47, May 23, 2005 (UTC)
Arithmetic sequences
Are there any formulas for the continued fractions when the numbers are in a special sequence such as a Arithmetic progression or Geometric progression (Examples: [0;1,2,3,...],[1;2,4,8,...])?--SurrealWarrior 03:16, 14 Jun 2005 (UTC)
- According to Richard Schroeppel in HAKMEM, when the terms of the continued fraction are an arithmetic sequence, say [a+d, a+2d, a+3d, ...], the value of the fraction is
- <math>I_{a/d}(2/d) \over I_{1+a/d}(2/d)<math>,
- where the I(x) are modified Bessel functions. Hope this helps! -- Dominus 13:29, 14 Jun 2005 (UTC)
Thanks--SurrealWarrior 19:34, 14 Jun 2005 (UTC)