Euclid's gcd

post your favourite implementation ``in symta''

"Hello World!"


function gcd(numbers) {
    function baseGCD(x, y) {
        var a = Math.min(x, y), b = Math.max(x, y), r;
        return (r = b % a) ? r : a;
    }
    return (numbers.length === 2)
      ? baseGCD(numbers[0], numbers[1])
      : gcd( [gcd(numbers.slice(0, -1))].concat(numbers[numbers.length-1]) );
}

dont remember euclid needing your ``concise notation''..

>>4
indeed, i prefer this implementation:

To find the greatest common measure of two given numbers not relatively prime.
Let AB and CD be the two given numbers not relatively prime.

It is required to find the greatest common measure of AB and CD.
    If now CD measures AB, since it also measures itself, then CD is a common measure of CD and AB. And it is clear that it is also the greatest, for no greater number than CD measures CD.

But, if CD does not measure AB, then, when the less of the numbers AB and CD being continually subtracted from the greater, some number is left which measures the one before it.
For a unit is not left, otherwise AB and CD would be relatively prime, which is contrary to the hypothesis.

Therefore some number is left which measures the one before it.
Now let CD, measuring BE, leave EA less than itself, let EA, measuring DF, leave FC less than itself, and let CF measure AE.

Since then, CF measures AE, and AE measures DF, therefore CF also measures DF. But it measures itself, therefore it also measures the whole CD.

But CD measures BE, therefore CF also measures BE. And it also measures EA, therefore it measures the whole BA.

But it also measures CD, therefore CF measures AB and CD. Therefore CF is a common measure of AB and CD.
I say next that it is also the greatest.

If CF is not the greatest common measure of AB and CD, then some number G, which is greater than CF, measures the numbers AB and CD.

Now, since G measures CD, and CD measures BE, therefore G also measures BE. But it also measures the whole BA, therefore it measures the remainder AE.

But AE measures DF, therefore G also measures DF. And it measures the whole DC, therefore it also measures the remainder CF, that is, the greater measures the less, which is impossible.

Therefore no number which is greater than CF measures the numbers AB and CD. Therefore CF is the greatest common measure of AB and CD.

>>3
OPTIMIZED

function gcd(numbers) {
    return numbers.reduce(function(x, y) {
        var a = Math.min(x, y), b = Math.max(x, y), r;
        return (r = b % a) ? r : a;
    });
}

Symta sucks

This account is temporarily suspended to cool down. The suspension period ends on Feb 1 '14 at 6:32.

>>7
The suspend reasons are intentionally vague

>>3,6
HIBT? Neither of these work.

>>9
see >>5

In Perl6 this is very hard



say [gcd] 12,144,48;   #Prints 12
say [gcd] 54,24;       #Prints 6

How the fuck do I do that when there is no fucking documentation.

function gcd(a) {
    return a.reduce(function (a, b) {
        if (!a) return b;
        for (; b;) a > b ? a -= b : b -= a;
        return a
    })
}
94 bytes, not counting whitespace. Not bad.

>>13
I should probably have called the outer parameter something descriptive like 'array' instead of a though. My bad