(* ----------------------------------------------------------------------------
 * $Id: SACDPOL.mi,v 1.3 1992/10/15 16:28:39 kredel Exp $
 * ----------------------------------------------------------------------------
 * This file is part of MAS.
 * ----------------------------------------------------------------------------
 * Copyright (c) 1989 - 1992 Universitaet Passau
 * ----------------------------------------------------------------------------
 * $Log: SACDPOL.mi,v $
 * Revision 1.3  1992/10/15  16:28:39  kredel
 * Changed rcsid variable
 *
 * Revision 1.2  1992/02/12  17:33:57  pesch
 * Moved CONST definition to the right place
 *
 * Revision 1.1  1992/01/22  15:14:11  kredel
 * Initial revision
 *
 * ----------------------------------------------------------------------------
 *)

IMPLEMENTATION MODULE SACDPOL;

(* SAC Dense Polynomial Implementation Module. *)



(* Import lists and declarations. *)

FROM MASSTOR IMPORT LIST, SIL, BETA, SRED, SFIRST, 
                    FIRST, RED, COMP, INV, ADV, LIST1;

FROM SACLIST IMPORT LIST2, COMP2, ADV2, FIRST2, 
                    CLOUT, CINV, RED2, SECOND, EQUAL;

FROM SACM    IMPORT MDDIF, MDINV, MDSUM, MDPROD;

FROM SACPOL  IMPORT PDEG;

CONST rcsidi = "$Id: SACDPOL.mi,v 1.3 1992/10/15 16:28:39 kredel Exp $";
CONST copyrighti = "Copyright (c) 1989 - 1992 Universitaet Passau";

 

PROCEDURE DMPPRD(RL,ML,A,B: LIST): LIST;
(*Dense modular polynomial product.  A and B are polynomials in r
variables over Z sub m, m a beta-integer, r ge 0.  C=A*B.*)
VAR  AL, AP, AS, BL, BP, BS, C, C1, CL, EL, FL, IL, JL, NL, RLP:
     LIST;
BEGIN
(*1*) (*a or b zero.*)
      IF (A = 0) OR (B = 0) THEN C:=0; RETURN(C); END;
(*2*) (*rl=0.*)
      IF RL = 0 THEN C:=MDPROD(ML,A,B); RETURN(C); END;
(*3*) (*general case.*) ADV(A, EL,AP); ADV(B, FL,BP); AS:=CINV(AP);
      BS:=CINV(BP); C:=0; RLP:=RL-1;
      FOR IL:=0 TO FL DO C1:=BETA;
          FOR JL:=1 TO IL DO C1:=COMP(0,C1); END;
          AP:=AS; ADV(BS, BL,BS);
          FOR JL:=0 TO EL DO ADV(AP, AL,AP);
              IF RLP = 0 THEN CL:=MDPROD(ML,AL,BL); ELSE
                 CL:=DMPPRD(RLP,ML,AL,BL); END;
              C1:=COMP(CL,C1); END;
          NL:=EL+IL;
          WHILE (C1 <> SIL) AND (FIRST(C1) = 0) DO NL:=NL-1;
                C1:=RED(C1); END;
          IF C1 <> SIL THEN C1:=COMP(NL,C1); C:=DMPSUM(RL,ML,C1,C);
             END;
          END;
      RETURN(C);
(*6*) END DMPPRD;


PROCEDURE DMPSUM(RL,ML,A,B: LIST): LIST;
(*Dense modular polynomial sum.  A and B are dense polynomials in r
variables over Z sub m, m a beta-integer.  C=A+B.*)
VAR  AL, AP, BL, BP, C, CL, EL, FL, IL, RLP: LIST;
BEGIN
(*1*) (*a or b zero.*)
      IF A = 0 THEN C:=B; RETURN(C); END;
      IF B = 0 THEN C:=A; RETURN(C); END;
