Timeline for Comparing different Euclidean algorithms on a Euclidean domain
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2022 at 8:13 | history | edited | CommunityBot |
replaced http://math.uga.edu/~pete with http://alpha.math.uga.edu/~pete
|
|
| Apr 13, 2017 at 12:19 | history | edited | CommunityBot |
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
|
|
| Mar 21, 2014 at 11:16 | history | edited | Torsten Schoeneberg | CC BY-SA 3.0 |
addendum
|
| Sep 26, 2013 at 10:59 | comment | added | Torsten Schoeneberg | Thanks for the comments. Colin McLarty: Sure. My question then would be how your last two sentences could be made precise. Franz Lemmermeyer (1st comment): Sure. My question is whether anything in this direction can be said, exactly because the trivial bound mentioned in my question is worthlessly crude. Sorry for not being clear enough on this. | |
| Sep 24, 2013 at 16:22 | comment | added | Colin McLarty | What Motzkin calls an algorithm is not an algorithm in the sense of a calculating routine. It is a norm on the ring with certain order theoretic properties (none concerning calculability). He calls one 'faster' than another if it consistently gives results closer in that order to the GCD. In general there need not be any calculating routine and in any case none needs to be specified. His parenthetic remark says that under further conditions this will agree with the idea of requiring fewer steps. Probably the further conditions relate to the classical Euclidean algorithm computinge gcd's. | |
| Sep 24, 2013 at 15:44 | comment | added | Franz Lemmermeyer | As for your last question I think you can easily come up with counterexamples. | |
| Sep 24, 2013 at 15:42 | comment | added | Franz Lemmermeyer | If you compare algorithms, you should not do this by looking at crude upper bounds on the number on steps; what you need are upper bounds that are attained (worst case) or bounds on the average number of steps. | |
| Sep 24, 2013 at 15:31 | history | asked | Torsten Schoeneberg | CC BY-SA 3.0 |