Polynome in einer Variablen

• Repräsentation:
  • dicht: Folge (Data.Sequence) der Koeffizienten
  • dünn: endliche Abbildung (Data.Map)

    Schlüssel: Grad, Wert: Koeffizient

    normalisierte Darstellung: nur Koeffizienten ≠ 0 werden repräsentiert (dann einfacher Test auf P = 0)

• Auswertung: mit Horner-Schema
• Addition
  • in dichter Darstellung: Data.List.zipWith (+)
  • in dünner Darstellung: Data.Map.unionWith (+)
• Multiplikation: naiv: quadratisch, mit FFT: n log n