HN Explorer

8 comments

[ 3.3 ms ] story [ 21.1 ms ] thread
prtk
It is "grand-daddy" of all algorithms! --Don Knuth
jonsen
Nice analysis if you're into juggling formulas and theorems. I prefer a more pictorial argument like:

  a=24: a a a a a a a a a a a a a a a a a a a a a a a a
  b=18: b b b b b b b b b b b b b b b b b b

  d= 2: d d|d d|d d|d d|d d|d d|d d|d d|d d|d d|d d|d d

  d= 3: d d d|d d d|d d d|d d d|d d d|d d d|d d d|d d d|

  d= 4: d d d d|d d d d|d d d d|d d d d|d d d d|... no good;
multiples of d must hit the ends of b and a

  d:   |                                   |           |


  b=18: b b b b b b b b b b b b b b b b b b
  a-b : a a a a a a

  d:   |           |                       |


  b-(a-b): b b b b b b b b b b b b
  a-b    : a a a a a a

  d:      |           |           |


  b-(a-b)-(a-b): b b b b b b
  a-b          : a a a a a a

  d:            |           |

  d=6
gyom
Clicking on that link I expected something more than just the kind of information given by every math textbook covering Euclid's algorithm (with a sketch of proof).
redxaxder
Euclid's algorithm doesn't make as much sense until you see it done at least once. It's a shame there's no example. Finding the GCD of 85 and 221:

  221 = 2 * 85 + 51

  85 = 51 + 34

  51 = 34 + 17

  34 = 2 * 17 + 0
So our GCD is 17. Why? Well, if we rearrange the parts, we get...

  51 = 34 + 17, so 51 = (2 * 17) + 17 = 3 * 17

  85 = 51 + 34 = (3 * 17) + (2 * 17)

  85 = 5 * 17

  221 = 2 * (5 * 17) + (3 * 17) 

  221 = 13 * 17
So 221 and 85 are both divisible by 17.

Bonus: This also gives us a way to write 17 as an integral combination of 221 and 85. We also get this by rearranging the parts:

  17 = 51 - 34

  34 = 85 - 51

  51 = 221 - 2 * 85
so

  17 = 51 - (85 - 51)

  17 = 2 * 51 - 85

  17 = 2 * (221 - 2 * 85) - 85

  17 = 2 * 221 - 3 * 85
aklein
Cool, you're right, examples are good. Thanks for pointing out!
btilly
Interesting historical note.

The original importance of Euclid's algorithm was that it made calculations with ratios easier. And the reason why that was important was currency conversions.

It is used today in cryptography, which is used for online financial transactions.

One way or another, it all comes down to money. :-)

hammock
Math, counting and numbers in general were developed for trade - so yes it all comes back to "money" (What you really mean to say is trade). When farmers stopped farming for themselves and started trading with others they suddenly had a need to be able to count how much rice and livestock they had.