Talk:Extended Euclidean algorithm

From Wikipedia, the free encyclopedia

To-do list for Extended Euclidean algorithm:

edit · history · watch · refresh

Explain and compare the similarity and difference between the two methods of the algorithm(one using double recursion, another using tail recursion;the first one work forward, the second one work backward, so on...) Wikify(Make it into a table) the equations showing this algorithm in the first example. Done Lemontea Cleanup the informal formulation section, explaning the example in more detail. Done Lemontea Add a proof of correctness section. Not quite needed, afterall, since it's just an extension. Lemontea Wikify the pseudocode, bold the keywords like else, return, etc.Done Lemontea Reorganise(and refactor, since it's too long now) Cleanup the formal description section. Maybe we can do better in explaning how to find out the x and y in a concise and clear manner.(Use the now deleted Algebraic formulation as a reference) Have an implementation section with one simple code, and one more complete code.(Not sure whether this is neccessary, depends on how good the pseudocode is) Needs links to Linear congruence theorem Start a section on the significance of the extension as compared to the original euclidean algorithm(e.g. finding inverses) Mention and/or explain (faster) binary version of the algorithm (e.g., The Art of Computer Programming, v. 2, ed. 3, section 4.5.2, exercise 39 — explanation and references in Answers to Excercises)

needs links to Linear congruence theorem. Dmharvey Talk 5 July 2005 17:46 (UTC)

Contents 1 Unclear pseudocode 2 gcd/hcf 3 The two methods 4 Leftover 5 Link to .exe file 6 Matrix form 7 Soure code reference removed 8 Table method

[edit] Unclear pseudocode

I liked the (now deleted) mathbook-like algebraic formulation that I gave in [1]. IMO, the pseudocode here doesn't really make the mathematics clear. Should I resurrect the "algebraic formulation" section?

Another problem is that the pseudocode doesn't currently state preconditions/postconditions/behavior of mod with negative integers/etc. Thus its correctness depends on the prejudices of the reader (i.e. it's informal). Regardless of whether people want the algebraic formulation back, I think these problems should be cleared up with the pseudocode. - Connelly 01:28, 14 December 2005 (UTC)

I think there should definitely be pseudocode, but I object to the horrendous verbosity of the current listing and its failure to state assumptions. It may be best to have two versions, one simple but not fully general and one handling all cases. In Bresenham's line algorithm I developed the pseudocode in stages to ease complexity. Deco 01:43, 14 December 2005 (UTC)

[edit] gcd/hcf

hello. Don't you think it is confusing to have this gcd/hcf thing all along the text?

I believe that if this hcf thing is really important at all, this alternative name should stick to that phrase in the first sentence.

If someone here really belives that HCF is the best name to call the gcd, then perhaps we can change the whole text to hcf, and keep gcd only in the first sentence. It's extremelly awkward to me, but it's better than having the operation called by two names all the time, don't you think?...

Every mathematical text have this problem with what nomenclature to adopt. This is to be defined on a prologue, and the rest of the text should use a unique notation and nomenclature. Bringing the problem to the body of the text is extremmlly confuse.

agree 100% ... should stick to gcd after introduction Dmharvey Talk 9 July 2005 14:02 (UTC)

Also for the pseudocode below, it would be nice to mention that "<>" means not equals to. Does any programming language use that syntax. Is it a standard syntax used in psuedocode?

Several languages use it, mostly notably BASIC. It should use ≠ in the article, however. Deco 01:45, 14 December 2005 (UTC)

[edit] The two methods

Notice that the first method in article is iterative rather than recusive in nature: it employs the quotient in the same order they appear/ the algorithm proceed forward. Compare this with the second method described, which is really a recursion and notice how they use the quotient in the reverse order they appear/ it work backward. Thus it is reasonable that the pseudocode is so long and seemingly complicated in the first method: it uses recursion rather than iteration. I suggest the code and the function call can be rewritten in an iterative fashion. Thanks. --Lemontea 14:47, 26 January 2006 (UTC)

[edit] Leftover

I've refactored quite some sections of this article, here are something I would like to see get handled:

1. Cleanup the informal description part I've written. Proofread it, check its tone, etc.
2. Help format the table and layout of this article in general.(e.g. the last table in the iterative method section could do some highlighting, just as the last table do)
3. Gives commments on the style of the informal formulation section: is it suitable to intermix the example with the theory(that is, explain the theory, then demostrate it in action, then some theory again, and so on), or is it good to completely separate them? Partly because of the messy nature of this algorithm, and partly because of easy understanding and readibility(could have drowned off if it were pure theory), I've chosen the first one.
4. Does The formal description part need a description of finding out x and y: just like those written out by bulleted list(see other algorithm page for examples), or does the pseudocode suffice?

That's all I can think up with now. Thanks. --Lemontea 15:15, 17 February 2006 (UTC)

[edit] Link to .exe file

I removed a link to an .exe file (presumably a Windows executable, compiled from one of the source code examples). Since there are other, safer, demonstrations, I think it's worth it to minimise the risk of Wikipedia being used to spread malicious software.

In case someone strongly disagrees, I left the original link commented out in the references section.

Robert 21:35, 11 May 2006 (UTC)

[edit] Matrix form

There is a representation of the EEA step -- that x_{i + 1} = x_{i − 1} − q_ix_i; y_{i + 1} = y_{i − 1} − q_iy_i thing -- as a matrix multiplication. Mine source is Gregory & Krishnamurthy, "Methods and Applications of Error-Free Computation", Springer, 1984. The respresentation itself is

and is IMHO rather understandable and brings some more insight as the notation used in this article. --88.68.34.243 12:44, 9 June 2006 (UTC)

[edit] Soure code reference removed

I've remmoved the link to the C++ source code program as it seems like a broken one :

azi@magicb0x ~ $ g++ mulinv.cpp mulinv.cpp:3:16: error: ronh: No such file or directory mulinv.cpp: In function 'int main()': mulinv.cpp:50: warning: converting to 'int' from 'double' mulinv.cpp:53: error: 'mod' was not declared in this scope mulinv.cpp:72: error: 'mod' was not declared in this scope mulinv.cpp:89: error: 'mod' was not declared in this scope azi@magicb0x ~ $

[edit] Table method

One should explain the table method more accurately. The method described does not return the values shown in the table, neither for using always 5 nor for using the divider...

divider:

1 0 120

0 1 23

1 -5 5

-3 16 3

7 -37 2

-10 53 1

5:

1 0 120

0 1 23

1 -5 5

-5 26 3

26 -135 2

-135 701 1