Wikipedia

Wikipedia:Featured article candidates/Euclidean algorithm/archive1

< Wikipedia:Featured article candidates
This is an old revision of this page, as edited by Proteins (talk | contribs) at 17:04, 5 May 2009 (→Euclidean algorithm: added clarifying sentence to visualization paragraph). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Euclidean algorithm

Nominator(s): Proteins (talk) 16:22, 27 April 2009 (UTC)[reply]
Toolbox

I am nominating this mathematical article because I believe it meets the Featured Article criteria. In its simplest form, the Euclidean algorithm is often taught to 10-year-old children; for many, it is the only algorithm they encounter in school. It has several important applications, such as the RSA algorithm (often used in electronic commerce) and solving Diophantine equations. Although the oldest known algorithm (23 centuries), it continues to play a role in developing new mathematics. It would be helpful for Wikipedia to have an excellent article on this topic, both for itself and for the introduction it provides to advanced mathematics such as abstract algebra. Proteins (talk) 16:22, 27 April 2009 (UTC)[reply]

Game of Euclid
I'm a bit concerned about the inclusion of the "Game of Euclid" in the historical development section. It doesn't seem to be very important as a research topic or achievement, and it certainly doesn't even come close to the other developments in that section. What was the reason for including this? --C S (talk) 17:19, 27 April 2009 (UTC)[reply]
The FA criteria require that the article be "comprehensive" (criterion 1b). I admit that the game of Euclid is relatively unimportant, but it has been discussed in mathematical journals and textbooks, as referenced in the article. There didn't seem to be a better place to put that material besides "Historical development". Proteins (talk) 17:43, 27 April 2009 (UTC)[reply]
Well, I spy less than half a dozen "mathematical journals and textbooks" that mention the game. Surely there are many topics with more coverage that have not been included in this article. So I can't see how omitting this game would violate criterion 1b. Not to mention, these math journals you talk of are mainly math education related ones, except the journal INTEGERS, which seems like an ok journal but not particularly well-known. Of course, I don't mean to disparage journals whose primary audience may be math educators, but in terms of using such journals as a justification for including a mathematical topic in this article, I don't think it is sufficient. One has to separate a topic which is primarily used as an educational device from a topic which is considered an important development in understanding of the Euclidean algorithm. --C S (talk) 19:23, 27 April 2009 (UTC)[reply]
Oldest algorithm?

I think that the sentence "The Euclidean algorithm is the oldest algorithm in the historical record" is wrong because of Old Babylonian algorithms used to solve problems. --El Caro (talk) 18:04, 27 April 2009 (UTC)[reply]

This is a good point. The passage stated is uncited, but there is further down a box with a quote by Knuth which makes the nuanced observation that it is the "oldest nontrivial algorithm" that has survived to the present day. Since Knuth actually wrote an article in 1972 on ancient Babylonian algorithms [1] where he examined written records of their algorithms, presumably he was aware that the "nontrivial" is an important and necessary modifier. "Oldest nontrivial...", of course, is his opinion. --C S (talk) 19:21, 27 April 2009 (UTC)[reply]
I've read the quote in the box. Is this "only" Knuth's opinion or a statement on whom most specialists agree ? --El Caro (talk) 19:39, 27 April 2009 (UTC)[reply]
If "algorithm" is defined only as a set of numerical rules (without requiring proof that the rules always work or understanding why they work), then surely there were algorithms for thousands of years before Euclid. I'll review the literature and list the opinions of other people besides Knuth. Proteins (talk) 20:25, 27 April 2009 (UTC)[reply]
I corrected this in the text before, but that is indeed what "algorithm" means. I have never seen anyone define algorithm to mean it must come with understanding of the person using it or a proof that it works. So I can't imagine Knuth would use some nonstandard definition of "algorithm", as you suggest, especially since he is a computer scientist and certainly computer scientists do not require algorithms come with proofs. That is probably why he says "nontrivial" as I mentioned above. --C S (talk) 20:40, 27 April 2009 (UTC)[reply]
After consulting more than a dozen mathematical sources, I concede that you are entirely correct. An algorithm is any well-defined (alpha)numerical procedure, and can well be incorrect. Thus, pre-Pythagorean carpenters constructing a right angle by a 3-4-5 triangle were using an algorithm, and so were carpenters who used a 2-3-4 triangle. I accepted the proof requirement (which I read elsewhere) because Knuth's argument for the EA's priority seemed incompatible with the obvious prior existence of many algorithms, such as calendars, money changing, tax and inheritance systems, measurement of area, architecture, multiplication and division, etc. I have also not found a reliable source besides Knuth that identifies an oldest nontrivial algorithm. The solution for this FAC may well be to leave the quote box from Knuth, but to change the assertion in the article. How about "oldest numerical algorithm still in common use", or "one of the oldest algorithms in the historical record"? Would either of those wordings be acceptable? Proteins (talk) 02:45, 29 April 2009 (UTC)[reply]

