1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
(* Programmed by Jedidiah Barber *)
(* Licensed under the Sunset License v1.0 *)
module PolyMap = Map.Make(Z)
type t = Z.t PolyMap.t
let zero =
PolyMap.empty
let one =
PolyMap.singleton Z.zero Z.one
let singleton ~coeff ~expnt =
if coeff = Z.zero then
zero
else
PolyMap.singleton expnt coeff
let ( ~$ ) (a, b) =
singleton ~coeff:a ~expnt:b
let of_int a =
PolyMap.singleton Z.zero (Z.of_int a)
let of_zint a =
PolyMap.singleton Z.zero a
let of_arraylist_helper p (coeff,expnt) =
if coeff = Z.zero then
p
else
if PolyMap.mem expnt p then
PolyMap.add expnt Z.((PolyMap.find expnt p) + coeff) p
else
PolyMap.add expnt coeff p
let to_list a =
List.rev_map (fun (expnt,coeff) -> (coeff,expnt)) (PolyMap.bindings a)
let of_list a =
List.fold_left of_arraylist_helper zero a
let to_array a =
Array.of_list (to_list a)
let of_array a =
Array.fold_left of_arraylist_helper zero a
let degree p =
match (PolyMap.max_binding_opt p) with
None -> Z.zero
| Some (k,v) -> k
let get_coeff ~expnt p =
match (PolyMap.find_opt expnt p) with
None -> Z.zero
| Some v -> v
let stringifier (coeff, expnt) =
let sign_str = if coeff < Z.zero then "-" else "+" in
let coeff_str =
if Z.abs coeff = Z.one && expnt <> Z.zero then ""
else Z.to_string (Z.abs coeff) in
let expnt_str =
if expnt = Z.zero then ""
else if expnt = Z.one then "x"
else "x^" ^ (Z.to_string expnt) in
(sign_str, coeff_str ^ expnt_str)
let to_string a =
let pieces = List.map stringifier (to_list a) in
if List.length pieces = 0 then "0"
else
let first_term_sign = if fst (List.hd pieces) = "-" then "-" else "" in
let first_term = first_term_sign ^ (snd (List.hd pieces)) in
let term_concat s (x,y) = s ^ " " ^ x ^ " " ^ y in
let remaining_terms = List.fold_left term_concat "" (List.tl pieces) in
first_term ^ remaining_terms
let print a =
print_string (to_string a)
let output channel a =
output_string channel (to_string a)
let pp_print format a =
let pieces = List.map stringifier (to_list a) in
let do_first item =
if fst item = "-" then Format.pp_print_string format "-";
Format.pp_print_string format (snd item) in
let do_rest item =
Format.pp_print_string format (" " ^ (fst item));
Format.pp_print_space format ();
Format.pp_print_string format (snd item) in
if List.length pieces = 0 then
Format.pp_print_string format "0"
else
(do_first (List.hd pieces);
List.iter do_rest (List.tl pieces))
let neg =
PolyMap.map Z.neg
let add a b =
let f key x y =
if Z.(x + y) = Z.zero then None
else Some Z.(x + y)
in PolyMap.union f a b
let sub a b =
let f key x y =
match (x, y) with
(None, None) -> None
| (Some v, None) -> Some v
| (None, Some v) -> Some Z.(~- v)
| (Some v1, Some v2) ->
if Z.(v1 - v2) = Z.zero then None else Some Z.(v1 - v2)
in PolyMap.merge f a b
let single_mul expnt coeff p =
let helper expnt2 coeff2 r =
PolyMap.add Z.(expnt + expnt2) Z.(coeff * coeff2) r
in PolyMap.fold helper p zero
let mul a b =
PolyMap.fold (fun k v result -> add result (single_mul k v b)) a zero
let div_rem a b =
let rec helper dividend quotient remainder =
if dividend = zero then
(quotient, remainder)
else
if degree b > degree dividend then
(quotient, add dividend remainder)
else
let (dsor_expnt, dsor_coeff) = PolyMap.max_binding b in
let (dend_expnt, dend_coeff) = PolyMap.max_binding dividend in
let (coeff_div, coeff_rem) = Z.div_rem dend_coeff dsor_coeff in
let expnt_diff = Z.(dend_expnt - dsor_expnt) in
let divisor_adjusted = single_mul expnt_diff coeff_div b in
let dividend_adjusted = sub dividend divisor_adjusted in
let new_dividend = PolyMap.remove dend_expnt dividend_adjusted in
let new_quotient =
if coeff_div <> Z.zero then
PolyMap.add expnt_diff coeff_div quotient
else
quotient in
let new_remainder =
if coeff_rem <> Z.zero then
PolyMap.add dend_expnt coeff_rem remainder
else
remainder in
helper new_dividend new_quotient new_remainder in
if b = zero then
raise Division_by_zero
else
helper a zero zero
let div a b =
fst (div_rem a b)
let rem a b =
snd (div_rem a b)
let ( + ) = add
let ( - ) = sub
let ( * ) = mul
let ( / ) = div
|
