Arithmetic of polynomials

 

• polynomial in one variable in sparse representation

• algorithms dealing with lists

• algorithm for the addition of two polynomials

        PLUSPOL(a, b) :=
          if  a = ( )  then return b
            else if  b = ( )  then return a
            else
              ea := first first a
              eb := first first b
              ca := second first a                      %a=((ea ca) ...)
              cb := second first b                      %b=((eb cb) ...)
              return(
                if ea > eb then
                    cons(first a, pluspol(rest a, b))
                  else if ea < eb then
                    cons(first b, pluspol(rest b, a))
                  else if ca + cb = 0 then
                    pluspol(rest a, rest b)
                  else cons(list(ea, ca + cb), pluspol(rest a, rest b))
                fi fi fi)
          fi fi

• for example, adding the two polynomials and would be performed (after converting them into sparse representation) by PLUSPOL[((2 4) (1 -3)),((1 5) (0 7))] => ((2 4) (1 2) (0 7)) which is the sparse representation of the sum

• algorithm for the multiplication of two polynomials ; if and then

        TIMESPOL(a, b) :=
          if  a = ( ) or b = ( )  then return ( )
            else
              ea := first first a
              eb := first first b
              ca := second first a                      %a=((ea ca) ...)
              cb := second first b                      %b=((eb cb) ...)
              return(cons(list(ea + eb, ca * cb),
                          pluspol(timespol(list first a, rest b),
                                  timespol(rest a, b))
                         )
                    )
          fi

• for example, multiplying the two polynomials a would be performed (after converting them into sparse representation) by TIMESPOL[((1 4) (0 -3)),((1 5) (0 2))] => ((2 20) (1 -7) (0 -6)) which is the sparse representation of their product

 
• Lists