C ALGORITHM 386 COLLECTED ALGORITHMS FROM ACM. C ALGORITHM APPEARED IN COMM. ACM, VOL. 13, NO. 07, C P. 447. SUBROUTINE GCDN * (N,A,Z,IGCD) C N NUMBER OF INTEGERS C A(I) INPUT ARRAY OF N INTEGERS, A(I) IS USED AS WORKING STORAGE, C INPUT IS DESTROYED C Z(I) OUTPUT ARRAY OF N MULTIPLIERS C IGCD OUTPUT, GREATEST COMMON DIVISOR OF THE A(I) INTEGERS C DIMENSION A(50),Z(50) INTEGER A,Z,C1,C2,Y1,Y2,Q C FIND FIRST NON-ZERO INTEGER DO 1 M = 1,N IF(A(M) .NE.0) GO TO 3 1 Z(M)=0 C ALL ZERO INPUT RESULTS IN ZERO GCD AND ALL ZERO MULTIPLIERS IGCD=0 RETURN C IF LAST NUMBER IS THE ONLY NON-ZERO NUMBER, EXIT IMMEDIATELY 3 IF(M.NE.N) GO TO 4 IGCD=A(M) Z(M)=1 RETURN 4 MP1= M+1 MP2= M+2 C CHECK THE SIGN OF A(M) ISIGN=0 IF(A(M).GE.0) GO TO 5 ISIGN=1 A(M)=-A(M) C CALCULATE GCD VIA N-1 APPLICATIONS OF THE GCD ALGORITHM FOR TWO C INTEGERS. SAVE THE MULTIPLIERS. 5 C1= A(M) DO 30 I=MP1,N IF(A(I).NE.0) GO TO 7 A(I) = 1 Z(I)= 0 GO TO 25 7 Y1=1 Y2=0 C2=IABS(A(I)) 10 Q= C2/C1 C2= C2-Q*C1 C TESTING BEFORE COMPUTING Y2 AND BEFORE COMPUTING Y1 BELOW SAVES N-1 C ADDITIONS AND N-1 MULTIPLICATIONS. IF(C2.EQ.0) GO TO 20 Y2= Y2-Q*Y1 Q =C1/C2 C1 = C1- Q*C2 IF(C1.EQ.0) GO TO 15 Y1 = Y1 - Q*Y2 GO TO 10 15 C1 = C2 Y1 = Y2 20 Z(I)= (C1 - Y1*A(M))/A(I) A(I)=Y1 A(M)=C1 C TERMINATE GCD CALCULATIONS IF GCD EQUALS ONE. 25 IF(C1.EQ.1) GO TO 60 30 CONTINUE 40 IGCD=A(M) C CALCULATE MULTIPLIERS DO 50 J= MP2,I K = I-J+2 KK=K+1 Z(K)=Z(K)*A(KK) 50 A(K)=A(K)*A(KK) Z(M)=A(MP1) IF(ISIGN.EQ.0) GO TO 100 Z(M)=-Z(M) 100 RETURN C GCD FOUND, SET REMAINDER OF THE MULTIPLIERS EQUAL TO ZERO. 60 IP1= I+1 DO 65 J= IP1,N 65 Z(J) =0 GO TO 40 END