Euclid's Algorithm: An Analysis

http://blog.adamdklein.com/?p=334

by aklein • 15 years ago

37 8 15 years ago

blog.adamdklein.com

prtk• 15 years ago

It is "grand-daddy" of all algorithms! --Don Knuth

jonsen• 15 years ago

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• 15 years ago

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).

tompickles• 15 years ago

Agreed

redxaxder• 15 years ago

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

  17 = 51 - (85 - 51)

  17 = 2 * 51 - 85

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

  17 = 2 * 221 - 3 * 85

aklein• 15 years ago

Cool, you're right, examples are good. Thanks for pointing out!

btilly• 15 years ago

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• 15 years ago

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.

Euclid's Algorithm: An Analysis

Related Stories