The Euclidean Algorithm (for finding the greatest common divisor)

Question

The Challenge

Write a program or function that takes two input integers, i and j, and outputs their greatest common divisor; calculated by using the Euclidean algorithm (see below).

Input

Input may be taken as a space-delimited string representation of i and j or as two separate integers. You can assume that integers will be less than or equal to 10,000. You can also assume that the input integers will not be prime to one another.

Euclidean Breakdown

The larger number between i and j is divided by the smaller as many times as possible. Then, the remainder is added. This process is repeated with the remainder and the previous number, until the remainder becomes 0.

For example, if the input was 1599 650:

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

The final number, 13, is the greatest common divisor of the two input integers. It can be visualized like this:

Output

Your output must be the breakdown in the form above, followed by a newline and the GCD. It can be output through any medium.

Examples

Inputs

Outputs

27 = (18 * 1) + 9
18 =  (9 * 2) + 0
9

50 = (20 * 2) + 10
20 = (10 * 2) +  0
10

501 = (447 * 1) + 54
447 =  (54 * 8) + 15
 54 =  (15 * 3) +  9
 15 =   (9 * 1) +  6
  9 =   (6 * 1) +  3
  6 =   (3 * 2) +  0
3

9894 = (2628 *  3) + 2010
2628 = (2010 *  1) +  618
2010 =  (618 *  3) +  156
 618 =  (156 *  3) +  150
 156 =  (150 *  1) +    6
 150 =    (6 * 25) +    0
6

Note: Outputs do not have to be spaced as they are above. The spacing is only for clarity. Parentheses are required.

Bonus

If your output is spaced as above, you may add a -10% bonus to your score.

1. Can we assume the largest number is given first? 2. For the bonus, you mean the field width should be constant and just enough to allow for one space before the largest number? (with the spaces coming before the left parenthesis in the second column of numbers.) You should avoid ambiguous phrasing such as "as they are above" when the output is variable. It's OK if the required output is fixed. — steveverrill, yesterday
Your original title was OK, I've commented on what happened at meta.codegolf.stackexchange.com/q/7043/15599 . The phrase "greatest common denominator" was wrong however. "Denominator" relates to fractions. Googling "greatest common denominator" only gives results for "greatest common divisor / factor." — steveverrill, yesterday
I thought the title was OK, but I changed it to "The" as to not displease anyone. Thanks for editing in "divisor", BTW. @steveverrill — Zach Gates, yesterday

Dennis · Answer 1 · 2015-09-25 05:06:24Z

up vote 5 down vote

CJam, 46 43 39 bytes

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

Try it online in the CJam interpreter.

edited 18 hours ago

answered yesterday

Dennis♦
40.1k664185

add a comment |

xnor · Answer 2 · 2015-09-24 08:25:47Z

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

Cabbie407 · Answer 3 · 2015-09-25 14:36:09Z

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.

Jakube · Answer 4 · 2015-09-24 09:15:02Z

Pyth, 33 bytes

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H

Try it online: Demonstration or Test Suite

Explanation:

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H
  Q                                read the two numbers from input
 S                                 sort them
A                                  and assign them to G and H
   WG                              while G != 0:
                      K%HG           assign H mod G to K
     s[H\=\(G\*/HG\)\+K   )          join the following list items and print:
                                        H=(G*(H/G))+K
                           A,KG      assign K, G to G, H
                               )   end while
                                H  print H

steveverrill · Answer 5 · 2015-09-24 12:55:37Z

up vote 2 down vote

Rev 1: Ruby, 86

Recursive algorithm, thanks to tip from Doorknob.

f=->i,j{j>i&&(i,j=j,i)
0<j ?(print i," = (#{j} * #{i/j}) + #{i%j}
";f[j,i%j]):puts(i)}

Rev 0: Ruby, 93

This really hasn't worked out well at all. The while loop takes up too many characters, especially with the end. I can't see a way of avoiding it. Recursion would require a named function instead of a lambda, which would also eat up a lot of characters.

->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}

Call it like this:

f=->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}

I=gets.to_i
J=gets.to_i

f.call(I,J)

edited yesterday

answered yesterday

steveverrill
9,86221347

You can use recursion via a=->i,j{...} and call a via a[1,2]—not sure if this would save you characters, though. – Doorknob♦ yesterday

@Doorknob thanks for the tip, I wasn't aware of that syntax for calling lambda functions (see my use of f.call.) It is actually quite a bit shorter, but still a long way off Python. – steveverrill yesterday

add a comment |

TessellatingHeckler · Answer 6 · 2015-09-25 04:43:16Z

PowerShell, 84

A recursive code block, stored in a variable. Invoke it with & $e num1 num2, e.g.:

$e={$s,$b=$args|Sort;if(!$s){$b}else{$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";&$e $s $r}}

PS D:\> & $e 9894 2628
9894=(2628*3)+2010
2628=(2010*1)+618
2010=(618*3)+156
618=(156*3)+150
156=(150*1)+6
150=(6*25)+0
6

In a more readable form, it does the following (nb. for clearer code, I've put the full commandlet names, more spaces in the string, and made the pipeline output commands explicit):

function Euclid {
    $small, $big = $args|Sort-Object   #Sort argument list, assign to two vars.

    if (!$small) {                     #Recursion end, emit the last
        Write-Output $big              #number alone, for the last line.

    } else {                           #main recursive code

        $remainder = $big % $small
        Write-Output "$big = ( $small* $(($big-$remainder)/$small)) + $remainder"
        Euclid $small $remainder
    }
}

One annoyance from a codegolf point of view; PoSh has no integer division, 10/3 returns a Double, but cast the result to an integer and it doesn't always round down, it rounds N.5 to the nearest even number - up or down. So [int](99/2) == 50.

That leaves two awkward choices:

$remainder = $x % $y
$quotient = [Math]::Floor($x/$y)

# or, worse

$remainder=$null
$quotient = [Math]::DivRem($x, $y, [ref]$remainder)

Which is why I have to burn some characters doing:

$remainder = $big % $small
($big - $remainder)/$small

Apart from that, it's the number of $$$$ and the lack of ternary operator which really hurts.

I also have an iterative version which, rather nicely, is also 84 characters:

{$r=1;while($r){$s,$b=$args|Sort;$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";$args=$s,$r}$s}

Completely anonymous codeblock, so run it with

& {*codeblock*} 1599 650

asked	yesterday
viewed	710 times
active	today

current community

your communities

more stack exchange communities

The Euclidean Algorithm (for finding the greatest common divisor)

The Challenge

Input

Euclidean Breakdown

Output

Examples

Inputs

Outputs

Bonus

6 Answers 6

CJam, 46 43 39 bytes

Python 2, 70

awk, 78 77

Output

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

Some newlines and tabs added

Pyth, 33 bytes

Explanation:

Rev 1: Ruby, 86

Rev 0: Ruby, 93

PowerShell, 84

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

The Euclidean Algorithm (for finding the greatest common divisor)

The Challenge

Input

Euclidean Breakdown

Output

Examples

Inputs

Outputs

Bonus

6 Answers 6

CJam, 46 43 39 bytes

Python 2, 70

awk, 78 77

Output

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

Some newlines and tabs added

Pyth, 33 bytes

Explanation:

Rev 1: Ruby, 86

Rev 0: Ruby, 93

PowerShell, 84

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Related

Hot Network Questions

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