Euclid's Algorithm: An Analysis(blog.adamdklein.com)

37 pointsby akleinvor 15 Jahren8 comments

blog.adamdklein.com

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

5 comments

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

akleinvor 15 Jahren

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

btillyvor 15 Jahren

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

hammockvor 15 Jahren

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.

jonsenvor 15 Jahren

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

gyomvor 15 Jahren

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

tompicklesvor 15 Jahren

Agreed

prtkvor 15 Jahren

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