Polynomial long division: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
(Translate Ocaml into F#) |
||
Line 1,415: | Line 1,415: | ||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
|||
{{trans|Ocaml}} |
|||
<lang fsharp> |
|||
let rec shift n l = if n <= 0 then l else shift (n-1) (l @ [0.0]) |
|||
let rec pad n l = if n <= 0 then l else pad (n-1) (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 d = (List.length p) - (List.length q) in |
|||
List.map2 op (pad (-d) p) (pad d q) |
|||
let polydiv f g = |
|||
let rec aux f s q = |
|||
let ddif = (deg f) - (deg s) in |
|||
if ddif < 0 then (q, f) else |
|||
let k = (List.head f) / (List.head s) in |
|||
let ks = List.map ((*) k) (shift ddif s) in |
|||
let q' = zip (+) q (shift ddif [k]) |
|||
let f' = norm (List.tail (zip (-) f ks)) in |
|||
aux f' s q' in |
|||
aux (norm f) (norm g) [] |
|||
let str_poly l = |
|||
let term v p = match (v, p) with |
|||
| ( _, 0) -> string v |
|||
| (1.0, 1) -> "x" |
|||
| ( _, 1) -> (string v) + "*x" |
|||
| (1.0, _) -> "x^" + (string p) |
|||
| _ -> (string v) + "*x^" + (string 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) |
|||
let _ = |
|||
let f,g = [1.0; -4.0; 6.0; 5.0; 3.0], [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" |
|||
(str_poly f) (str_poly g) (str_poly q) (str_poly r) |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
(x^4 + -4*x^3 + 6*x^2 + 5*x + 3) div (x^2 + 2*x + 1) |
|||
gives |
|||
quotient: (x^2 + -6*x + 17) |
|||
remainder: (-23*x + -14) |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
<lang factor>USE: math.polynomials |
<lang factor>USE: math.polynomials |