Slide 6.b: Non-recursive greatest common divisor (GCD)

Non-Recursive Greatest Common Divisor (GCD)

A non-recursive GCD algorithm is given on the right side. Java does not have “repeat ... until” command, so the command “do ... while” is used instead.

procedure GCD( int a, int b )
  repeat
    gcd = a mod b
    a = b
    b = gcd
  until a mod b == 0
  return gcd
end procedure

NonRecursiveGCD.java (non-recursive greatest common divisor)

 // Non-recursive Java program to find the GCD 
 class NonRecursiveGCD {
   public static void main( String[ ] args ) {
     // Find GCD between two command-line arguments.
     int a = Integer.parseInt( args[0] );
     int b = Integer.parseInt( args[1] );
     System.out.print( "GCD of " + a + " and " + b + " is " );
     a = Math.abs( a );
     b = Math.abs( b );

     // Check the special cases.
     if ( ( a == 0 ) && ( b == 0 ) )  System.out.println( 0 );
     else if ( b == 0 )  System.out.println( a );
     else if ( a == 0 )  System.out.println( b );
     else  {
       int gcd = 1;
       do 
         gcd = ;
         a   = b;
         b   = gcd;
       while (  > 0 ) {
       System.out.println( gcd );
     }
   }
 }

shell> java NonRecursiveGCD