Aritmetika polynomů

• polynom v jedné proměnné v řídké reprezentaci

• algoritmy pro práci se seznamy

• algoritmus pro sčítání dvou polynomů

        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
  

• například sečtení dvou polynomů 4 x² - 3 x a 5 x + 7 by bylo vykonáno (po jejich převedení do řídké reprezentace) pomocí PLUSPOL[((2 4) (1 -3)),((1 5) (0 7))] => ((2 4) (1 2) (0 7)) což je řídká reprezentace jejich součtu 4 x² + 2 x + 7

• algoritmus pro násobení dvou polynomů a, b ; pokud a=a1+a2, b=b1+b2 potom a b = a1 b1 + a1 b2 + a2 b

        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
  

• například vynásobení dvou polynomů 4 x - 3 a 5 x + 2 by bylo vykonáno (po jejich převedení do řídké reprezentace) pomocí TIMESPOL[((1 4) (0 -3)),((1 5) (0 2))] => ((2 20) (1 -7) (0 -6)) což je řídká reprezentace jejich součinu 20 x² - 7 x - 6