22 lines
617 B
Haskell
22 lines
617 B
Haskell
import Data.List
|
|
|
|
shift n l = l ++ replicate n 0
|
|
|
|
pad n l = replicate n 0 ++ l
|
|
|
|
norm :: Fractional a => [a] -> [a]
|
|
norm = dropWhile (== 0)
|
|
|
|
deg l = length (norm l) - 1
|
|
|
|
zipWith' op p q = zipWith op (pad (-d) p) (pad d q)
|
|
where d = (length p) - (length q)
|
|
|
|
polydiv f g = aux (norm f) (norm g) []
|
|
where aux f s q | ddif < 0 = (q, f)
|
|
| otherwise = aux f' s q'
|
|
where ddif = (deg f) - (deg s)
|
|
k = (head f) / (head s)
|
|
ks = map (* k) $ shift ddif s
|
|
q' = zipWith' (+) q $ shift ddif [k]
|
|
f' = norm $ tail $ zipWith' (-) f ks
|