Can anyone explain me in below algorithm how the "ISZERO" function checking whether the polynomial is zero or not. Here "REM(P,e)" function removes all the values with exponent "e". what i don't able to understand is the significance of "if COEF(P,e) = - c". And also what is this "SMULT" function.
structure POLYNOMIAL
declare ZERO( ) poly; ISZERO(poly) Boolean
COEF(poly,exp) coef;
ATTACH(poly,coef,exp) poly
REM(poly,exp) poly
SMULT(poly,coef,exp) poly
ADD(poly,poly) poly; MULT(poly,poly) poly;
for all P,Q, poly c,d, coef e,f exp let
REM(ZERO,f) :: = ZERO
REM(ATTACH(P,c,e),f) :: =
if e = f then REM(P,f) else ATTACH(REM(P,f),c,e)
***ISZERO(ZERO) :: = true
ISZERO(ATTACH(P,c,e)):: =
if COEF(P,e) = - c then ISZERO(REM(P,e)) else false***
COEF(ZERO,e) :: = 0
COEF(ATTACH(P,c,e),f) :: =
if e = f then c + COEF(P,f) else COEF(P,f)
SMULT(ZERO,d,f) :: = ZERO
SMULT(ATTACH(P,c,e),d,f) :: =
ATTACH(SMULT(P,d,f),c d,e + f)
ADD(P,ZERO):: = P
ADD(P,ATTACH(Q,d,f)) :: = ATTACH(ADD(P,Q),d,f)
MULT(P,ZERO) :: = ZERO
MULT(P,ATTACH(Q,d,f)) :: =
ADD(MULT(P,Q),SMULT(P,d,f))
end
end POLYNOMIAL
Without knowing what language this is, it looks like this line
ISZERO(ATTACH(P,c,e)):: =
if COEF(P,e) = - c then ISZERO(REM(P,e)) else false
is specifying ISZERO
recursively. We are trying to determine whether ATTACH(P, c, e)
, otherwise known as P(x) + cx^e
, is zero. It first checks whether the x^e
coefficient of P
is -c
. If not, then P(x) + cx^e
is definitely not zero, and you can return false immediately. Otherwise, P(x) + cx^e = REM(P, e)
, so you have to check ISZERO(REM(P, e))
.
I believe SMULT
is multiplication, so SMULT(P, a, b)
is equivalent to a * x^b * P(x)
.