Polynomial synthetic division: Difference between revisions
Content added Content deleted
m (→{{header|Python}}: ahora funciona en Python 2.7 y 3.x) |
(→{{header|Haskell}}: added solution) |
||
Line 346:
[1/1 -12/1 0/1 -42/1] / [1/1 -3/1] = [1/1 -9/1 -27/1] remainder [-123/1]
</pre>
=={{header|Haskell}}==
<lang haskell>import Control.Monad
normalized :: (Eq a, Num a) => [a] -> [a]
normalized = dropWhile (== 0)
isZero :: (Eq a, Num a) => [a] -> Bool
isZero = null . normalized
shortDiv :: (Eq a, Fractional a) => [a] -> [a] -> ([a], [a])
shortDiv p1 p2
| isZero p2 = error "zero divisor"
| otherwise = foldM step p1 [1 .. length p1 - length as]
where
a:as = normalized p2
step (h:t) = return ([h/a], zipWith (+) (map ((h/a) *) ker) t)
ker = negate <$> (as ++ repeat 0)</lang>
<pre>*Main> shortDiv [1,-12,0,-42] [1,1,-3]
([1.0,-13.0],[16.0,-81.0])
*Main> shortDiv [6,5,0,-7] [3,-2,-1]
([2.0,3.0],[8.0,-4.0])</pre>
For monic divisors it is possible to perform purely integral computations (without Fractional constraint):
<lang haskell>isMonic :: (Eq a, Num a) => [a] -> Bool
isMonic = ([1] ==) . take 1 . normalized
shortDivMonic :: (Eq a, Num a) => [a] -> [a] -> ([a], [a])
shortDivMonic p1 p2
| isZero p2 = error "zero divisor"
| not (isMonic p2) = error "divisor is not monic"
| otherwise = foldM step p1 [1 .. length p1 - length as]
where
a:as = normalized p2
step (h:t) = return ([h], zipWith (+) (map (h *) ker) t)
ker = negate <$> as ++ repeat 0</lang>
<pre>shortDivMonic [1,-12,0,-42] [1,1,-3 :: Int]
([1,-13],[16,-81])</pre>
=={{header|J}}==
| |||