Hi Proteins. Well, as you said, multiplication algorithm was around before, so I'm unhappy with the first phrasing. The second seems acceptable. Actually, I had a bit of fun digging around the Google searches for "euclidean algorithm oldest". I had no idea that there was such a common misconception of the Euclidean algorithm being the oldest algorithm (with no qualification). Perhaps Wikipedia itself has had a role in perpetuating this. In "Mathematica in Action" by Stan Wagon [2], Wagon asserts "The Euclidean algorithm for computing the gcd of two numbers is arguably the best algorithm in all of mathematics. According to Knuth, it is the oldest nontrivial algorithm that has survived to the present day." So here Knuth's assertion of "oldest nontrivial..." is repeated with the addition that it is the best algorithm bar none. However, misleadingly, the section heading proceeding the passage states "The oldest surviving algorithm"! In this book, the author asserts, the "Most likely, it is the oldest mathematical algorithm in existence". Oops! Anyway, although the Wagon claim is on the strong side, I think the Knuth quote really has some content there. So I think we ought to keep that in the box, while in the text we can make a more unobjectionable assertion like "one of the oldest...record". --C S (talk) 06:56, 29 April 2009 (UTC)[reply]

Applied to real numbers

"Euclid's algorithm can be applied to real numbers, as described by Euclid in Book 10 of his Elements" looks like an anachronism. Did Euclid know real numbers ? --El Caro (talk) 18:17, 27 April 2009 (UTC)[reply]

Well, now we're getting into metaphysical matters that I think are tangential. For example, when Euclid considered arithmetical operations on whole numbers, it's not the same in a sense as what we consider such arithmetic, nor is probably what the ancient Greeks considered whole numbers the same as what we do now. So strictly speaking Euclid did not know real numbers, but he didn't know whole numbers, addition, or subtraction either. So that makes your point kind of moot. --C S (talk) 19:21, 27 April 2009 (UTC)[reply]
The ancient Greek certainly knew about irrational numbers, at least as surds, even if they hadn't defined Dedekind cuts. Book X of Euclid's Elements is devoted entirely to questions of incommensurability, and this real-number version of Euclid's algorithm begins that exposition. Knuth states elsewhere that the Greeks treated real numbers by infinite continued fractions, but he doesn't explain his remark further; I took him to be referring to this version of Euclid's algorithm. One could argue, I suppose, that the modern concept of real numbers embraces more than just "the set of all rational and irrational numbers", but that seems beyond the level of this article. Proteins (talk) 20:18, 27 April 2009 (UTC)[reply]
Ancient Greeks considered numerical concepts mainly in terms of geometric constructions ala ruler and compass and that is how Euclid's treatment of commensurability goes. This is certainly not the way modern mathematicians think of them. Sure the ancient Greeks knew of some irrational numbers, but they certainly didn't know "e" or many other irrational numbers that are not constructible. So their concept of irrational number was far more limited than our modern understanding, even when one limits the concept of real number to mean "set of rational and irrational numbers". Even on the math where modern and ancient understanding would seem to overlap, it's clear the ancient Greeks just had a different way of thinking about it, so in a metaphysical sense, you could argue that the objects are really different. --C S (talk) 20:40, 27 April 2009 (UTC)[reply]
Oppose on criterion 3
  • File:Gabriel-Lamé.jpeg - There is no source, date, or author for this image that would lead us to believe that it is in the PD. We need to be able to verify that it is in the PD. More research on this image needs to be done.
  • File:Dedekind.jpeg - The website for this image does not indicate the 1870 date and we have no name or death date for the photographer, so we cannot verify the PD license listed. More research on this image needs to be done.

