Anonymous user
Polynomial long division: Difference between revisions
OCaml example
m (Make the demonstration example in the header easier to read) |
(OCaml example) |
||
Line 331:
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}}==
{{works with|Python 2.x}}
| |||