Talk:Continued fraction

Archives

This page has archives. Sections older than 365 days may be automatically archived by when more than 10 sections are present.

Ordinary arithmetic operations on continued fraction representation

While the representation of numbers as continued fractions is very pretty, I wonder how we do basic arithmetic operations like addition, subtraction, multiplication, and division directly in this form, without having to resort to converting them to ordinary fractions. I feel that the usefulness of this article can be greatly enhanced by this inclusion. Manoguru (talk) 18:22, 17 December 2019 (UTC)[reply]

"Complete convergent"?

The paper patz5.pdf cited under Pell's equation says on page 2:

... If

x_{n}=(P_{n}+{\sqrt {D}})/Q_{n}

is the n-th complete convergent of the simple continued fraction for

\omega =(P_{0}+{\sqrt {D}})/Q_{0}

, ...

but I can't find any definition of complete convergent. Is it just another name for a complete quotient? If it is, perhaps someone sufficiently knowledgeable could mention it in that page. Hv (talk) 13:46, 22 May 2021 (UTC)[reply]

Requires citations and clarifications

This is a long article; and I jumped in to the "Examples" section. The table completely mystified me, in terms of "how do I get from the 'stuff' in the table to a continued fraction?" What I'm getting at is that the column and row headings are neither descriptive nor described -- at least a quick definition of terms or a "For example, using the table able, we can generate pi with the following continued fraction. Notice how the values <bla bla bla> correspond to the table entries <bla bla bla>."

The citation that I'd like is one in the "History" section, where it states, "300 BCE Euclid's Elements contains an algorithm for the greatest common divisor which generates a continued fraction as a by-product" -- unfortunately, neither hotlink "Euclid's Elements" nor "greatest common divisor" leads me to text that deals with the "greatest common divisor which generates a continued fraction as a by-product" goal that I was looking for. Each leads me to its respective "narrow" definition, but nothing leads me to the overall concept about how GCD relates to continued fractions. 198.84.205.118 (talk) 00:03, 29 May 2021 (UTC)[reply]

I have edited the first item of section "History", and added in section "Motivation and notation": "The sequence of the integers that occur in this representation [of a rational numbers by a continued fraction] is the sequence of the successive quotients that are computed by the Euclidean algorithm". D.Lazard (talk) 08:32, 29 May 2021 (UTC)[reply]

Too hard formula represented on article

Correct formula for programming conversion $a/b$ to continued fraction is very simple and like this within loop:

       an1 := an0 / bn0; // integer div (you need this  $a_{n}$ )
       bn1 := an0 % bn0; // integer mod
       an0 := bn0;
       bn0 := bn1;

Mvitaminus (talk) 23:28, 2 June 2021 (UTC)[reply]

Division by zero

The article currently indicates "where $a i$ and $b i$ can be any complex numbers." Before we required $b i$ to be 1 -- because we were defining a simple continued fraction before -- and we also required that $a i$ be a positive integer. As a consequence, this prevented division by zero in every convergent. The current definition has no such safeguard. Should it? — $Q$ uantling (talk | contribs) 17:21, 2 May 2022 (UTC)[reply]

Reciprocal of 1

The article suggest that the reciprocal of a number is given by adding/removing a zero at the begining. It is not true for 1 or -1 since their reciprocals are themselves. 2601:648:8601:93A0:AC29:71C5:7EE0:6ABA (talk) 06:55, 13 December 2022 (UTC)[reply]

Did you work out the value of the continued fraction obtained when you add a zero at the beginning for these numbers? Remember that continued fraction representations are not always unique. —David Eppstein (talk) 07:01, 13 December 2022 (UTC)[reply]

The golden ratio is not the most irrational number.

If you use square roots, instead of fractions, you can get something more irrational than the golden ratio, because many square roots already become irrational with 1 iteration, which does not apply with fractions.

