Timeline for Why is this gcd implementation from the 80s so complicated?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 23, 2020 at 21:02 | comment | added | mathmandan | @MishaLavrov Agreed! | |
| Dec 23, 2020 at 20:59 | comment | added | Misha Lavrov | @mathmandan And I think once we make that optimization, we're back to the code in the question! | |
| Dec 23, 2020 at 20:07 | comment | added | mathmandan |
@MishaLavrov Yes! But if you work in binary then you can also easily divide out the powers of 2 as you go. Example: gcd(1000000, 2) = 2*gcd(500000, 1) = 2*gcd(15625, 1) = 2*gcd(15624, 1) = 2*gcd(1953, 1) = 2*gcd(1952, 1) = 2*gcd(61, 1), etc. Following every subtraction step you get an even number in one entry or the other, which you can then divide by 2 (or more). That way it's not quite so regrettable...although granted, it does not seem like the best way to do this example!
|
|
| Dec 23, 2020 at 18:42 | comment | added | Misha Lavrov | @CSM Mathematically speaking, yes; in practice, you will regret doing that if you're computing the GCD of 1000000000 and 2. | |
| Dec 23, 2020 at 16:22 | comment | added | CSM | Note that if you know that both numbers are positive, then you can replace the modulo with a pair of subtractions. en.wikipedia.org/wiki/… | |
| Dec 23, 2020 at 9:12 | comment | added | John U |
As I said, for the sole purpose of dating a piece of code containing goto it doesn't matter what anyone thinks of it.
|
|
| Dec 23, 2020 at 9:04 | comment | added | Mark Morgan Lloyd | I agree up to a point, but would remind you that Dijkstra himself became unhappy about the extent to which avoidance of goto became treated as a religious tenet (see the archive of his papers). | |
| Dec 23, 2020 at 8:59 | comment | added | John U |
True, but he does make a good point and it's held true for ~50 years so I don't think it was too extreme. Looking at the state of modern code I can only imagine how bad it would be if we were throwing goto in everywhere with wild abandon. Anyway, the title isn't important here - it's the effect - and the fact that goto rapidly fell from favour helps date the text of the book.
|
|
| Dec 22, 2020 at 17:23 | comment | added | Mark Morgan Lloyd | Please remember that "considered harmful" was not Dijkstra's choice of title: it was Wirth's and judging by Wirth's early code was more than a little tongue in cheek. | |
| S Dec 22, 2020 at 16:01 | history | suggested | Andreas Rejbrand | CC BY-SA 4.0 |
improved grammar and spelling
|
| Dec 22, 2020 at 15:54 | review | Suggested edits | |||
| S Dec 22, 2020 at 16:01 | |||||
| Dec 22, 2020 at 15:17 | history | answered | John U | CC BY-SA 4.0 |