-
Notifications
You must be signed in to change notification settings - Fork 0
/
sht.ml
252 lines (181 loc) · 7.01 KB
/
sht.ml
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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
module type Field = sig
type t
val zero : t (* zero element of the field *)
val one : t (* unit element of the field *)
val compare : t -> t -> int (* comparison *)
val to_string : t -> string (* field element to string *)
val add : t -> t -> t (* addition *)
val mul : t -> t -> t (* multiplication *)
val sub : t -> t -> t (* subtraction *)
val div : t -> t -> t (* division *)
val add_inv : t -> t (* additive inverse *)
val mul_inv : t -> t (* multiplicative inverse *)
end ;;
module type RationalField =
sig
include Field with type t = int * int
type t = int * int (* rationals are represented as pairs of int *)
exception Bad_rational of string
val standard_form : t -> t (* standard from of a rational number *)
val to_float : t -> float (* decimal expansion *)
val from_int : int -> t (* integer to rational conversion *)
end;;
module type GaussianRationalField =
sig
include Field with type t = (int * int) * (int * int)
(* Gaussian rationals are represented as pairs of rationals *)
exception Division_by_zero of string
val from_rational : (int * int ) -> t (* rational to complex *)
val conj : t -> t (* conjugate *)
val re : t -> (int * int) (* real part *)
val im : t -> (int * int) (* inaginary part *)
end
module Rationals : RationalField =
struct
type t = int * int
exception Bad_rational of string
let zero = (0,1)
let one = (1,1)
let standard_form (n,d) =
let rec gcd a b =
if b = 0 then a else gcd b (a mod b)
in
let k = gcd n d
in
(n/k,d/k)
let compare (r1,i1) (r2,i2) =
let (a,b) = standard_form (r1,i1)
in
let (c,d) = standard_form (r2,i2)
in
let l = a * d
in
let r = b * c
in compare l r
let add (a,b) (c,d) =
if (b==0 || d==0) then raise (Bad_rational ("cant divade by zero")) else
standard_form ((a*d + b*c), (b*d))
let mul (a,b) (c,d) =
if (b==0 || d==0) then raise (Bad_rational ("cant divade by zero")) else
standard_form ((a*c),(b*d))
let sub (a,b) (c,d) =
if (b==0 || d==0) then raise (Bad_rational ("cant divade by zero")) else standard_form ((a*d - b*c), (b*d))
let div (a,b) (c,d) =
if b==0 || c == 0 then raise (Bad_rational ("cant divade by zero")) else
standard_form ((a*d),(b*c))
let add_inv (a,b) =
if (b==0 || a ==0 ) then raise (Bad_rational ("cant divade by zero")) else
standard_form(-a,b)
let mul_inv (a,b) =
if a==0 || b == 0 then raise (Bad_rational ("cant divade by zero"))
else
standard_form(b,a)
let from_int a = (a,1) (*wrong*)
let to_float (a,b) =
if b = 0 then raise (Bad_rational ("cant divade by zero")) else
float_of_int a /. float_of_int b
let to_string (a, b) =
let temp =
standard_form (a, b)
in
match temp with | (c, d) ->
if c = 0 then string_of_int(0)
else if d = 1 then string_of_int(c)
else string_of_int c ^ "/" ^ string_of_int (d)
end
module GaussianRationals : GaussianRationalField =
struct
type t = (int * int) * (int * int)
exception Division_by_zero of string
let zero = ((0,1),(0,1))
let one = ((1,1),(1,1))
let add x1 x2 =
let ((a,b),(a1,b1)) = x1
in
let ((c,d),(c1,d1)) = x2
in
if (d ==0 || d1 ==0 || b1 ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
let k1 = Rationals.standard_form ((a*d + b*c), (b*d))
in
let k2 = Rationals.standard_form ((a1*d1 + b1*c1), (b1*d1))
in
(k1,k2)
let sub x1 x2 =
let ((a,b),(a1,b1)) = x1
in
let ((c,d),(c1,d1)) = x2
in
if (d ==0 || d1 ==0 || b1 ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
let k1 = Rationals.standard_form ((a*d - b*c), (b*d))
in
let k2 = Rationals.standard_form ((a1*d1 - b1*c1), (b1*d1))
in
(k1,k2)
let mul ((a,b),(a1,b1)) ((c,d),(c1,d1)) =
if (d ==0 || d1 ==0 || b1 ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
let s = Rationals.mul (a,b) (c,d)
in
let k = Rationals.mul (a1,b1) (c1,d1)
in
let re = Rationals.sub s k
in
let p = Rationals.mul (a,b) (a1,b1)
in
let t = Rationals.mul (a1,b1)(c,d)
in
let im = Rationals.sub p t
in
(re,im)
let div ((a,b),(a1,b1)) ((c,d),(c1,d1)) =
if (d ==0 || d1 ==0 || b1 ==0 || b ==0 || c1 ==0 || c ==0 ) then raise (Division_by_zero("cant devide by zero"))
else
let s = Rationals.standard_form ((a*d),(b*c))
in
let y = Rationals.standard_form ((a1*d1),(b1*c1))
in
(s,y)
let add_inv ((a,b),(c,d)) =
if (d ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
( Rationals.standard_form(-b,a),Rationals.standard_form(-c,d) )
let mul_inv ((a,b),(c,d)) =
if (d ==0 || a ==0 || c ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
((Rationals.standard_form (b, a)), (Rationals.standard_form (d, c)))
let from_rational (a,b) =
if ( b ==0) then raise (Division_by_zero("cant devide by zero"))
else
(Rationals.standard_form(a,b),(0,1))
let conj ((a, b), (c,d)) =
if (d ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
(Rationals.standard_form(a, b), Rationals.standard_form((-c), d))
let re ((a,b),(c,d)) =
if (d ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
Rationals.standard_form(a,b)
let im ((a,b),(c,d)) =
if (d ==0 || b ==0) then raise (Division_by_zero("cant devide by zero"))
else
Rationals.standard_form(c,d)
let compare (r1,i1) (r2,i2) =
if (Rationals.compare r1 r2) != 0 then Rationals.compare r1 r2
else Rationals.compare i1 i2
let to_string (r,i) =
let (k1,k2) = Rationals.standard_form r
in
let (c1,c2) = Rationals.standard_form i
in
if c1 == 0 || k1 ==0 then string_of_int(0)
else if c1<0 then string_of_int(k1) ^ "/" ^ string_of_int(k2) ^ "-" ^ string_of_int c1 ^ "/" ^ string_of_int c2 ^ "i"
else string_of_int(k1) ^ "/" ^ string_of_int(k2) ^ " + " ^ string_of_int c1 ^ "/" ^ string_of_int c2 ^ " i"
(* make sure that both the real part r and the imaginary part i
are in standard form as a rational number.
Skip a summand if it is 0.
*)
end
;;
GaussianRationals.mul ((5,10),(10,7)) ((5,10),(10,7));;