1

I found the function here. It accepts an array of integers and returns their greatest common divisor. Sometimes it gets into an endless loop and crashes the browser. I want to debug it to find the cause, but I don't understand the syntax used in fors. How could these be re-written to ordinary for(var i; i<max; i++) loops?

mdc = function(o){
    if(!o.length)
        return 0;
    for(var r, a, i = o.length - 1, b = o[i]; i;)
        for(a = o[--i]; r = a % b; a = b, b = r);
    return b;
}; 
3
  • How cryptic .. code gone "too clever". Just separate it out: for(init;condition;post) ..
    – user166390
    Aug 24, 2012 at 2:24
  • @pst, I would, but the problem is the borders between init, 'condition, and post are not clear and I cannot make correct associations. Aug 24, 2012 at 2:27
  • The boundaries are the semicolons. The commas can be broken out as multi-statement versions of init, condition, and post. Note that the post for the outer loop is empty.
    – Ted Hopp
    Aug 24, 2012 at 2:33

5 Answers 5

2

Here is a literal translation, from for loops to while loops:

mdc = function(o){
    if(!o.length)
        return 0;
    var r;
    var a;
    var i = o.length - 1;
    var b = o[i];
    while (i) {
        a = o[--i];            
        while (r = a % b) {
            a = b;
            b = r;
        }
    }        
    return b;
}; 

Here is a translation that unpacks some of the silliness and renames the variables:

mdc = function(o){
    if(!o.length)
        return 0;
    var cur_index = o.length - 1;
    var b = o[cur_index];
    while (cur_index) {
        cur_index -= 1;
        var a = o[cur_index];              

        var remainder = a % b;         
        while (remainder) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
    }        
    return b;
}; 
1

I'll give it a try

var r, a, i = o.length - 1
var b = o[i];

while(i) {
  a = o[--i];
  while(r = a % b) {
   a = b;
   b = r;
 }
 return b;
}
1

This for does the same thing that you are used to see, but only with more steps in each part of it. The are three parts:

part 1: it initializes the variables;

part 2: it verifies if the for should continue to iterate

part 3: it increases or decreases the variables;

If you look at it, you're going to see some commas; it is used to declare more than only one variable or condition. The code bellow is the same as the code that you posted, but in a way that looks familiar to you:

mdc = function(o){
if(!o.length)
    return 0;
    var r;
    var a;
    var i = o.length - 1;
    for(var b = o[i]; i;) {
        for(a = o[--i]; r = a % b;b = r) {
           a = b;
        }
        return b;
    }
}; 

You can notice the second for ends with a ";", which is equivalent to a command line, that why there is only the "a = b" command in it, instead of "return b";

1

Well the basic formula of a for loop is

for(initial code; condition to check for; code to execute after loop)
{
    loop
}

I don't like the syntax in that code. Just declare all your variables at the top. Since your best interest is to debug the code, it's probably best to have one statement per line.

mdc = function(o)
{
    if(!o.length)
        return 0;
    var r, a, b, i;
    i = o.length - 1;
    b = o[i];
    while(i)
    {
        a = o[i];
        i--;
        while(r = a % b)
        {
            a = b;
            b = r;
        }
    }
    return b;
};
1

``I think the problem is that (a,b) need to be interchanged depending on which is greater. (The second for loop). The Euclidean algorithm does that. This one does not seem to be doing that.

GCD of an array of numbers: I would use the standard Euclidean algorithm.

If you are iterating from the end : GCD (a,b) =K
Now call GCD(K,next_element_in_array) . That should work.

enter code here
  Written in Pseudo-code What he is trying to do is more understandable:  
   For(b =array[end];   )    
     { 
      For(a= array[end-1]; end >=0 ;end --)  
          {
          (i)Divide a/b
          (ii)Put the new 'reduced' divisor in 'b'.
         (iii)Put the reminder back in c 
          }     
         end --
      } 

           }
       }

So, at the end of the loop, anything What he is trying to simulate is the hand-division computation of gcd of series of numbers - the high-school trick!

The problem, as I mentioned above,is in swapping (a,b) which is greater.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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