example: 3+sqrt(7+sqrt(15+sqrt(1+sqrt(292+sqrt(... 84.151.244.169 (talk) 15:07, 8 May 2023 (UTC)[reply]

I don't think that there is a precise meaning for "most irrational number". The point in the article is to highlight that the continued fraction expansion of the golden ratio

φ

is all ones. It turns out that this means that regardless of the fraction

p / q

, it is the case that the value

(| φ - p / q |) \times q 2

is large in comparison to what can be achieved with rational approximations for other irrational numbers. —

Q

uantling (talk | contribs) 16:20, 8 May 2023 (UTC)[reply]

Revamping the page

Hello!

I just wanted to check in with anyone that might care whether or not they'd take issue with me trying to reorganise the page. I've become quite interested in continued fractions not just as a weird means of 'calculating numbers', but as an alternate means of representing numbers between the integers to that of the usual decimal 'negative power series', and I'd really like to try to do justice to them through updating the page.

Some notes I've taken thus far as as follows:

- Motivation and Notation section spends a lot of time explaining how to calculate the continued fraction form from usual decimal negative power series form, not enough time talking about actual motivations/history/desirability, and the notation. Either I can change the name and collate related information or remove from this section and write a clearer explanation of the method elsewhere, preserving Pier4r's request above.

- Whole separate Notation section exists, which actually discusses 'alternative notations' to the ones presented in the 'motivation and notations section'; I think this heading should be changed and it should be subsumed by a broader section on notation.

- Repeated references throughout to the effect of "sqrt(2) actually equals 1.41421..., so you can calculate this from its continued fraction form [1;2,2,2,..] by doing so and so." Seems to be a neglect for the consideration of a continued fraction representation of a number as equally 'valid' as the power series representation, probably due to unfamiliarity and the somewhat cumbersome but necessary notation. To be clear, I think there's little reason to not switch the notation such that for example pi = 3.7(15)1(292)111213... (in continued fraction form) = [3;1,4,1,5,9,2,6,..] (in power series form) -- now imagine analogously saying that " pi actually = 3.7(15)1(292)111213..., so you can calculate this from its power series form via... ". I personally think it's reductive and unnecessary, so I wonder what you guys might think of this point in particular.

- The continued fraction notation version of a bunch of mathematical constants in the Motivation and Notation section seems really helpful to me for familiarising the reader with this perspective on these numbers, and I would like to preserve something similar, but when you look for its context you see that all this space is actually serving to elucidate infinite continued fractions, which is off-topic from the heading. I'd like to flesh out some of these kinds of examples with more numbers that aren't just infinite cfs, and reserve discussion of infinite cfs for maybe the section 'Infinite continued fractions and convergents'.

- Notice that there's no mention nor use of the 'repeating' notation usually seem with 'decimal' notation of numbers like 1/3 or 1/7, only ellipsis like sqrt(3) = [1;1,2,1,2,1, 2,...]. I'd like to explicitly incorporate that.

- Having read the page quite a few times, I'm confused as to whether it's about cfs in the canonical form or the generalised form. Given that a page exists solely for the generalised form, I'd be inclined to dedicate this to the canonical form, but I also feel that that would be too specific and might mislead people given the name. The diagram in the introduction shows it in the canonical form, mention of definition as 'the reciprocal of another number' somewhat suggests the understanding that it's about the canonical form, the intro makes the delineation between the two and suggests a prioritisation of the canonical form, yet the section on Basic Formula immediately jumps into the generalised form, despite that formula being mirrored on the generalised cf's page. That formula is then repeated in the later section titled 'generalized continued fraction(s?)', which I feel again is redundant and I'd like to remove and possibly move over any interesting information to its respective article if it's not there already.

There's more I'd like to add, including some interesting patterns I've found myself, some restructuring to be done, and more I need to study in order to be able to really speak on some topics. I'd like to ensure I'm factoring in the suggestions that others have already made too, and in particular I'd love to be able to address Manoguru's concerns about the natural operations of numbers in continued fraction form, but that's all I can speak on for now.

Please do let me know your thoughts on my potential changes, thank you for reading if you made it this far! CallumMScott (talk) 14:17, 14 August 2023 (UTC)[reply]

how "larger term" better approximation

I don't like the sentence

The larger a term is in the continued fraction, the closer the corresponding convergent is to the irrational number being approximated.

It goes on to explain that the golden ratio is the hardest to approximate because all terms of its continued fraction are "1".

I think what the sentence should say is something like "the larger a term is, the more that one term improves the approximation." But then I want to natter on about percentage reduction in absolute error.

I would like to hear from someone who understands the article before I try to "improve" it.

Jmichael ll (talk) 20:41, 8 November 2023 (UTC)[reply]

Which is closer to 4: 41⁄7 or 41⁄3?

The greater a partial quotient is, the less effect it and its successors have on the number; in other words, the more accurate the fraction already is. —Tamfang (talk) 05:32, 15 November 2023 (UTC)[reply]

Perhaps I'm mistaken in this concern, but isn't there a problem about what we mean by "the corresponding convergent"? Would it be an improvement to add a "next", as in

The larger the next term in the continued fraction is, the closer a convergent is to the irrational number being approximated.

?

I think both are true and mean slightly different things. Dhrm77 (talk) 15:40, 15 November 2023 (UTC)[reply]

Constructive observation

A real number $x$ has an infinite continued fraction expansion iff it is apart from all rationals: $\forall q:\mathbb {Q} .\exists m:\mathbb {N} +.|x-q|\geq (1/m)$ . This is constructively stronger than being irrational (not rational).

^[1]

46.33.143.125 (talk) 15:52, 28 January 2024 (UTC)[reply]

What does "apart from all rationals" mean, if not "irrational"? —Tamfang (talk) 17:28, 27 March 2024 (UTC)[reply]

Constructively, "apart" has a stronger meaning than "not equal". Two numbers are "apart" if they differ by at least some $1/n$. 46.33.143.125 (talk) 19:04, 13 April 2024 (UTC)[reply]

Can you give an example of an irrational number which is not "apart" from the rationals? –jacobolus (t) 19:37, 13 April 2024 (UTC)[reply]

What is an example of an irrational that has a finite neighborhood containing no rationals?? —Tamfang (talk) 21:07, 13 April 2024 (UTC)[reply]

The definition in the top comment here lets you pick a different neighborhood excluding each rational number. But I don't understand what's different about it than the concept of "irrational" per se. –jacobolus (t) 22:22, 13 April 2024 (UTC)[reply]

References

^ https://mathoverflow.net/q/462219

Proposal: move this to "Simple continued fraction", so that the current lemma can be used for generalized continued fraction

As already noted in 2006 (Talk:Generalized_continued_fraction#Not_"generalized"_enough?), the current lemmata continued fraction and generalized continued fraction are at variance from much of the mathematical literature. I therefore offer my help to move

this article continued fraction to simple continued fraction, and
generalized continued fraction to continued fraction,

in agreement with

DLMF https://dlmf.nist.gov/1.12
Weisstein https://mathworld.wolfram.com/ContinuedFraction.html
this most pertinent book https://www.google.de/books/edition/History_of_Continued_Fractions_and_Pad%C3%A9/rxzsCAAAQBAJ?hl=de&gbpv=1&dq=brezinski+history+of+continued&printsec=frontcover

Dyspophyr (talk) 15:23, 23 October 2024 (UTC)[reply]

Hi @Dyspophyr, I think your suggestion makes sense; although, in my opinion, it might make even more sense to merge the two articles...

Best, Malparti (talk) 16:11, 23 October 2024 (UTC)[reply]

"Continued fraction" is by far the WP:COMMONNAME for the topic currently at continued fraction. That is where anyone intersted in the topic would expect to find that article. It should not be moved. —David Eppstein (talk) 17:33, 23 October 2024 (UTC)[reply]

@David, you may be right that texts about `b0+1/(b1+1/(...` commonly call them "continued fraction". However, it is also true that texts about `b0+a1/(b1+a1/(...` commonly call these "continued fraction" as well. If under the header "continued fraction" we only treat the case `a1=a2=..=1`, then we are out of sync with much of the mathematical literature. If we start under this header with the generic case, then we do nothing wrong. Of course at some point we have to mention the special case `a1=a2=..=1`. -- Dyspophyr (talk) 17:49, 23 October 2024 (UTC)[reply]

@David Eppstein "Continued fraction" is by far the WP:COMMONNAME for the topic currently at continued fraction." → I agree, but I was under the impression — and I might be wrong about this! — that "continued fraction" is also the WP:COMMONNAME for the topic currently at generalized continued fraction. Hence my suggestion that maybe the two articles could be merged.

At any rate: I think we agree that what matters is that people who search for "continued fraction" should be told fairly early in the article that "continued" fraction is a generic term that some people use in a strict sense to refer to what are also known as simple continued fractions; and some other people use in a loose sense to refer to what are also known as generalized continued fractions. Then, whether there should be {one article} vs {a main article about simple continued fractions and a specialized one on generalized continued fractions} vs {a main article about generalized continued fractions and a specialized one about simple continued fractions} is not completely clear: to me, these three options seem to make sense...

One argument that goes in the direction suggested by @Dyspophyr is that several of the resources linked in the article continued fractions define "continued fractions" as generalized continued fractions (Britannica, Encyclopedia of mathematics, to some extent Wolfram MathWorld, etc).

Best, Malparti (talk) 20:09, 23 October 2024 (UTC)[reply]

@Malparti, there are two pragmatic reasons against merging: The present article is very long, and uses notation that is in conflict with the generic article. Therefore I rather suggests that the generic article, moved here, be given a section on the `a1=a2=..=1` case, which then refers to "simple continued fraction" for deeper information. -- Dyspophyr (talk) 17:49, 23 October 2024 (UTC)[reply]

I oppose this move. This encyclopedia is a general resource, not devoted solely to mathematicians. Non math readers who want to learn about "continued fractions" should get this article, not a more general one.

I think the issues you cite about the relationship between the articles could be reduced by adding a WP:Hatnote to this article. Among all readers who enter, those who are looking for the mathematicians view would then quickly find the other article. Johnjbarton (talk) 18:18, 23 October 2024 (UTC)[reply]

I don't think a hatnote is a good solution. But generalized continued fraction should be linked from within the lead section. –jacobolus (t) 19:02, 23 October 2024 (UTC)[reply]

This seems like reasonable evidence that the present wiki-naming is against the common naming convention. It also seems like the Press–Teukolsky and Jones–Thron sources at generalized continued fraction also use "continued fraction" for what wiki now calls "generalized continued fraction." Is there good counterevidence, that "generalized continued fraction" is actually common terminology for this? Gumshoe2 (talk) 18:25, 23 October 2024 (UTC)[reply]

There are many sources calling this "simple continued fraction" and many sources calling the other one "generalized continued fraction" (though more sources just use the name "continued fraction" with the specific meaning clear from context), but ~~I think the "simple" variant is overall a better article for this title. It seems fine to use the title Generalized continued fraction for that article,~~ I don't think readers will be confused.

What we could do, however, is enlarge the section at this article about generalized continued fractions to provide a somewhat more detailed summary. –jacobolus (t) 19:12, 23 October 2024 (UTC)[reply]

Edit: after doing some more skimming in the literature, I'm somewhat leaning towards mostly merging these articles under the name Continued fraction, and then possibly splitting out any excessively detailed sub-sections into more specific articles. –jacobolus (t) 20:56, 23 October 2024 (UTC)[reply]

If it's possible to do without making the article unwieldy, this seems to me like a very satisfactory solution. (But I have no opinion on whether it's possible!) Gumshoe2 (talk) 21:03, 23 October 2024 (UTC)[reply]

The current article is mostly unwieldy because it has a poor structure: there are too many small top-level sections, limited narrative flow, and not much high-level vision. Even without changing the scope it would be improved significantly by someone with knowledge about and care for the subject doing a some significant housecleaning (probably with some nontrivial shortening / cutting of material here now). I don't feel qualified or motivated to take on a job like that though. –jacobolus (t) 22:24, 23 October 2024 (UTC)[reply]

@Johnjbarton »Non math readers who want to learn about "continued fractions" should get this article, not a more general one« - Why? Non-specialist readers come here because they somehow encountered the notion "continued fractions" out in the wild, often applied to beasts of the non-simple type. They will be very confused by our current narrow definition, as I was when I first came here. A hatnote would help (@jacobolus why not even a hatnote??). However, using standard terminology from the onset would help much more. -- Dyspophyr (talk) 19:41, 23 October 2024 (UTC)[reply]

Hatnotes are not intended to be used for disambiguating closely related topics like this. See WP:RELATED. –jacobolus (t) 22:19, 23 October 2024 (UTC)[reply]

Ok, seems like you have a lot of input here. I was mainly pushing against the idea that the decision should be based on what mathematicians want. Johnjbarton (talk) 22:21, 23 October 2024 (UTC)[reply]

@jacobolus »many sources calling the other one "generalized continued fraction"« - can you show us some of these sources? -- Dyspophyr (talk) 19:45, 23 October 2024 (UTC)[reply]

Some evidence: Google Scholar search for "the continued fraction" (a phrasing that makes sense only for the version described in this article): about 31200 results. Google Scholar search for "simple continued fraction": about 2730 results. Or, if you prefer phrasing where this distinction is even less ambiguous: "the continued fraction expansion": about 11700 results; "simple continued fraction expansion": about 1040 results. So avoiding simple and using a definite article to indicate the uniqueness of the expansion (something that would not be true for generalized continued fractions) is about 10x more of a WP:COMMONNAME than using simple. —David Eppstein (talk) 20:01, 23 October 2024 (UTC)[reply]

@David Eppstein ""the continued fraction" (a phrasing that makes sense only for the version described in this article)" → I am nitpicking a bit here, but I disagree with this because I've used expressions such as "the continued fraction of the theorem" and "the continued fraction <math expression>" to refer to generalized continued fractions in work indexed by Google Scholar. Malparti (talk) 20:19, 23 October 2024 (UTC)[reply]

That's why I included the second variation, with "expansion". It didn't make much difference in the relative proportions. —David Eppstein (talk) 20:23, 23 October 2024 (UTC)[reply]

@David Eppstein Sorry, but I don't understand: I could see myself use something like "the continued fraction expansion below" to refer to a generalized continued fraction expansion (and in fact I've done that; and read it as well). So wouldn't those be false hits for your stats? Sorry if I am missing something. Anyway: I am not arguing that "continued fraction" isn't the common name for simple continued fraction — we agree on that. My "concern" (though the word is a bit excessive) is that it might also the common name for generalized continued fraction. Malparti (talk) 20:40, 23 October 2024 (UTC)[reply]

Any query is going to have false hits. I do not expect the number of false hits to be significant nor to change the proportions much for these queries. —David Eppstein (talk) 20:42, 23 October 2024 (UTC)[reply]

Maybe I've misunderstood your point, but this evidence seems perfectly compatible with the claim that "generalized continued fraction" is not a common name for the topic of wiki article generalized continued fraction and moreover that both are typically called "continued fraction." Gumshoe2 (talk) 20:41, 23 October 2024 (UTC)[reply]

Sure. But when two related but distinct topics share the same name we still need two articles on them, and in such cases when one of the two topics is by far the WP:COMMONNAME (that is, the topic usually meant by that name, not merely the name usually used for that topic) we let that topic have the unmodified name and modify the name of the less-common topic. Exactly as is the status quo for these two articles already. —David Eppstein (talk) 20:45, 23 October 2024 (UTC)[reply]

I find that rather problematic, any reasonable wiki-reader would clearly think that "generalized continued fraction" is the typically understood name for this concept. (In fact, until today I have been such a reader of these particular pages.)

However I can appreciate that the one special case is the most important and deserves the most central coverage. I don't see any easy solution; however, from what I can see, at minimum I think a note should be added somewhere near the top of generalized continued fraction to say that the concept is typically (or at least very often) simply called "continued fraction." Gumshoe2 (talk) 21:00, 23 October 2024 (UTC)[reply]

If it is really the case that "generalized continued fraction" is not used much for these things, so much so that it would be misleading to use that title, another alternative would be to use a disambiguator, like continued fraction (non-unit). —David Eppstein (talk) 21:09, 23 October 2024 (UTC)[reply]

I think something like that would be much more satisfactory than the present situation.

(However, just to emphasize, my only knowledge of this matter comes from this thread. For all I know, "generalized continued fraction" is actually common language for this – but so far I haven't seen any reason to think this.) Gumshoe2 (talk) 21:13, 23 October 2024 (UTC)[reply]

Other names include "non-simple continued fraction" and "irregular continued fraction". –jacobolus (t) 22:00, 23 October 2024 (UTC)[reply]

I like those better than my disambiguation above. —David Eppstein (talk) 22:08, 23 October 2024 (UTC)[reply]

Continued fraction (complex) would be a natural disambiguation. fgnievinski (talk) 02:49, 24 October 2024 (UTC)[reply]

"Complex" is potentially confusing, because it seems to more commonly indicate that the "integers" in the fraction are Gaussian integers rather than describing what kind of numerators are used. –jacobolus (t) 03:59, 24 October 2024 (UTC)[reply]

@David Eppstein (also @Jacobolus): "But when two related but distinct topics share the same name we still need two articles on them" → Yes, but that was my point from the start: are these topics distinct enough that we need two articles? From my perspective (i.e, from the perspective of someone not working on continued fractions, but who has used them in their research), I wasn't really convinced that this was the case... Hence my suggestion to merge the two articles (and possibly keep dedicated articles for more in depths discussions). Malparti (talk) 21:01, 23 October 2024 (UTC)[reply]

Also: as I said, I'm not an expert on the topic so my opinion isn't really informed; as a result, I think I've contributed what I had to contribute to this conversation. What I could do — if that's useful — is set up a slightly more robust method to try to search the literature and try to determine "what is being called what, in which field" and "what is the most common topic, in which field" [my guess is that simple continued fractions overwhelmingly used in topics related to number theory; but that generalized continued fractions might be more common in other areas]. As long as it doesn't take me more than, say, one hour, I'm happy to do that if that's helpful. Cheers, Malparti (talk) 21:08, 23 October 2024 (UTC)[reply]

Looking some more, I find plenty of examples but also a similar number where "generalized continued fraction" instead means a higher-dimensional analog of a continued fraction, which I'm not sure we have any articles about. –jacobolus (t) 20:47, 23 October 2024 (UTC)[reply]

@David Eppstein Let me look into your argument based on a Google Scholar search. You found "continued fraction" is 10 times more frequently used than "simple continued fraction". That sounds perfectly credible. Even a higher ratio would not have surprised me. But it does not support your conclusion.

You argue: In the scholarly literature, term X ("continued fraction") is more frequently used than term Y ("simple continued fraction"), hence X is the WP:COMMONNAME for Wikipedia article X. Funnily, your argument would work exactly the same way after we had done the proposed renaming. Why? Because you nowhere refer to the contents of the articles.

In drawing your conclusion, you implicitly assume that the scholarly works about X and Y deal with the thing defined in our article X. This, however, is not the case. Quite many texts (reference works, textbooks, research reports) that contain the term X assume a definition that is less restrictive than in our present article X. They all, however, are compatible with the definition given in another WP article, currently named Z ("generalized continued fraction"), which defines Z to be a strict superset of X.

In such a situation the obvious solution, advocated by @Malparti, is to merge articles X and Z under lemma X. However, this would lead to a loss of version history. For this only reason I propose to move X to Y ("simple continued fraction") before porting a digest of it to the new common article X'.

Does this help to elucidate the situation? -- Dyspophyr (talk) 05:59, 24 October 2024 (UTC)[reply]

No. Try fewer words.

A hint: I didn't refer to the content of the articles because I think we can all agree on what they are: one is about nested fractions of a specific form with 1 in the numerators, and the other is on a similar form without the restriction on the numerators.

So your theoretical maunderings about how maybe these articles could be about some entirely different topic than what they are about seem to be entirely based on counterfactuals. —David Eppstein (talk) 06:32, 24 October 2024 (UTC)[reply]

[1] ttps://mathoverflow.net/q/462219

[1]