These issues should relatively easy to resolve. I look forward to reading the entire article. Awadewit (talk) 21:13, 27 April 2009 (UTC)[reply]

Unfortunately, despite a diligent search, I have not been able to verify the copyright status of either image. Both were taken around 1870 (roughly 140 years ago) and both are widely distributed on the Internet. However, it is conceivable that the original photographer died less than 70 years ago, or that the photographs themselves were not published until more recently. I found a similar image of Lamé published in 1897, but the Ecole polytechnique asserts its unrestricted copyrights. I found an alternative photograph of Dedekind published in 1930 in Braunschweig as part of his Collected Works; however, I cannot verify that it is out of copyright, either. I'll remove the images for now, pending a fuller investigation. They're not essential. Proteins (talk) 02:45, 29 April 2009 (UTC)[reply]
Ah, good news! We can use the Lame picture from 1897 then. It doesn't matter if Ecole Polytechnique claims copyright; US copyright law is what Wikipedia requires us to follow and that means the picture is considered in the public ___domain in the US (see Wikipedia:Public_domain). --C S (talk) 04:42, 29 April 2009 (UTC)[reply]
We can use the the French Lamé. As CS explains, it is acceptable under US copyright law. You can upload it to the English Wikipedia. Awadewit (talk) 01:11, 30 April 2009 (UTC)[reply]
Lack of citations?
  • Problem - many of the paragraphs are lacking citations or, if having them, there are no citations covering many sentences. See the end of the section "Greatest common divisor" for just one example. This needs to be fixed before it can pass FAC. Ottava Rima (talk) 23:45, 27 April 2009 (UTC)[reply]
    • If you are referring to the subsection that begins, "Three related mathematical methods are used often in the arguments below..." That is an explanatory paragraph explaining the article elements, in particular, explaining what typical math proof method will be used further down. That does not require citation. Looking through the article, I see plentiful citations. I suspect what Ottava Rima is referring is to paragraphs where the initial statement might be sourced, but further explanation or example is not (although it is simply a further explication of what the initial sentence said). I wonder if Ottava Rima is familiar with WP:SCG, since I cannot see how the article fails the SCG. I think there is some confusion that would be remedied by reading "Examples, derivations and restatements" section of the SCG in particular. --C S (talk) 23:58, 27 April 2009 (UTC)[reply]
      • Unless it is sourced, it is possibly Original Research. Now, from the guideline that you quoted: "The no original research and verifiability policies are of paramount importance to Wikipedia. Information presented in Wikipedia should be easily verifiable by anyone who wishes to do so. To ease verification, sources should be detailed by the articles." This article fails that. The whole page has over 50 sections needing citations. Such things are 100% unacceptable in an FA. Ottava Rima (talk) 00:26, 28 April 2009 (UTC)[reply]
        • You've been claiming a lot citation violations, but have yet to demonstrate one example. Could you show me an example paragraph from the article that violates the SCG? You cited the opening sentences of the SCG, but I'm not sure you've read further past it since the rest of the introduction explains that there are different ways to satisfy these core polices. Then further on down in the first section it is explained that not every sentence or paragraph may require a citation depending on the type of material. --C S (talk) 01:27, 28 April 2009 (UTC)[reply]
          • Violations? No. FA has as a requirement that everything is verifiable. This requires all information to be cited. There are over 50 spots that need citations. I read through the whole article, as, when working on my classics degree, Euclid books 1, 2, 3, 5, and 6 were included, so a page dealing with Euclid is something that I find interesting. Ottava Rima (talk) 03:08, 28 April 2009 (UTC)[reply]
            • Yes it's true that FA has a verifiability criterion. But it does not automatically follow that all information is needed to be cited. This is a logical jump not supported by any listed policy, guideline, or FA criterion. In addition, SCG has been found to be satisfactory in prior FA nominations by Raul and Sandy. So I'm afraid your opinion is just your opinion, without consensus, and will probably be ignored as far as this nomination goes. --C S (talk) 03:51, 28 April 2009 (UTC)[reply]
            • I agree with CS. Please re-read Wikipedia:Verifiability to gain a better understanding of the policy. My only quibble with respect to verifiability was the "oldest algorithm" bit. The discussion above has laid that objection to rest. Lwnf360 (talk) 06:10, 28 April 2009 (UTC)[reply]
              • Sorry, you two, but I've been here for a long time, I've worked on many FACs, FARs, and the rest. I know what the verifiability criterion is. Your arguments have shown that this wont be corrected, so I have no choice but to oppose. 13:20, 28 April 2009 (UTC)
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. Proteins (talk) 02:45, 29 April 2009 (UTC)[reply]
I've added 22 more references. Proteins (talk) 17:20, 30 April 2009 (UTC)[reply]
Comment on terminology

