Polynomial long division: Difference between revisions
Content added Content deleted
m (Make the demonstration example in the header easier to read) |
(OCaml example) |
||
Line 331: | Line 331: | ||
end program PolyDivTest</lang> |
end program PolyDivTest</lang> |
||
=={{header|OCaml}}== |
|||
First define some utility operations on polynomials as lists (with highest power coefficient first). |
|||
<lang ocaml> |
|||
let rec shift n l = if n <= 0 then l else shift (pred n) (l @ [0.0]) |
|||
let rec pad n l = if n <= 0 then l else pad (pred n) (0.0 :: l) |
|||
let rec scale k l = List.map (( *.) k) l |
|||
let rec norm = function | 0.0 :: tl -> norm tl | x -> x |
|||
let deg l = List.length (norm l) - 1 |
|||
let zip op p q = |
|||
let gap = (deg p) - (deg q) in |
|||
if gap = 0 then List.map2 op p q else |
|||
if gap > 0 then List.map2 op p (pad gap q) |
|||
else List.map2 op (pad (-gap) p) q |
|||
let sub = zip (-.) |
|||
let add = zip (+.) |
|||
</lang> |
|||
Then the main polynomial division function |
|||
<lang ocaml> |
|||
let polydiv f g = |
|||
let rec aux f s q = |
|||
let gap = (deg f) - (deg s) in |
|||
if gap < 0 then (q, f) else |
|||
let k = (List.hd f) /. (List.hd s) in |
|||
let q' = add q (scale k (shift gap [1.0])) in |
|||
let f' = norm (List.tl (sub f (scale k (shift gap s)))) in |
|||
aux f' s q' in |
|||
aux (norm f) (norm g) [] |
|||
</lang> |
|||
For output we need a pretty-printing function |
|||
<lang ocaml> |
|||
let str_poly l = |
|||
let term v p = match (v, p) with |
|||
| ( _, 0) -> string_of_float v |
|||
| (1.0, 1) -> "x" |
|||
| ( _, 1) -> (string_of_float v) ^ "*x" |
|||
| (1.0, _) -> "x^" ^ (string_of_int p) |
|||
| _ -> (string_of_float v) ^ "*x^" ^ (string_of_int p) in |
|||
let rec terms = function |
|||
| [] -> [] |
|||
| h :: t -> |
|||
if h = 0.0 then (terms t) else (term h (List.length t)) :: (terms t) in |
|||
String.concat " + " (terms l) |
|||
</lang> |
|||
and the test driver |
|||
<lang ocaml> |
|||
let _ = |
|||
let f = [1.0; -4.0; 6.0; 5.0; 3.0] and g = [1.0; 2.0; 1.0] in |
|||
let q, r = polydiv f g in |
|||
begin |
|||
Printf.printf "f = %s\ng = %s\n\n" (str_poly f) (str_poly g); |
|||
Printf.printf "q = %s\nr = %s\n" (str_poly q) (str_poly r) |
|||
end |
|||
</lang> |
|||
which gives the output: |
|||
<pre> |
|||
f = x^4 + -4.*x^3 + 6.*x^2 + 5.*x + 3. |
|||
g = x^2 + 2.*x + 1. |
|||
q = x^2 + -6.*x + 17. |
|||
r = -23.*x + -14. |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{works with|Python 2.x}} |
{{works with|Python 2.x}} |