(* SAC Integer definition module. *)

DEFINITION MODULE SACI;


FROM MASSTOR IMPORT LIST;

    
PROCEDURE AADV(L: LIST; VAR AL,LP: LIST);
(*Arithmetic advance.  L is a list.  If L ne () then a=FIRST(L) and
LP=RED(L).  Otherwise a=0 and LP=().*)


PROCEDURE IABSF(A: LIST): LIST;
(*Integer absolute value function.  A is an integer.  B=ABS(A).*)


PROCEDURE ICOMP(A,B: LIST): LIST;
(*Integer comparison.  A and B are integers.  s=SIGN(A-B).*)


PROCEDURE IDEGCD(AL,BL: LIST; VAR CL,UL1,VL1,UL2,VL2: LIST);
(*Integer doubly extended greatest common divisor algorithm.  a and b
are integers.  c=GCD(a,b).  a*u1+b*v1=c and a*u2+b*v2=0.
If a ne 0 and b ne 0 then ABS(u1) le ABS(b)/(2*c), ABS(v1) le
ABS(a)/(2*c), u2=-b/c and v2=a/c.  Otherwise u1=v2=SIGN(a),
v1=SIGN(b) and u2=-SIGN(b).*)


PROCEDURE IDIF(A,B: LIST): LIST;
(*Integer difference.  A and B are integers.  C=A-B.*)


PROCEDURE IDIPR2(A,B,AL,BL: LIST): LIST;
(*Integer digit inner product, length 2.  A and B are integers.
a and b are beta-integers.  C=A*a+B*b.*)


PROCEDURE IDPR(A,BL: LIST): LIST;
(*Integer-digit product.  A is an integer.  b is a beta-digit.
C=A*b.*)


PROCEDURE IDP2(A,KL: LIST): LIST;
(*Integer division by power of 2.  A is an integer.  k is a
non-negative beta-digit.  B is the integral part of A/2**k.*)


PROCEDURE IDQ(A,BL: LIST): LIST;
(*Integer-digit quotient.  A is an integer.  b is a non-zero
beta-digit.  C=INTEGER(A/b).*)


PROCEDURE IDQR(A,BL: LIST; VAR Q,RL: LIST);
(*Integer-digit quotient and remainder.  A is an integer.  b is a
non-zero beta-digit.  Q is the integral part of A/b and r=A-b*Q.*)


PROCEDURE IDREM(A,BL: LIST): LIST;
(*Integer-digit remainder.  A is an integer.  b is a non-zero
beta-digit.  r=A-b*INTEGER(A/b).*)


PROCEDURE IEGCD(AL,BL: LIST; VAR CL,UL1,VL1: LIST);
(*Integer extended greatest common divisor algorithm.  a and b are
integers.  c=GCD(a,b).  a*u1+b*v1=c.  If a ne 0 and b ne 0
then ABS(u1) le ABS(b)/(2*c) and ABS(v1) le ABS(a)/(2*c).
Otherwise u1=SIGN(a) and v1=SIGN(b).*)


PROCEDURE IEVEN(A: LIST): BOOLEAN;
(*Integer even.  A is an integer.  If A is even then true is returned 
and otherwise false. *)


PROCEDURE IEXP(A,NL: LIST): LIST;
(*Integer exponentiation.  A is an integer.  n is a non-negative
beta-integer.  B=A**n.*)


PROCEDURE IFCL2(AL: LIST; VAR ML,NL: LIST);
(*Integer, floor and ceiling, logarithm, base 2.  a is a non-zero
integer.  m and n, gamma-integers, are the floor and ceiling of
LOG2(ABS(a)) respectively.*)


PROCEDURE IGCD(A,B: LIST): LIST;
(*Integer greatest common divisor.  A and B are integers.  C=GCD(A,B).*)


PROCEDURE IGCDCF(A,B: LIST; VAR C,AB,BB: LIST);
(*Integer greatest common divisor and cofactors.  A and B are integers.
C eq GCD(A,B).  If C eq 0 then AB eq BB eq 0 and otherwise
AB eq A/C,BB eq B/C.*)


PROCEDURE IHEGCD(A,B: LIST; VAR C,V: LIST);
(*Integer half-extended greatest common divisor.  A and B are integers.
C=GCD(A,B).  If A ne 0, B*V=C(mod A), with ABS(V) le ABS(A)/2C.  If
A=0,V=SIGN(B).*)


PROCEDURE ILCM(A,B: LIST): LIST;
(*Integer least common multiple.  A and B are integers.
C=LCM(A,B), a nonnegative integer.*)


PROCEDURE ILCOMB(A,B,UL,VL: LIST): LIST;
(*Integer linear combination.  A and B are non-negative integers.
u and v are beta-integers such that A*u+B*v ge 0.  C=A*u+B*v.*)