Often in math books, the Euclidean algorithm is not the actual procedure for finding the GCD, but rather the statement that for two a, b (natural numbers, integers, residue classes of integers, polynomials over commutative rings, power series over complete local rings, and so forth) we can solve the equation:   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. Fowler&fowler«Talk» 17:43, 28 April 2009 (UTC)[reply]

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? Proteins (talk) 02:45, 29 April 2009 (UTC)[reply]
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 [3]). 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. --C S (talk) 04:59, 29 April 2009 (UTC)[reply]
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 A Course in Modern Algebra (1989), Rowen's Algebra: Groups, Rings, and Fields (1994), Lang's Algebra: A Graduate Course (2002), Murty and Esmonde's Problems in algebraic number theory (2004), Lang's Undergraduate Algebra (2005), and Lowen's 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! Fowler&fowler«Talk» 12:26, 29 April 2009 (UTC)[reply]
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). --C S (talk) 20:47, 29 April 2009 (UTC)[reply]
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. --C S (talk) 21:01, 29 April 2009 (UTC)[reply]
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 Graduate Algebra: The Noncommutative View (2008), published by the AMS does look recent. Anyway, this is not a biggie for me. Regards, Fowler&fowler«Talk» 22:23, 29 April 2009 (UTC)[reply]

I understand and agree wholeheartedly. Perhaps I should have forestalled your comments by mentioning that Herstein is still a widely used book. --C S (talk) 23:02, 29 April 2009 (UTC)[reply]

I have added the following as a footnote to the introductory sentence: Some widely-used textbooks, such as I. N. Herstein's Topics in Algebra and Serge Lang's Algebra, use "Euclidean algorithm" to refer to division algorithm.

I don't know if that's the best place for it, but it should save some confusion on terminology. --C S (talk) 23:09, 29 April 2009 (UTC)[reply]

Comment on animation in lead
I've found a way to hide the animation until it's requested. Proteins (talk) 17:20, 30 April 2009 (UTC)[reply]
Intelligibility

It's excellent that the atmosphere here is cordial and constructive; I appreciate everyone pitching in to make the article better. For my part, I'm determined to make the article as intelligible as possible to lay-readers. I'd appreciate advice on how to do that, or alerts to obscure sections. Thanks! (We should continue this discussion on the article talk page.) Proteins (talk) 17:20, 30 April 2009 (UTC)[reply]

  • The article should NOT have its technical aspects toned down. Readers searching for information on the topic will 9 times out of 10 be looking for the technical explanation. The technical explanations are excellent. Lwnf360 (talk) 23:08, 30 April 2009 (UTC)[reply]

Thank you, and no worries! I just want to avoid unnecessary obscurity. Proteins (talk) 00:01, 1 May 2009 (UTC)[reply]

!Votes
  • Conditional Support. Overall, the article is excellent and it certainly meets criteria 1 and 2. In fact, arguments could be made that the article is too comprehensive i.e. includes too much on related topics (criterion 4). However, I would not support that argument. The image copyright issues raised by Awadewit should be corrected. Unless I have missed something major, in my view, the article should be featured. Lwnf360 (talk) 06:10, 28 April 2009 (UTC)[reply]
