Wikipedia:Featured article candidates/Euclidean algorithm/archive1: Difference between revisions
Content deleted Content added
→Euclidean algorithm: some replies to Cryptic |
MalnadachBot (talk | contribs) m Fixed Lint errors. (Task 12) |
||
| (28 intermediate revisions by 5 users not shown) | |||
Line 1:
<!--FAtop--><div class="boilerplate metadata afd vfd xfd-closed" style="background-color: #E6F2FF; margin: 2em 0 0 0; padding: 0 10px 0 10px; border: 1px solid #AAAAAA;">
:''The following is an archived discussion of a [[Wikipedia:featured article candidates|featured article nomination]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made on the article's talk page or in [[Wikipedia talk:Featured article candidates]]. No further edits should be made to this page.''
The article was '''promoted''' by [[User:Karanacs|Karanacs]] 21:05, 19 May 2009 [http://en.wikipedia.org/w/index.php?diff=prev&oldid=291028455].
----
===[[Euclidean algorithm]]===
Line 54 ⟶ 60:
:As a conciliatory gesture to a numerically-minded classicist, I'll be glad to add some more references to the 130 already there. When I've finished, please reconsider your strong oppose. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 02:45, 29 April 2009 (UTC)
::I've added 22 more references. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 17:20, 30 April 2009 (UTC)
:::There are just a few more passages that I think need to be cited: 1) "However, the solutions cannot shrink indefinitely, since...." until the end. 2) "The remainder is equivalent to the congruence class in modular arithmetic." 3) "A generalization of this result is known as Sturm's theorem." 4) "Bézout's identity, and therefore the previous algorithm, can both be generalized to the context of Euclidean domains." 5) "The GCD is said to be the generator of the ideal of a and b. This GCD definition led to the modern abstract algebraic concepts of a principal ideal..." 6) "this is impossible for a system of linear equations when the solutions can be any real number." 7) "Such finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called Galois fields, and are abbreviated as GF(p) or GF(pm)." 8) "Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity. For comparison, the efficiency of alternatives to Euclid's algorithm may be determined." (statement of practice definitely needs a citation for verification) 9) "In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization..." (see above about statements of practice) 10) "The polynomial Euclidean algorithm has other applications as well, such as Sturm chains...." 11) "Many of the other applications of the Euclidean algorithm carry over to Gaussian integers." 12) "This failure of unique factorization in some cyclotomic fields led Ernst Kummer to the concept of ideal numbers and, later, Richard Dedekind to ideals." 13) "An important generalization of the Euclidean algorithm" (characterization as "important").
:::Question - do you cite a first line, but that citation carries into the next? That could be a problem, because your citations would cover the next sentences but you don't place them where they would acknowledge that. [[User:Ottava Rima|Ottava Rima]] ([[User talk:Ottava Rima|talk]]) 14:54, 8 May 2009 (UTC)
;Comment on terminology
Line 60 ⟶ 68:
<math>
a = bq + r </math>
uniquely with a (degree) condition on r (and some conditions on a and b). They are related, of course, but I was wondering if it might be worthwhile saying something to that effect off the bat. [[User:Fowler&fowler|<
:Perhaps you're referring to the "division lemma" or [[division algorithm]]? If so, the article mentions it in the subsection "Calculating the quotients and remainders". But I haven't encountered a source that calls it the "Euclidean algorithm"; could you point me towards one? [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 02:45, 29 April 2009 (UTC)
::I had a vague feeling Fowler had a point there, so I dug through some books I had handy. I found that (as expected) Hardy & Wright's number theory book states that "Euclid's algorithm" is defined by generating the sequence of remainders which terminates (it seems to give no name for the "division algorithm", merely calling it division with remainder at times), Dummit & Foote's abstract algebra book states that the "Euclidean algorithm" comes from the ''division algorithm'', but Herstein's ''Topics in Algebra'' does indeed call the above, ''the'' Euclidean algorithm. Herstein is a pretty well-known algebra book, so I dug a bit more and I found that a source on the [[Euclidean ___domain]] article, which was published in the Bulletin of the American Mathematical Society in 1949, also uses the term Euclidean algorithm for division algorithm (see [http://projecteuclid.org/euclid.bams/1183514381]). I think in number theory books there is a pretty well-established tradition of using "Euclidean algorithm" to mean generating the sequence of remainders from the two initial numbers. In algebra texts that discuss Euclidean domains, my suspicion is that books here and there may use Euclidean algorithm to mean division algorithm but I suspect that modern books generally don't; I find Dummit & Foote is pretty reliable regarding modern terminology, while Herstein is from 1961 and sometimes a bit outdates on terminology. In any case, I think a note or footnote is in order. --[[User:C S|C S]] ([[User talk:C S|talk]]) 04:59, 29 April 2009 (UTC)
:::Yes, I guess you are right: number theory texts do call it the "division algorithm," and in fact, come to think of it, in high-school we called it the "division algorithm" ourselves, perhaps because it was introduced as a part of elementary number theory. Somewhere in college though the name became less certain (as I remember it). As for texts, among the classic algebra texts, both van der Waerden and Birkoff/Mac Lane do call it the "division algorithm," but Herstein doesn't (as you say). The more recent texts seem to be a mixed bag. I don't know Dummit and Foote, but among the books published in the last 20 years that refer to the "division algorithm" as the "Euclidean algorithm" are (the links should take you straight to the page about the "Euclidean Algorithm"): Hilton and Wu's ''[http://books.google.com/books?id=ua5gKZt3R6AC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA10,M1 A Course in Modern Algebra]'' (1989), Rowen's [http://books.google.com/books?id=EmO9ejuMHNUC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA116,M1 Algebra: Groups, Rings, and Fields] (1994), Lang's ''[http://books.google.com/books?id=Fge-BwqhqIYC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA173,M1 Algebra: A Graduate Course]'' (2002), Murty and Esmonde's [http://books.google.com/books?id=YaqVpdrngNYC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA3,M1 Problems in algebraic number theory] (2004), Lang's ''[http://books.google.com/books?id=PdBirmNTwu0C&printsec=frontcover&source=gbs_summary_r&cad=0#PPA113,M1 Undergraduate Algebra]'' (2005), and Lowen's [http://books.google.com/books?id=8svFC09gGeMC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA27,M1 Graduate Algebra: The Noncommutative View] (2008). Lang (2002), in particular, is still widely used, I think. So the footnote will be useful for any others who have questions like mine. :) Thanks! [[User:Fowler&fowler|<
::::I didn't check all those books publication dates, but certainly Lang's well-known classic ''Algebra'' is not really a book "published in the last 20 years". The revised 3rd edition is from 2002, but the original was from 1965, and subsequent versions are essentially the same (but with fixing of errors and so forth). Unlike the others you mention, which I've never heard of, certainly it is still used (mainly by the top graduate programs and more that like to think they are in the same class). --[[User:C S|C S]] ([[User talk:C S|talk]]) 20:47, 29 April 2009 (UTC)
::::Actually I expect the Hilton and Wu book must be from the 60s too, since "Hilton" is Peter Hilton and he wrote several books in that period, all of which are well regarded but never really caught on like their competitors. Indeed, Hilton is rather infamous (in a humorous way) for writing a book on homology/cohomology (with Wylie) and using the terms homology and cohomology to refer the opposite way as everyone else used them. That never changed in subsequent editions even though by then it became clear they had lost the terminology reformation attempt. Herstein is also a bit weird in that he composes linear transformations from left to right instead of right to left. That never changed in recent printings. So anyway, if your point (which I think it may be) is that even though these books are old, but they were recently republished and so must reflect more modern terminology, I'm afraid I don't buy that. In my experience, republished classic texts often retain their classic (read: outdated) terminology, and the reader is supposed to be on guard for it. --[[User:C S|C S]] ([[User talk:C S|talk]]) 21:01, 29 April 2009 (UTC)
:::::My point was simply that these books, regardless of their provenance, are still being used by students (as both books by Lang are, by your own admission), so it doesn't hurt to have the note. I have no idea if the terminology is outdated. Certainly Lowen's [http://books.google.com/books?id=8svFC09gGeMC&printsec=frontcover&source=gbs_summary_r&cad=0#PPA27,M1 Graduate Algebra: The Noncommutative View] (2008), [http://www.ams.org/bookstore-getitem/item=GSM/91 published by the AMS] does look recent. Anyway, this is not a biggie for me. Regards, [[User:Fowler&fowler|<
I understand and agree wholeheartedly. Perhaps I should have forestalled your comments by mentioning that Herstein is still a widely used book. --[[User:C S|C S]] ([[User talk:C S|talk]]) 23:02, 29 April 2009 (UTC)
Line 89 ⟶ 97:
* '''Strong Oppose''' - lack of citations for over 50% of the page means that it fails the citation requirements. [[User:Ottava Rima|Ottava Rima]] ([[User talk:Ottava Rima|talk]]) 13:20, 28 April 2009 (UTC)
*'''Looking to support'''. I haven't read it yet, but it looks pretty good. Will make vote more definite upon reading. [[User:Fowler&fowler|<
*'''Support'''. I have (inofficially) reviewed the article recently and found it very good (see the article talk page), and think it has even improved since. It is very comprehensive, accessible, provides pictures where useful. I only have one suggestion, which is easy to fix: please consider adding reference(s) for the section "Induction, recursion and infinite descent". I don't agree with Ottava Rima's point above, which is exaggerating verifiability, but that section could do with a brief reference for each of the three methods, just in the sense of a "further reading", if readers are interested in learning more about induction etc. (A reference mentioning these techniques in correlation to the EA would be ideal.) [[User:Jakob.scholbach|Jakob.scholbach]] ([[User talk:Jakob.scholbach|talk]]) 21:47, 29 April 2009 (UTC)
Line 127 ⟶ 135:
**:Reworded caption, thanks. The animation might be helpful, but that would require someone to create and position precisely 1440 1-by-1 squares. It's possible — are you volunteering, by any chance? [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 09:59, 4 May 2009 (UTC)
**::I'm not familiar with how to convert a series of images into an animation, but I'd be willing to make the images (or at least try). If I make them, can you make the animation? --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 18:52, 4 May 2009 (UTC)
**<s>"The greatest common divisor is often written as GCD(a, b) or, more simply, as (a, b)." Yes, the second version is simpler, but that notation is also used for ''lots'' of other things in mathematics. What (a, b) represents depends on the context of the problem, and I think it would be wise to mention this so as not to mislead our less mathematically-inclined readers.</s>
**:Mentioned ambiguity of "(''a'', ''b'')" notation, and swapped order of last two sentences in paragraph for better flow. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:10, 5 May 2009 (UTC)
**::Eh, better, but instead of "although the simpler notation is also used for unrelated mathematical objects, such as two-dimensional vectors." how about "although the latter notation is also used for various other mathematical concepts, such as two-dimensional [[vector]]s."
**:::That's a good suggestion! I followed your wording more-or-less exactly. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 02:29, 6 May 2009 (UTC)
**::::I was hesitant to use the word "unrelated", but I couldn't figure out exactly why. Here's why: "unrelated" may imply that the two components, ''a'' and ''b'', are unrelated, which is obviously never the case. "other" makes it clear that the concepts are unrelated to EA without introducing the ambiguity. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 00:57, 8 May 2009 (UTC)
**:::::Just to clarify, the wording now is "although the latter notation is also used for other mathematical concepts, such as two-dimensional vectors." [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 15:52, 14 May 2009 (UTC)
**<s>"neither 6 = 2×3 nor 35 = 5×7 is a prime number, since they both have two prime factors" I think it may be a tad confusing to include the prime factorization at first; perhaps this should be added later: "neither 6 nor 35 is a prime number, since they both have two prime factors: 6 = 2x3 and 35 = 5x7." or something like that.</s> Also, shouldn't it be "neither 6 nor 35 '''are''' prime number'''s'''" ?
**:Excellent suggestion for the rewording. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 09:59, 4 May 2009 (UTC)
Line 135 ⟶ 146:
**:::Hrm. Well, I'm not particularly sure about it myself, so use your best judgment. I just wanted to bring it to your attention. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 22:23, 3 May 2009 (UTC)
**::::In my way of thinking, it depends how we are using "6" in the context. Since we say "6 ''is'' composite" (just as we say "7 ''is'' prime"), it seems to me we are thinking of it as singular.
**::::"Neither," the converse of "both," usually has singular verb concord (as the Bartleby reference suggests as well). So, "Neither 6 nor 35 is prime" sounds correct to me. The adjective "prime" will not apply to instances of plural occurrences of 6; in other words, you can't apply "prime" to "six sheep," although you ''can'' say, "The number of sheep (''viz.'' 6) ''is'' prime." That is as far as ''prescriptive grammar'' goes. If you look at usage on the web, "Neither * nor * is" has [http://www.google.com/#hl=en&q=%22Neither+*+nor+*+is%22&btnG=Google+Search&aq=f&oq=%22Neither+*+nor+*+is%22&fp=OlAWEoQSgPM approximately 7 million hits], whereas "Neither * nor * are" has [http://www.google.com/#hl=en&q=%22Neither+*+nor+*+are%22&fp=OlAWEoQSgPM 16.4 million hits] (some are using "are" for plurals, but not all). So, even though most prescriptive grammar books don't look kindly upon plural verb agreement for "neither" in the case of third person singular nouns, as in "Neither Hamas nor Hizebollah ''are'' ...," if people, by a margin of two to one, ''are'' making such constructions, sooner or later the descriptive grammar books will take notice. [[User:Fowler&fowler|<
**:::::I agree that "6" and "35" (in the sense used here) are each singular, as in "7 is a prime number" or "12 is a composite number". Per Bartleby's and other references, I feel that "neither...nor" should take a singular verb if both nouns are singular, as in "Neither Clara nor John was absent from class". [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:06, 5 May 2009 (UTC)
**<s>"Imagine a rectangular area a by b, and consider any common divisor c that divides both a and b exactly." Wikipedia is an encyclopedia, not an episode of Spongebob Squarepants. No sentence in an encyclopedia should start with "imagine."</s>
Line 141 ⟶ 152:
**<s>"the GCD(462, 1071) = 3×7" In all other instances thus far, you have chosen not to use an article before GCD. Did you mean to say "the'''n''' GCD(462, 1071) = 3×7"?</s>
**:Thank you for catching that inconsistency, which I've fixed. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:32, 4 May 2009 (UTC)
**<s>"Integer factorization is thought to be a difficult problem for large numbers." A bit weaselly, and it's not particularly difficult if you have a calculator handy. Perhaps "can be" instead of "is thought to be" ?</s>
**:I clarified the sentence, although perhaps I should have been more clear about "large numbers". A pocket calculator might help in factoring numbers up to 20,000 (5 digits), but it won't be useful in factoring numbers with 500 digits, the rough size of number used in modern cryptography. Nevertheless, the Euclidean algorithm can quickly find the greatest common divisor of two 500-digit numbers. That was the point I was trying to convey. Should I spell that out in the article, do you think? [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:32, 4 May 2009 (UTC)
**::I corrected the statement the first time from asserting "is a difficult problem" to "is thought to be..." since it is "only" thought to be difficult, not proven. The new version which states "The computational difficulty of integer factorization grows exponentially with the size of the number being factored" is a step backwards in that regards. The computational difficulty of integer factorization is in fact unknown. --[[User:C S|C S]] ([[User talk:C S|talk]]) 11:36, 4 May 2009 (UTC)
**:::You are right that I was inferring too much about the specific scaling of factorization. I've re-worded this sentence to "Factorization of large integers is believed to be such a difficult problem that many modern cryptography systems are based upon it.", which is supported by the Schroeder reference. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 13:59, 4 May 2009 (UTC)
**::::Good enough for me. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 00:57, 8 May 2009 (UTC)
**<s>"A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory." This statement should probably be accompanied by a ref.</s>
**:OK. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:32, 4 May 2009 (UTC)
Line 161 ⟶ 173:
**<s>"Finally, in infinite descent, a given solution is used to construct a smaller solution." I read this sentence and thought I understood the concept being explained. Then I read [[infinite descent]]. Then I reread this sentence, which I now realize does a fairly poor job of explaining infinite descent. My familiarity with the concept is limited to that which I have just read, so I have no suggestion as to how to concisely summarize it, but I strongly urge you to rework the current explanation.</s>
**: I hadn't wanted to talk about the (more common) use of infinite descent in impossibility proofs such as [[Fermat's Last Theorem]]. Rather, my goal was to prepare the reader to follow the logic of why the EA must stop eventually. Nevertheless, I've re-written those sentences to to give a broader understanding of the argument. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 09:36, 5 May 2009 (UTC)
**<s>"The validity of the Euclidean algorithm can be shown by two-step argument." Since the title of the section is ''proof of validity'', perhaps this sentence should include the word 'proof': "The validity of the Euclidean algorithm can be proven with a two-step argument."</s>
**::If you're worried about what mathematicians will think of the section, perhaps providing a rigorous proof would be better than simply avoiding the word 'proof'. In any case, I'm happy with it as is. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 18:04, 5 May 2009 (UTC)
**:Perhaps I'm not following you but the the paragraph about prime factorization and GCD in the Background section uses 1071 and 462 as an example. For example, it says, "since 462 can be factored into 2×3×7×11 and 1071 can be factored into 3×3×7×17, the greatest common divisor of 462 and 1071 equals 21 = 3×7, the product of their shared prime factors." We could repeat that here, but it seems redundant. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:58, 5 May 2009 (UTC) **::>.< I swear you put that in after I made the comment! :P --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 18:04, 5 May 2009 (UTC)
**<s>"The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly." This paragraph desperately needs to end with: "The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle." or something like that.</s>
**:
**<s>"where the magnitude of rk is strictly less than that of rk−1" The use of 'magnitude' here strikes me as being a bit odd. Why not just write a simple inequality? r<sub>k</sub> < r<sub>k-1</sub></s>
**:The "magnitude" wording also covers versions of the algorithm when the remainder can be negative. For example, -37628 < 4, but 4 has a smaller magnitude. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:58, 5 May 2009 (UTC)
**::True. I wonder if using absolute value notation |r<sub>k</sub>| would be better. Up to you. In any case, magnitude or absolute value should be linked to avoid confusion for math noobs. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 18:04, 5 May 2009 (UTC)
**:::Another good idea, which I followed. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 02:29, 6 May 2009 (UTC)
**<s>"Euclid finds the quotient and remainder by repeated subtraction" Last time I checked, Euclid is dead. Past tense, perhaps?</s>
**:Perhaps passive voice, instead. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:58, 5 May 2009 (UTC)
**::Perhaps I've struck the issue. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]'''
**<s>"''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>" Is there some article to which we can link '≡'? I'm not sure I know what it means.</s>
**:It means "equivalent to" in [[modular arithmetic]]. I'll make a link. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:58, 5 May 2009 (UTC)
**I don't think the ''implementations'' section belongs in this article. [[WP:NOT|Wikipedia is not]] a how-to guide, and this section does not contain any new relevant information.
**::Your initial reaction is similar to mine. Bu let me argue that the implementations contribute at least epsilon to the article for most readers, and for some readers may convey the algorithm's idea better than anything else. I note that [http://en.wikipedia.org/w/index.php?title=Euclidean_algorithm&oldid=276556143 when I arrived] at this article — then rated at nearly GA level by the Math WikiProject — the implementations were the article's main content, having been debated and perfected for over [http://en.wikipedia.org/w/index.php?title=Euclidean_algorithm&oldid=250714 seven years]. Some editors champion the pseudocode as the only valid way of defining the algorithm precisely. In deference to these editors and in deference to the many readers like them, I feel we should retain the Implementations section. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:18, 9 May 2009 (UTC)
**:::Deference to these editors? Pfft. Perhaps you have forgotten the disclaimer: "If you don't want your writing to be '''edited mercilessly''' or redistributed for profit by others, do not submit it." As for the readers, they come here for a lot of things that they really shouldn't (medical advice comes to mind). The very most we can do in regards to instruction content like this is to provide an informative link — perhaps to a WikiHow article or a programming site. I realize that you have the best intentions by wanting to keep the material, but the fact of the matter is that it really doesn't belong here. The other points you've brought up are largely irrelevant. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 03:32, 9 May 2009 (UTC)
**::Let me clarify the question with a triple negative. ;) I'm NOT saying that we should violate WP:NOT in order to NOT hurt the feelings of some devoted editors. Rather, the pivotal issue is whether the Implementations section allows us to ''explain the algorithm'' to readers who might not really understand it otherwise. I argue yes. It's not about providing snippets of HOWTO code, but rather providing another avenue that connects the algorithm to our readers. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 04:13, 10 May 2009 (UTC)
**:::You will not be able to find a pseudocode representation that all programmers will be able to understand. I am very experienced with TI-BASIC and I've twiddled with C++, but I'm not familiar with some of the notation you've used. As I see it, you have three options: Give whatever programming language you choose [[WP:UNDUE]] weight by explaining all of the relevant syntax, leave it vague and hope for the best, or remove the section altogether. I think at this point it's clear which option I'd prefer. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 03:32, 11 May 2009 (UTC)
**<s>"if the resulting negative remainder is smaller in absolute value than the typical positive remainder" You used "magnitude" earlier. I recommend swapping out "absolute value" for "magnitude" for consistency.</s>
**::OK, sounds good. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:18, 9 May 2009 (UTC)
**<s>"to the greatest length g that measures a and b evenly" The word "measures" seems a bit off. Shouldn't it be "divides"?</s>
**::A geometric length is qualitatively different than an integer. "Measure" or "measure off" is the standard vocabulary used for the former. The ancient Greeks distinguished the two operations (division and "measuring off"), and their concepts have carried over. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:18, 9 May 2009 (UTC)
**<s>"in other words, the lengths a and b are both multiples of the length g" I suggest the injection of the word "integer" before "multiples", without it, the whole concept is meaningless.</s>
**::Great catch, although I predict that most non-mathematicians would assume that "multiple = integer multiple". [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:18, 9 May 2009 (UTC)
**:::Aye, it's the finnicky mathematicians I'm worried about here. :) --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 03:32, 11 May 2009 (UTC)
**<s>"The algorithm was likely known by Eudoxus of Cnidus (about 375 BC). The use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in Euclid and Aristotle (Topics IV) suggests that the algorithm predates Eudoxus." I see what you're getting at, but to some readers, these sentences may seem to contradict each other. Suggested rewrite: "The use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in Euclid and Aristotle (Topics IV) suggests that what we now know as the Euclidean Algorithm may have predated [[Eudoxus of Cnidus]], a Greek mathematician who died in approximately 350 BC." or some such. Meh. That's not exactly perfect either. Give it some thought.</s>
**::That's a good suggestion, and very helpful. I toyed with the wording beforehand, but I didn't come up with anything as good as yours. I've uploaded a third wording that may combine the best of our efforts. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 04:13, 10 May 2009 (UTC)
**:::Ah, much better! More direct than mine, too. I'm confused about the last bit, though: "use of the technical term ἀνθυφαίρεσις (''anthyphairesis'', reciprocal subtraction) in Euclid and Aristotle (''Topics'' IV)" Did Euclid and Aristotle collaborate on a book called "Topics IV"? What's going on here? --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 03:32, 11 May 2009 (UTC)
**::::That interpretation didn't occur to me, thanks! The ''Topics'' reference was just a clue for the reader where to find Aristotle's comments on reciprocal subtraction. Euclid and Aristotle didn't co-author anything, at least to my knowledge; IIRC, Euclid was much younger than Aristotle. The passage now reads "The algorithm may even pre-date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle." [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 15:57, 14 May 2009 (UTC)
**<s>"Euclid's algorithm was re-invented both in India and in China" "re-invent" often implies that an existing concept was significantly improved. I think "independently developed" or "independently discovered" might serve better.</s>
**::Good idea, made additional minor changes in wording. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:35, 9 May 2009 (UTC)
**<s>"the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer"" Erm... why?</s>
**::Good question! The historical record does not say, as far as I can tell. One author speculates that it's because the algorithm "pulverizes" difficult linear Diophantine equations in only a few steps, emphasizing its power to solve problems. Its operation also vaguely resembles a pulverizer that breaks a large stone into medium-sized stones, then into small stones, and thence into dust. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:35, 9 May 2009 (UTC)
**:::Both of those certainly make sense. Whichever explanation best adheres to the available sources should probably be added to the article—I'm sure some readers will have the same question I did. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 03:32, 11 May 2009 (UTC)
**::::Added "perhaps because of its effectiveness in solving Diophantine equations." with a citation to the speculating textbook. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:00, 14 May 2009 (UTC)
**<s>"and applied it solving linear Diophantine equations" Consider changing "applied it solving" to "used it to solve".</s>
**::Much better, thank you! [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:35, 9 May 2009 (UTC)
**<s>"Although a special case of the Chinese remainder theorem was described earlier by Chinese mathematician and astronomer Sun Tzu" The use of "earlier" implies a relation to the previous sentence rather than the following clause. Suggest "was described earlier" to "had already been described".</s>
**::Good! [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:35, 9 May 2009 (UTC)
**<s>"The algorithm was first described in Europe in the second edition of Bachet's ''Problèmes plaisants et délectables'' (1624)." Which algorithm? The EA? Or the Chinese Remainder Theorem? Also, do you have a translation for that French title?</s>
**::Clarified EA, translated title. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 03:35, 9 May 2009 (UTC)
**<s>"In the 19th century, Carl Friedrich Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers by 1815 (published 1832), although he did not mention the algorithm in his earlier work, Disquisitiones Arithmeticae (1801), except as a method for continued fractions." If you include specific years, "In the 19th century" is redundant. Also, I'm confused by the 1815/1832 thing. Also, the second chunk is somewhat misleading. Suggested rewrite: "though he had mentioned the algorithm in his earlier work, Disquisitiones Arithmeticae (1801), simply as a method for solving continued fractions."</s>
**::Yes, this was worded awkwardly. I've re-arranged the material and added a topic sentence so that it flows better (I hope). The 1815/1832 issue is that Gauss did the calculation in 1815 (as we know from his notebooks), but didn't publish it until 1832. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 06:42, 11 May 2009 (UTC)
**:::Ah, so much better! --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 23:06, 11 May 2009 (UTC)
**<s>"[[Dirichlet]] seems to have..." A person's full name (or at least their first name) should be given the first time they are mentioned.</s>
**::OK, Peter it is. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 06:42, 11 May 2009 (UTC)
**<s>"would hold true for any other system of numbers in which the Euclidean algorithm could be applied" Should be "to which the", right?</s>
**::Right on! thanks, 06:42, 11 May 2009 (UTC)
**<s>"Dirichlet's insight likely inspired Richard Dedekind to develop theories for new types of numbers, the algebraic integers, and more generally Euclidean domains." As this is written, it implies that Dedekind might or might not have developed those theories. Also, the ending construction implies that "new types of numbers, the algebraic integers, and more generally Euclidean domains" are all separate items in a list, but my hunch is that the second is an example of the first. Suggested rewrite: "Richard Dedekind's theories for new types of numbers, such as algebraic integers and Euclidean domains, may have been inspired by Dirichlet's insight." If you do end up rewriting this sentence, be sure to tweak the following sentence to make sure it flows logically.</s>
**::I made a draft - does it read better now? [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 06:42, 11 May 2009 (UTC)
**:::Looks very good up until this sentence: "Dedekind also defined the concept of a Euclidean ___domain, a number system in which (roughly speaking) a version of the Euclidean algorithm can be defined." Unfortunately, the speaking is so rough that I have no idea what it means. "(roughly speaking)" is unencyclopedic, and the statement that follows doesn't provide any real information.
**::::I changed the wording slightly to "Dedekind also defined the concept of a [[Euclidean ___domain]], a number system in which a version of the Euclidean algorithm can be defined (as described [[Euclidean algorithm#Euclidean domains|below]])." I'm hoping that the wikilink to the fuller explanation within the article itself will satisfy the readers' curiosity. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:04, 14 May 2009 (UTC)
**:::::That's better, but the wording is still a bit odd. "...in which a version of the Euclidean algorithm..." isn't worded in the best possible way, as it leaves the reader thinking "Uhh... what version?" Any adjective before "version" would make this read more smoothly.
**::::::Perhaps "generalized version"? I don't want to have to go into details in the hHistory section about how we need to define the norm and the definition of divisibility in the new sumber system to make an EA work there. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 14:11, 16 May 2009 (UTC)
**<s>"In 1829, Sturm showed..." Not sure why this chunk comes after the Dirichlet/Dedekind bit. I'm assuming that Dirichlet/Dedekind did their work after 1832, which may not be correct. If that is correct, then this section is somewhat out of order. If is not correct, then this is still out of order and specific years should be added for clarity (if possible).</s>
**::I was trying to discern between two developments of the EA in the 19th century: the ''general'' development of new number systems and ''specific'' applications of the EA such as Sturm's theorem. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 06:42, 11 May 2009 (UTC)
**:::Ah. This distinction is clearer now. --'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 23:06, 11 May 2009 (UTC)
**<s>"In 1829, Sturm showed that the algorithm provided an efficient method for counting the number of real roots of polynomials in any given interval." Again, be sure to include given names when introducing people. Also, "efficient method" is currently linked to [[Sturm chain]]. [[WP:MOSLINK]] advises that the article being linked to should be made clear by the words being linked. In this case, I fully expected the phrase to link to an article about the efficiency of algorithms. I suggest rewording the sentence to include "Sturm chain" and then linking that directly.</s>
**:Both good calls. I added "Charles" to Sturm, and I re-arranged the sentence to clarify the Sturm-chain method. I also removed a double link within the paragraph. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:26, 14 May 2009 (UTC)
**<s>"A generalization of this result is known as [[Sturm's theorem]]." The use of the indefinite article "a" implies that there are multiple generalizations of the result, in which case I would recommend swapping out "a" with "one" or explaining the other generalizations. Or both. If this is the only significant generalization, I recommend swapping out "a" for "the". I wouldn't worry about it too much though; if the number of pertinent generalizations was not made clear in your research, "a" will do just fine.</s>
**:Since it wasn't really germane to the EA itself, I dropped the "generalization" sentence. I might add another EA application later, though, to flesh out that paragraph somewhat. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:26, 14 May 2009 (UTC)
**<s>"No new general algorithms were developed until 1979" Erm, I seriously doubt this. I think you may need something more specific than "general algorithms".</s>
**:Reworded to be briefer and to keep within the bounds of the references. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:26, 14 May 2009 (UTC)
**<s>"The PSLQ algorithm, a "jazzed up" version of Euclid's algorithm, has been recognized as one of the top ten algorithms of the 20th century." This is totally irrelevant trivia and really doesn't fit in with the section.</s>
**:Yes, I should've listened to my conscience on this one. Gone. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:26, 14 May 2009 (UTC)
**I'm not sure that the Game of Euclid section belongs in the ''Historical development'' section. It does seem to be worth mentioning in the article, but it really doesn't fit in with the content introduced here. It might be better off being listed in the See Also section.
**:Another difficult call. I sympathize with the critique, but I'm not sure where else to put the discussion. Hitherto I've included the discussion and early in the article, because it's mentioned prominently in some textbooks, it's been the subject of a few research papers, and because I suspect that it might help make some readers more comfortable with the topic, less daunted by the otherwise unbroken wall of math and more likely to push on. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 16:26, 14 May 2009 (UTC)
**<s>It seems odd that the ''Bezout's identity'' section is a subsection of ''Applications''. Applications sections, in my (probably biased) experience, generally deal with how the subject applies to real world problems, not theoretical mumbo jumbo. Some readers will probably jump down to ''Applications'' thinking that they are going to be reading about how the EA can be used in sailing or accounting or whatever. To avoid crushing their tiny little hearts, consider changing ''Applications'' to ''Mathematical applications'', though I may be alone in thinking that this is a good idea.</s>
**::That does seem like a good suggestion; more specific section headings are always better. Changed to "Mathematical applications". [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 14:11, 16 May 2009 (UTC)
**<s>"to the set of multiples of a single number, their GCD g" This would probably be slightly less confusing if "a single number, their GCD g" were replaced with "GCD(a, b)". Much simpler.</s>
**::Excellent idea; changed wording as you suggest. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 01:39, 18 May 2009 (UTC)
**<s>"For example, suppose that a cook has two measuring cups of volume a and b, respectively. By adding and subtracting multiples of these two volumes, the cook can measure out any volume ua + vb. These volumes are all multiples of g = GCD(a, b)." Although I appreciate the real world connection, the inclusion of the cook is somewhat unnecessary and unencyclopedic. This analogy should work with just the measuring cups.</s>
**::Good point; I hope you like the new wording. Thanks for your continued keen reviewing! [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 01:39, 18 May 2009 (UTC)
**"For example, consider two measuring cups of volume a and b, respectively" Why "respectively"?
**"By assumption, this can be written as" I've never heard the term "by assumption" before. If it is indeed the correct term here, perhaps it should be wikilinked.
**The closing lines of ''Extended Euclidean algorithm'' (before ''Equivalent matrix method'') are, to borrow a term of yours, a "wall of math". I think an example with real numbers would be very helpful here, something I'm sure you can find in any math textbook.
**The term ''matrix'' should probably be wikilinked somewhere in the section ''Equivalent matrix method''.
**"The inverse is well-defined" I have the feeling "well-defined" is jargon that should either be wikilinked, explained, or reworded.
**"Bézout's identity is essential to many higher applications" I think "higher" was supposed to be "higher-level", though omitting it entirely would also work.
**"For if the greatest common divisor of u and w is 1, then integers s and t can be found such that" Extraneous "for" at the beginning of this sentence? Perhaps I'm misreading this section.
**"Specifically, if a prime number ''p'' divides ''L'', it must divide at least one factor of ''L''" If you want to introduce a new letter for this sentence, be sure to actually use it: "Specifically, if a prime number ''p'' divides ''L'', ''p'' must divide at least one factor of ''L''". One the other hand, if you want to be brief and reduce the number of letters being thrown at the reader, try this: "Specifically, if a prime number divides ''L'', it must divide at least one factor of ''L''" or "Specifically, if a prime number ''p'' divides ''L'', that prime number must also divide at least one factor of ''L''".
**"where ''a'', ''b'' and ''c'' are also integers" It may be helpful for the reader if "also" were swapped out for "given". This clarifies the distinction between the variables (x, y) and the constants (a, b, c).
**"where s and t can be found by the extended Euclidean algorithm" Throughout the article, you've mentioned several times how the EA is extremely helpful in solving Diophantine equations. However, this is the only line (along with the bit about Bezout's identity, although that is arguably a separate topic) of the section ''Linear Diophantine equations'' that mentions the EA. Perhaps I may be missing something here, but it seems to me that whatever connections exist between the EA and linear Diophantine equations need to be spelled out more explicitly in this section.
--'''[[User:Cryptic C62|Cryptic C62]] · [[User talk: Cryptic C62|Talk]]''' 19:59, 3 May 2009 (UTC)
:::Thank you very much for your careful reviewing! The article is definitely improving. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 10:32, 4 May 2009 (UTC)
'''Comments'''
:1) The spacing convention is not followed consistently through out. (e.g. 252 = 21 × 12 (with space) but 35 = 5×7 (without space), k=0 (with no space))
:::Thank you; I tried to be consistent about this, but a few expressions may have escaped my notice. I'll go through the article myself, but please correct any unspaced expressions that you happen to see. The spaced version (using a non-breaking space) is the correct one. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 21:48, 10 May 2009 (UTC)
:2) "Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of an arbitrary number of integers."
::Can it calculate the GCD of a countable infinite set of integers? An uncountable one? Be specific.
:::You're pulling my leg about the uncountably infinite set of integers, right? I may not be a mathematician, but I wasn't born yesterday. ;) How about "arbitrarily many integers" as a compromise wording? [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 21:48, 10 May 2009 (UTC)
:3) "The latter argument is used to show that the Euclidean algorithm for natural numbers must end in a finite number of steps."
::Citation needed.
:::OK, citation provided. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 21:48, 10 May 2009 (UTC)
:4) Redundant phrase (found a lot at the beginning of paragraphs):
::*"the Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD)"
::*"The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b."
::*"Euclid's algorithm, which computes the GCD of two integers"
::* "The Euclidean algorithm finds the greatest common divisor g of two numbers a and b in a series of steps."
[[Special:Contributions/131.111.216.15|131.111.216.15]] ([[User talk:131.111.216.15|talk]]) 15:58, 8 May 2009 (UTC)
:::I write that way on purpose to provide a touchstone, a "red thread" running through the article for newcomers to grab onto. I may have overdone it, however. I'll go through the article and try to trim the unnecessary. [[User:Proteins|Proteins]] ([[User talk:Proteins|talk]]) 21:48, 10 May 2009 (UTC)
:''The above discussion is preserved as an archive. <span style="color:red">'''Please do not modify it.'''</span> No further edits should be made to this page.''</div><!--FAbottom--><!--Tagged by FA bot-->
| |||