Lindo Systems

! Using a LINGO Procedure for computing the 
 Greatest Common Divisor of a set of numbers;
! Keywords: GCD, Greatest Common Divisor, 
    Procedures in LINGO, Euclid's algorithm;
SETS:
  FG: SIDEY;
ENDSETS
DATA: 
! Several different data sets from cutting stock problems;
 SIDEY=  715  429 858  572 605 660 594 759 605 363 594 781 968 935 781;
! SIDEY=  600 600 600 770 770 770 770 770 600 770 770 770 770 770 900 900 ;
! SIDEY=  450 450 500 300 300 300 300 600 600 500 450 450 450 450 600 600 600 600 600 600 600 600 ;
! SIDEY =  56 28 63 49 21 42 ;
ENDDATA

PROCEDURE GETGCD:
 ! Inputs:
     GCDPR = previous Greatest Common Divisor,
     GCDNTR = new term to include in GCD calculation,
   Outputs:
     GCDNU = GCD( GCDPR, GCDNTR);
   GCDX = GCDPR;
   ! Make GCDRM the smaller of the two;
   @IFC( GCDX #LT# GCDNTR:
     GCDNU = GCDNTR;
     GCDRM = GCDX;
    @ELSE
     GCDNU = GCDX;
     GCDRM = GCDNTR;
        );
  ! Now use Euclid's algorithm. If GCDNU divides GCDX,
    then the remainder is zero;
   @WHILE( GCDRM #GT# 0:
     GCDX = GCDNU;
     GCDNU = GCDRM;
  ! Get the remainder of GCDX/GCDNU;
     GCDRM = @MOD(GCDX,GCDNU);
      );
ENDPROCEDURE

CALC:
  ! Calc GCD of a set of numbers in SIDEY;
  @SET('TERSEO',2); ! Turn off default output;
  GCDNU = SIDEY(1); ! If only one number, it is the GCD;
  @FOR(FG(j) | j #GT# 1:
     GCDPR = GCDNU;
     GCDNTR = SIDEY(j);
     @WRITE(' Current GCD = ', GCDPR,', not yet including ',GCDNTR, @newline(1));
      GETGCD; ! Find GCDNU =  GCD of GCDPR and GCDNTR;
   );
  @WRITE(' Final GCD = ', GCDNU, @NEWLINE(1)); 
ENDCALC