Thank you, and I hope that the copyright issues will now be resolved. Proteins (talk) 02:45, 29 April 2009 (UTC)[reply]
  • 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.) Jakob.scholbach (talk) 21:47, 29 April 2009 (UTC)[reply]
    • Yet, is that not why we have separate articles on mathematical induction, recursion and infinite descent? Each of which has a well-written, extensive introduction, and with the except of 'infinite descent' has plentiful references? Is your suggestion because you don't like the look of a paragraph without footnote symbols? I'm genuinely confused by your comment, as we don't have a reference in the article for many other terms either (like ideal (ring theory). I would suggest just adding some references to infinite descent instead. --C S (talk) 23:02, 29 April 2009 (UTC)[reply]
      • Oh, that was not my intention. It is not that I a priori don't like paragraphs without footnotes, I just think it is a service to the reader to come up with a reference. For example mathematical induction does give a number of references, which is good, but assume you don't have the time nor ability to read that article nor scan all the references given there. In that case, an additional reference (in this article here) would be helpful, wouldn't it? Secondly, it is reassuring to have good surrounding articles, but you can't be sure of what happens with them. (You are right, taking that idea seriously would also mean to add references for all other notions like ideals, but I think ideals are far less crucial to the EA than induction etc.) Jakob.scholbach (talk) 06:16, 30 April 2009 (UTC)[reply]
        • Regarding the first concern I suppose I have a hard time seeing how providing a reference footnote would be helpful. If I don't have time to read one of the linked articles, I don't see why I would have time to go look up some reference in the library or read some other website or read some downloaded paper. I can see the point of the second concern, that something bad can happen to a linked article. I suppose it doesn't hurt to copy over some of the references from those articles; I'd feel a bit too silly doing that myself, so I'll leave that to you :-). --C S (talk) 06:57, 30 April 2009 (UTC)[reply]
  • Leaning to support. I haven't looked through the the whole article, but will do so. The "Game of Euclid" thing is not a good addition, but that can be argued (by those who care to) on the article talk page. Other issues discussed above all seem resolved. --C S (talk) 23:02, 29 April 2009 (UTC)[reply]
  • Support the lead - I have a very hard time reading mathematics articles. I tried very hard to understand this, but I kept getting lost. I understood the lead, but after that, not much. I'm too verbal, I suppose. (Even the diagrams slightly confused me. I was like, "why are there 10 squares?") Anyway, the lead makes sense to idiots such as myself. Awadewit (talk) 01:18, 30 April 2009 (UTC)[reply]
    • Perhaps the 10 square example could be improved. It's not important the exact numbers that are being used there. The basic idea is that the gcd of two numbers is the largest length which can be used as a unit for both numbers. So for the two numbers illustrated by the 10 square picture, the gcd fits in one number twice and fits in the other number 5 times. This is illustrated by the 5 x 2 grid. There is no way to tile that rectangle with a bigger square. --C S (talk) 01:40, 30 April 2009 (UTC)[reply]
    • Ok, so I rewrote the passage with the visualization example to say:

      Imagine a rectangular area a by b. Suppose d divides both a and b with no remainder. So we can divide the sides of the rectangle into some number of segments of length d and furthermore divide the rectangle into a grid consisting of squares of side length d. The greatest common divisor g equals the largest value of d for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 6×6 squares or 12×12 squares. Thus, 12 is the greatest common divisor of 24 and 60.

      Is this an improvement? --C S (talk) 07:11, 30 April 2009 (UTC)[reply]
  • Minor suggestion for improvement. The animated gif File:Euclidean algorithm 1071 462.gif is a very nice idea, especially for readers with limited math knowledge. But it would be more useful if the dimensions of the successive rectangles were given. (Hope you see what I mean) They're given in the caption but that forces the reader to look at the image, go to the caption, return to the image and pedagogically I think that's suboptimal. Also I think it's one of these rare cases where it makes sense to point out on the caption that clicking on the image will enlarge it (many readers are unaware of this). Pichpich (talk) 16:11, 1 May 2009 (UTC)[reply]
Those are both good suggestions, Pichpich, thank you. Although they may be more difficult to implement elegantly than you imagine, I'll work on them. Originally I left the numbers out of the animation on purpose, because I wanted it to be usable on other Wikipedias that do not use our digits, such as the Arabic Wikipedia. Proteins (talk) 10:25, 3 May 2009 (UTC)[reply]
  • Support. I really like this article. It's comprehensive, well-written, interesting, and informative. I do have one minor quibble, although I'm not sure anything can be done about it, and it's that at least on my laptop screen some of the formulae are difficult to read. For instance, in