(*2*) (*general case.*) RLP:=RL-1;
      IF FIRST(A) >= FIRST(B) THEN ADV(A, EL,AP); ADV(B, FL,BP); ELSE
         ADV(B, EL,AP); ADV(A, FL,BP); END;
      C:=BETA;
      FOR IL:=1 TO EL-FL DO ADV(AP, AL,AP); C:=COMP(AL,C); END;
      REPEAT ADV(AP, AL,AP); ADV(BP, BL,BP);
             IF RLP = 0 THEN CL:=MDSUM(ML,AL,BL); ELSE
                CL:=DMPSUM(RLP,ML,AL,BL); END;
             C:=COMP(CL,C);
             UNTIL AP = SIL;
(*3*) (*finish.*) C:=INV(C);
      WHILE (C <> SIL) AND (FIRST(C) = 0) DO C:=RED(C); EL:=EL-1;
      END;
      IF C = SIL THEN C:=0; ELSE C:=COMP(EL,C); END;
      RETURN(C);
(*6*) END DMPSUM;


PROCEDURE DMUPNR(PL,A,B: LIST): LIST;
(*Dense modular univariate polynomial natural remainder.  A and B are
non-zero dense univariate polynomials over Z sub p, p a prime
beta-integer, with deg(A) ge deg(B).  C is the natural remainder of B.
The list for A is modified.*)
VAR  AL, AP, APP, AS, BL, BLP, BP, BPP, BS, C, CL, KL, ML, NL:
     LIST;
BEGIN
(*1*) (*deg(b)=0.*) NL:=FIRST(B);
      IF NL = 0 THEN C:=0; RETURN(C); END;
(*2*) (*deg(b) positive.*) BP:=RED(B); ADV(BP, BL,BS);
      BLP:=MDINV(PL,BL); AS:=A;
      REPEAT ADV(AS, KL,AP); ML:=-1; ADV(AP, AL,APP);
             CL:=MDPROD(PL,AL,BLP); BPP:=BS;
             REPEAT ADV(BPP, BL,BPP); BL:=MDPROD(PL,BL,CL);
                    AL:=FIRST(APP); AL:=MDDIF(PL,AL,BL); KL:=KL-1;
                    IF (ML < 0) AND (AL <> 0) THEN ML:=KL; AS:=AP;
                       END;
                    SFIRST(APP,AL); AP:=APP; APP:=RED(AP);
                    UNTIL BPP = SIL;
             WHILE (ML < 0) AND (APP <> SIL) DO KL:=KL-1;
                   IF FIRST(APP) <> 0 THEN ML:=KL; AS:=AP; END;
                   AP:=APP; APP:=RED(AP); END;
             IF ML >= 0 THEN SFIRST(AS,ML); END;
             UNTIL ML < NL;
      IF ML >= 0 THEN C:=AS; ELSE C:=0; END;
      RETURN(C);
(*5*) END DMUPNR;


PROCEDURE DPFP(RL,A: LIST): LIST;
(*Dense polynomial from polynomial.  A is a polynomial in r
variables, r ge 0.  B is the result of converting A to dense
polynomial representation.*)
VAR  AP, B, BL, J1Y, KL, NL, RLP: LIST;
BEGIN
(*1*) IF (A = 0) OR (RL = 0) THEN B:=A; RETURN(B); END;
      NL:=PDEG(A); RLP:=RL-1; B:=BETA; AP:=A;
      FOR KL:=NL TO 0 BY -1 DO
          IF (AP = SIL) OR (FIRST(AP) < KL) THEN BL:=0; ELSE
             AP:=RED(AP); ADV(AP, BL,AP);
             IF RLP > 0 THEN BL:=DPFP(RLP,BL); END;
             END;
          B:=COMP(BL,B); END;
      J1Y:=INV(B); B:=COMP(NL,J1Y); RETURN(B);
(*4*) END DPFP;


END SACDPOL.

(* -EOF- *)