Anonymous user
Polynomial long division: Difference between revisions
m
a bit prettier
(polynomial long division in common lisp) |
m (a bit prettier) |
||
Line 514:
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])▼
<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 norm = function | 0.0 :: tl -> norm tl | x -> x
let deg l = List.length (norm l) - 1
let zip op p q =
let
Then the main polynomial division function
<lang ocaml>let polydiv f g =
let rec aux f s q =
let
if
let k = (List.hd f) /. (List.hd s) in
let
let
and f' = norm (List.tl (zip (-.) f ks)) 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
Line 555 ⟶ 545:
| h :: t ->
if h = 0.0 then (terms t) else (term h (List.length t)) :: (terms t) in
String.concat " + " (terms l)</lang>
and then the example
▲<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
Printf.printf
" (%s) div (%s)\ngives\nquotient:\t(%s)\nremainder:\t(%s)\n"
▲which gives the output:
<pre>
gives
</pre>
|