rk−2 = qk rk−1 + rk
qk rk−1 looks like qk to the power of rk−1. It may just be an artefact caused by the tail of the "q" though, either that or my tired old eyes. :-) If nobody else has a similar problem I'll just chalk it down to my default character set. --Malleus Fatuorum 13:57, 2 May 2009 (UTC)[reply]
Thank you! I sympathize with the small-equation issue, although the equations read correctly on my screen. The equations could've been rendered better in math mode (LaTeX), but that approach produces images that are not accessible to people using standard screen readers. Perhaps the best long-term solution for Wikipedia and other Wikimedia projects would be a script that generates ALT text automatically for a given math-mode equation, while allowing the editor to fine-tune its output. That would require a major investment of time and effort, however. Proteins (talk) 10:16, 3 May 2009 (UTC)[reply]
  • Comments from Cryptic C62 · Talk
    • The lead does not adequately summarize all of the main sections of the article. Unless I am misreading, it appears that Other number systems is not represented in the lead.
      Apparently you missed the sentence "In the 19th century, the algorithm was generalized to other types of numbers, which led to modern abstract algebraic notions such as Euclidean domains." in the lead. But you're right, that's too terse, so I expanded it to "The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains." Proteins (talk) 09:59, 4 May 2009 (UTC)[reply]
    • Caption: "The greatest common divisor of a and b is the largest square tile that covers an a-by-b rectangle exactly. Here, a 24-by-60 rectangle is covered with 12-by-12 square tiles." In the first sentence, it needs to be made clear that it is not one single square tile that covers the rectangle, but multiple iterations of that square tile. "exactly" is somewhat ambiguous, consider expanding. It would also be helpful to say "ten 12-by-12 square tiles". Addendum: upon reading the relevant paragraph, it might be helpful to make this into an animation which demonstrates the various ways in which a 60-by-24 rectangle can be divided.
      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? Proteins (talk) 09:59, 4 May 2009 (UTC)[reply]
      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? --Cryptic C62 · Talk 18:52, 4 May 2009 (UTC)[reply]
    • "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.
      Mentioned ambiguity of "(a, b)" notation, and swapped order of last two sentences in paragraph for better flow. Proteins (talk) 10:10, 5 May 2009 (UTC)[reply]
      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 vectors."
    • "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. Also, shouldn't it be "neither 6 nor 35 are prime numbers" ?
      Excellent suggestion for the rewording. Proteins (talk) 09:59, 4 May 2009 (UTC)[reply]
      Neither/nor - it depends if you think 6 and 35 are singular or plural. Are they singular because they are individual numerals or are they plural because they abstractly represent "more than one"? Tricky. Awadewit (talk) 20:05, 3 May 2009 (UTC)[reply]
      Hrm. Well, I'm not particularly sure about it myself, so use your best judgment. I just wanted to bring it to your attention. --Cryptic C62 · Talk 22:23, 3 May 2009 (UTC)[reply]
      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 approximately 7 million hits, whereas "Neither * nor * are" has 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. Fowler&fowler«Talk» 22:40, 3 May 2009 (UTC)[reply]
      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". Proteins (talk) 10:06, 5 May 2009 (UTC)[reply]
    • "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."
      I presume that you are not objecting to the imperative mood (a staple of mathematics: "Let x be..."), just the verb "imagine". I re-worded this to use "consider" for both: "Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly." Since this is an encyclopedia, we should both strive to keep our comments less colorful. Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
    • "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 "then GCD(462, 1071) = 3×7"?
      Thank you for catching that inconsistency, which I've fixed. Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
    • "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" ?
      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? Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
      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. --C S (talk) 11:36, 4 May 2009 (UTC)[reply]
      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. Proteins (talk) 13:59, 4 May 2009 (UTC)[reply]
    • "A more subtle definition of the GCD is helpful in advanced mathematics, particularly ring theory." This statement should probably be accompanied by a ref.
      OK. Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
    • "GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c)" Shouldn't this also include " = GCD(GCD(a, c), b)"?
      If only for symmetry. Good catch! Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
    • "Thus, Euclid's algorithm, which computes the GCD of two numbers, suffices to calculate the GCD of arbitrarily many numbers." Odd wording at the end. Suggest switching to "integers" to allow the following rewrite: "Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of any number of integers."
      That's a good point and a good rewording. By using the word "number", I was trying to be general, since this result applies not only to integers, but to any number system for which the EA works, such as real numbers or Gaussian integers. Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
      Well, if you'd still like to stick with "numbers" rather than "integers", how about this: "Thus, Euclid's algorithm, which directly computes the GCD of two numbers, can be used to calculate the GCD of any group of numbers, regardless of the size of the group." Or something? As long as we avoid phrases like "number of numbers", it should be fine. --Cryptic C62 · Talk 18:52, 4 May 2009 (UTC)[reply]
    • "This approach begins by showing that, if the theorem holds for n, it also holds for n + 1." I just learned about induction last semester, and this doesn't seem to be quite right, specifically the last two clauses. My understanding of induction is that it is a two-step process. The first step is proving the basis case (usually n=0 or n=1), and the second step is proving that it holds for n+1. The sentence in question is written as though the first step proves the second step, which is not the case.
      For induction, it doesn't matter whether you prove the basis case first and the (n implies n+1) step second, or the reverse. I chose to present the method in the reverse order because (1) I thought it would be easier for lay-people to follow, (2) it emphasizes the (n implies n+1) step, which I feel is more important; and (3) it de-emphasizes the basis case and clarifies that a proof could start with any basis case, e.g., n=7. Proteins (talk) 09:36, 5 May 2009 (UTC)[reply]
      Hmm. I've reread that section, and I'm not sure why I had a problem with it the first time, as it makes perfect sense to me now. Perhaps I should have read the entire section before commenting on individual sentences... --Cryptic C62 · Talk 16:31, 5 May 2009 (UTC)[reply]
    • "A recursion is an equation relating numbers that form a series a1, a2, a3, etc." This is a very poor definition of a recursion, as it does not adequately explain the concept to a reader with no prior familiarity to it. How about "A recursion is an equation in which an, an arbitrary term in a series, is defined by the values of previous terms in the series, such as an-1 or a0". This will also help the reader understand the Fibonacci example a bit more clearly.
      That's a good suggestion. I've re-worded the recursion along these lines. Proteins (talk) 09:36, 5 May 2009 (UTC)[reply]
    • "Several equations associated with the Euclidean algorithm are recursive, such as rk = rk−2 − qkrk−1." This example is essentially useless, as neither the meaning of the equation nor the terms used therein have been defined yet.
      Eliminated foreshadowing. Proteins (talk) 09:36, 5 May 2009 (UTC)[reply]
    • "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.
      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. Proteins (talk) 09:36, 5 May 2009 (UTC)[reply]
    • "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."
