The Euclidean Algorithm (for finding the greatest common divisor)

CJam, 46 43 39 bytes

q~]$3*~\{N5$"=("3$:G'*3$Gmd")+"\}h]7>NG

Try it online in the CJam interpreter.

How it works

q~]    e# Read all input, evaluate it and wrap the results in an array.
$3*    e# Sort the array and repeat it thrice.
~\     e# Dump the array and swap its last two elements.
{      e# Do:
  N    e#   Push a linefeed.
  5$   e#   Copy the sixth topmost element from the stack.
  "=(" e#   Push that string.
  3$:G e#   Copy the fourth topmost element from the stack. Save it in G.
  '*   e#   Push that character.
  3$   e#   Copy the fourth topmost element from the stack.
  Gmd  e#   Push quotient and remainder of its division by G.
  ")+" e#   Push that string.
  \    e#   Swap the string with the remainder.
}h     e#   If the remainder is positive, repeat the loop.
]7>    e# Wrap the stack in an array and discard its first seven elements.
NG     e# Push a linefeed and G.

Python 2, 70

f=lambda a,b:b and'%d=(%d*%d)+%d\n'%(a,b,a/b,a%b)*(a>=b)+f(b,a%b)or`a`

A recursive function that returns a multiline string. The function creates the first line, then appends it to the recursive result with the next pair of numbers in the Euclidean algorithm. Once the second number is zero, we take the string of the other number as the base case, causing it to be printed on its own line at the end.

The formatting is done via string substitution, using integer division to get the multiplicand.

One hiccup is needing to start with the larger number being taken mod the smaller number. Conveniently, if the numbers are in the wrong order, the first step of the Euclidian algorithm flips them. To prevent this step from being displayed, only add the current line if the first number is at least the second (equality is needed for, say f(9,9)).


awk, 78 77

x=$1{for(x<$2?x+=$2-(y=x):y=$2;t=y;x=t)print x"=("y"*"int(x/y)")+",y=x%y}$0=x

Sorting the input by size takes a lot of bytes :/
It comes down to this:

x=$1;
if(x<$2) x+=$2-(y=x); # add $2 subtract $1 and set y to $1
else y=$2;            # set y to $2

Output

650 1599            (input)
1599=(650*2)+ 299
650=(299*2)+ 52
299=(52*5)+ 39
52=(39*1)+ 13
39=(13*3)+ 0
13

Just for the fun of it I made a properly spaced version too, giving me a score of 233 * 0.9 == 209.7 bytes.

Update I was able to shorten this from 285 bytes and now it works for arbitrarily long numbers if calling gawk4 with the -M option.

x=$1{x<$2?x+=$2-(y=x):y=$2;a=length(x);b=length(y);for(d=length(x%y);t=y;x=t){$++i=x;$++i=y;if(c<l=length($++i=int(x/y)))c=l;$++i=y=x%y}while(j<NF)printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",$++j,_,$++j,$++j,$++j}$0=x

But I still got a feeling I ran into some mental block there somewhere...

Output (gawk4 called with awk -M -f code.awk)

6837125332653632513763 18237983363879361  (input)
6837125332653632513763 = (18237983363879361 * 374883) + 15415252446024000
     18237983363879361 = (15415252446024000 *      1) +  2822730917855361
     15415252446024000 =  (2822730917855361 *      5) +  1301597856747195
      2822730917855361 =  (1301597856747195 *      2) +   219535204360971
      1301597856747195 =   (219535204360971 *      5) +   203921834942340
       219535204360971 =   (203921834942340 *      1) +    15613369418631
       203921834942340 =    (15613369418631 *     13) +      948032500137
        15613369418631 =      (948032500137 *     16) +      444849416439
          948032500137 =      (444849416439 *      2) +       58333667259
          444849416439 =       (58333667259 *      7) +       36513745626
           58333667259 =       (36513745626 *      1) +       21819921633
           36513745626 =       (21819921633 *      1) +       14693823993
           21819921633 =       (14693823993 *      1) +        7126097640
           14693823993 =        (7126097640 *      2) +         441628713
            7126097640 =         (441628713 *     16) +          60038232
             441628713 =          (60038232 *      7) +          21361089
              60038232 =          (21361089 *      2) +          17316054
              21361089 =          (17316054 *      1) +           4045035
              17316054 =           (4045035 *      4) +           1135914
               4045035 =           (1135914 *      3) +            637293
               1135914 =            (637293 *      1) +            498621
                637293 =            (498621 *      1) +            138672
                498621 =            (138672 *      3) +             82605
                138672 =             (82605 *      1) +             56067
                 82605 =             (56067 *      1) +             26538
                 56067 =             (26538 *      2) +              2991
                 26538 =              (2991 *      8) +              2610
                  2991 =              (2610 *      1) +               381
                  2610 =               (381 *      6) +               324
                   381 =               (324 *      1) +                57
                   324 =                (57 *      5) +                39
                    57 =                (39 *      1) +                18
                    39 =                (18 *      2) +                 3
                    18 =                 (3 *      6) +                 0
3

Some newlines and tabs added

x=$1{
    x<$2?x+=$2-(y=x):y=$2;
    a=length(x);
    b=length(y);
    for(d=length(x%y);t=y;x=t)
    {
        $++i=x;
        $++i=y;
        if(c<l=length($++i=int(x/y)))c=l;
        $++i=y=x%y
    }
    while(j<NF)
        printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",
                                               $++j,_,$++j,$++j,$++j
}$0=x

I can save the lengths of the initial values for x, y and x%y in the beginning, because they can only get shorter each step. But for the factor I have to determine the maximum length before printing anything, because it's length can vary. I use $i as an array here, because it saves two characters compared to using a[i] every time.

Tags:

Math

Code Golf