News for hackers. Stuff that matters.
Re:Euclid's Algorithm: An Analysis by jonsen on Saturday July 16, 2011 @12:43PM (#2771060)
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

There are no comments on this comment yet.