I had avoided that wording for fear that mathematicians would cavil that the "proof" was not rigorous. I prefer your wording, however, so I replaced it. Proteins (talk) 16:58, 5 May 2009 (UTC)[reply]
    • "This agrees with the GCD(1071, 462) found by prime factorization above." Erm, there is no mentions of 1071 or 462 in the Background section. Why not just give the prime factorization here?
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. Proteins (talk) 16:58, 5 May 2009 (UTC)[reply]
    • "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.
Excellent suggestion, thanks! Proteins (talk) 17:04, 5 May 2009 (UTC)[reply]
    • "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? rk < rk-1
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. Proteins (talk) 16:58, 5 May 2009 (UTC)[reply]
    • "Euclid finds the quotient and remainder by repeated subtraction" Last time I checked, Euclid is dead. Past tense, perhaps?
Perhaps passive voice, instead. Proteins (talk) 16:58, 5 May 2009 (UTC)[reply]
    • "rk ≡ rk−2 mod rk−1" Is there some article to which we can link '≡'? I'm not sure I know what it means.
It means "equivalent to" in modular arithmetic. I'll make a link. Proteins (talk) 16:58, 5 May 2009 (UTC)[reply]
Thank you very much for your careful reviewing! The article is definitely improving. Proteins (talk) 10:32, 4 May 2009 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Wikipedia:Featured_article_candidates/Euclidean_algorithm/archive1&oldid=288085085"