PROCEDURE ILOG2(A: LIST): LIST;
(*Integer logarithm, base 2.  A is an integer.  If A=0 then n=0.
Otherwise n=FLOOR(LOG2(ABS(A)))+1, a beta-integer.*)


PROCEDURE ILWRIT(L: LIST);
(*Integer list write.  L is a list of integers.  The list L is written
in the output stream.*)


PROCEDURE IMAX(AL,BL: LIST): LIST;
(*Integer maximum.  a and b are integers.  c is the maximum of a
and b.*)


PROCEDURE IMIN(AL,BL: LIST): LIST;
(*Integer minimum.  a and b are integers.  c is the minimum of a
and b.*)


PROCEDURE IMP2(A,HL: LIST): LIST;
(*Integer multiplication by power of 2.  A is an integer.  h is a
non-negative beta-integer.  B=A*(2**h).*)


PROCEDURE INEG(A: LIST): LIST;
(*Integer negation.  A is an integer.  B=-A.*)


PROCEDURE IODD(A: LIST): BOOLEAN;
(*Integer odd.  A is an integer.  If a is odd then true is returned
and otherwise false. *)


PROCEDURE IORD2(AL: LIST): LIST;
(*Integer, order of 2.  a is a non-zero integer.  n is the largest
integer such that 2**n divides a.*)


PROCEDURE IPOWER(A,L: LIST; VAR B,NL: LIST);
(*Integer power.  A, greater than or equal to 3, is an odd positive
integer.  L is a list (p(1),p(2), ...,p(k)) of the first k prime
numbers, with p(k) greater than or equal to the base 3 logarithm of A.
If A=B**m for some m greater than or equal to 2 then n is the least
such m and B=A**(1/n).  Otherwise B=0 and n=0.*)


PROCEDURE IPROD(A,B: LIST): LIST;
(*Integer product.  A and B are integers.  C=A*B.*)


PROCEDURE IPRODK(A,B: LIST): LIST;
(*Integer product, Karatsuba algorithm.  A and B are integers.  C=A*B.*)


PROCEDURE IQ(A,B: LIST): LIST;
(*Integer quotient.  A and B are integers, B ne 0.  C is the integral
part of A/B.*)


PROCEDURE IQR(A,B: LIST; VAR Q,R: LIST);
(*Integer quotient and remainder.  A and B are integers, B ne 0.  Q is
the quotient, integral part of A/B, and R is the remainder A-B*Q.*)


PROCEDURE IRAND(NL: LIST): LIST;
(*Integer, random.  n is a positive beta-integer.  A is an integer
with random sign and random absolute value less than 2**n.*)


PROCEDURE IREAD(): LIST;
(*Integer read.  The integer A is read from the input stream.  Any
preceding blanks are skipped.*)


PROCEDURE IREM(A,B: LIST): LIST;
(*Integer remainder.  A and B are integers, B non-zero.  C is the
remainder of A and B.*)


PROCEDURE IROOT(A,NL: LIST; VAR B,TL: LIST);
(*Integer root.  A is a positive integer.  n, greater than or equal
to 2, is a beta-integer.  B=FLOOR(A**(1/n)) and t=SIGN(A-B**n).*)


PROCEDURE ISEG(A,NL: LIST; VAR A1,A0: LIST);
(*Integer segmentation.  A is an integer.  n is a positive beta-
integer.  A1 is the integral part of A/beta**n.  A0=A-A1*beta**n.*)


PROCEDURE ISIGNF(A: LIST): LIST;
(*Integer sign function.  A is an integer.  s=SIGN(A).*)


PROCEDURE ISQRT(A: LIST; VAR B,TL: LIST);
(*Integer square root.  A is a non-negative integer.  B is the floor
function of the square root of A and t is the sign of A-B*B.*)


PROCEDURE ISSUM(NL,L: LIST): LIST;
(*Integer shifted sum.  n is a positive integer.  L is a list
(c(0),c(1), ...,c(k)), k non-negative, of integers c(i) with
ABS(c(i)) less than beta**(2*n+1).  Either each c(i) is
non-negative or each c(i) is non-positive.  C is the sum on i,
from 0 to k, of c(i)*(beta**(i*n)).*)


PROCEDURE ISUM(A,B: LIST): LIST;
(*Integer sum.  A and B are integers.  C=A+B.*)


PROCEDURE ITRUNC(A,NL: LIST): LIST;
(*Integer truncation.  A is an integer.  n is a beta-integer.
B=INTEGER(A/2**n).*)


PROCEDURE IWRITE(A: LIST);
(*Integer write.  The input integer A is converted to decimal and
written in the output stream.*)


END SACI.