! 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
|