I got it, but is my code sloppy?

[Ryan Smith]

What do you guys think of this code to find the lowest common multiple (LCM):

private static int findLCM(int x, int y)
 {
  int lesser = x < y ? x : y;
  int d;
   
   /** Makes <code>x</code> and <code>y</code> 
     * relatively prime.
     */
 
   do 
   {
    for(d = 2; d <= lesser / 2; d++)
    { 
     if (x % d == 0 && y % d == 0)
     {
      x /= d;
      y /= d;
      lesser /= d;
      break;
     }
    }
   }while(d <= lesser / 2);
   
   int lowestcm = x * y;  
 
   int greater = x > y ? x : y;
 
   /** The final possibility is that the lesser number
     * is the final factor of the larger.
     */
 
   if (greater % lesser == 0)  
    lowestcm = greater / lesser;
 
   return lowestcm;
   
 }

[Greg Charles]

Not too bad! You have Javadoc style comments inside the method, which you don't need. They won't show up in the Javadocs anyway. Maybe rename d to something more descriptive? That's being a bit picky. Style-wise everything else looks fine. I think the algorithm is wrong though. You don't mean to divide both x and y by the common factor, do you? That would result in too low of an answer.

[Tim West]

Looks good to me also. If it was my code, I'd use longer variable names (probably...in math-heavy code I don't always ). Also, I'd move the "final possibility" clause to the very start - this is much more efficient, you can avoid the main body algorithm.

Finally, I'd consider using Euclid's Algorithm for finding the LCM. It's very efficient, and not too complex. Dunno if efficiency is a concern though.



--Tim
[ June 30, 2004: Message edited by: Tim West ]

[Greg Charles]

No, I'm wrong. You do need to divide both x and y by the common factor. However, you need to keep track of the common factors. I think this works:

  
private static int findLCM(int x, int y) 
{
int lesser = x < y ? x : y;
int limit = (int)(Math.sqrt(lesser));
int lowestcm = 1;
int factor = 2;

while (factor <= limit)
{
if (x % factor == 0 && y % factor == 0)
{
x = x / factor;
y = y / factor;
lowestcm *= factor;
}
else
{
factor++;
}
}

lowestcm = lowestcm * x * y;
return lowestcm;
        }

It's a good idea to avoid nested loops if you can. Also, the less you use break and continue, the better!

[Mala Gupta]

Hi Greg

> It's a good idea to avoid nested loops
> if you can. Also, the less you use break
> and continue, the better

What are the disadvantages of using nested loops, continue and break.

regards
Mala

[Nick Knickerbocker]

Ryan, Looking good man! Greg had good suggestions about the comment type and variable name. Use inline comments within methods. Use descriptive variable names. For other good tips on Java coding style, I recommend the book Elements of Java Style (Vermeulen et al.).

Mala, as with most style guidelines, Greg's suggestions are based on code clarity and readability. As software developers, one of our primary concerns is how well our code communicates its intention. Nested loops are by nature more difficult to comprehend. Sometimes break and continue are useful, but one should take care to make them obvious in code because they violate the normal flow of looping control structures.

Greg, your version of the LCM algorithm looks great, but upon cursory inspection I would have to delete that second-to-last line. Am I wrong?

 lowestcm = lowestcm * x * y; 

Cheers to all,
Nick

[Jeroen Wenting]

Originally posted by Mala Gupta:
Hi Greg

> It's a good idea to avoid nested loops
> if you can. Also, the less you use break
> and continue, the better

What are the disadvantages of using nested loops, continue and break.

readability. Code with deep nested loops and many breaks and continues can be hard to comprehend and therefore hard to change/maintain.

[Ryan Smith]

Hey guys, thanks for all the great suggestions!! I knew that nested loops looked ugly, but I wasn't sure what was wrong...it just looked funny to me.

So you guys are saying comments in /***/ style only appear if written before a mehtod is declared, right? And inside a method, only use // ?

[Angel Dobbs-Sciortino]

/** */ is generally used for javadoc, so you can use // if you have short comments within the method. You can also use /* */ if the comments are long.

[Greg Charles]

Originally posted by Nick Knickerbocker:
Greg, your version of the LCM algorithm looks great, but upon cursory inspection I would have to delete that second-to-last line. Am I wrong?

 lowestcm = lowestcm * x * y; 

Nick

Yes, you are wrong. The loop only makes x and y relatively prime. That is, it pulls out their common factors and stores them in a running tally. (No, tally's not the right word. Running product?) If x and y started relatively prime, for example 4 and 15, the running product after the loop would be 1, and x and y still the same. Ah, but maybe you were thinking of greatest common factor?

[James Chegwidden]

GCD:

/**
  * Euclid's greatest common divisor algorithm.
  * Find the largest number that evenly divides into both n and d.
  * require: n >= 0, d >= 0.
  * fastest if n >= d.
  */
public static int gcd(int n, int d)
   {
   if ( d == 0 )
      {
      return 1;
      }
   int r = n % d;
   return( r == 0 ) ? d : gcd( d , r );
   }
  

LCM:

(a * b) / gcd(a,b)

This is the way I would do it!!