-
Notifications
You must be signed in to change notification settings - Fork 0
/
bignums.smt
221 lines (185 loc) · 5.55 KB
/
bignums.smt
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
(class Natural Magnitude
(degree digitArray base)
(class-method new: (anInteger)
(newInt: (new self) anInteger))
(method newInt: (anInteger) (locals count digitList)
(set base 10)
(set count 0)
(set digitList (new List))
(whileTrue: {(> anInteger 0)}
{
(addLast: digitList (mod: anInteger base))
(set anInteger (asInteger (/ anInteger base)))
(set count (+ count 1))})
(ifTrue: (= count 0)
{(addLast: digitList 0)
(set count 1)})
(digits: self digitList)
(set degree count)
self)
(method degree ()
degree)
(method base ()
base)
(method digit: (anIndex) ; 1-indexed
(at: digitArray anIndex))
(method digit:put: (anIndex aDigit) ; 1-indexed
(at:put: digitArray anIndex aDigit))
(method makeEmpty: (aDegree) (locals apply)
(set apply (block (i) (digit:put: self i 0)))
(set digitArray (new: Array aDegree))
(set degree aDegree)
(doDigits: self apply))
(method doDigits: (aBlock) (locals i)
(set i 0)
(whileTrue: {(< i degree)}
{(set i (+ i 1))
(value aBlock i)}))
(method trim ()
(whileTrue: {(& (> degree 1) (= (at: digitArray degree) 0))}
{(set degree (- degree 1))}))
(method digits: (aSequence)
(set degree (size aSequence))
(if (= degree 0)
{(set degree 1)
(set digitArray (new: Array 1))
(at:put: digitArray 1 0)}
{(set digitArray (from: Array aSequence))}))
(method decimal () (locals i result)
(set i degree)
(set result (new List)) ; where?
(whileTrue: {(> i 0)}
{(addLast: result (at: digitArray i))
(set i (- i 1))})
result) ; return result list
(method print () (locals digitList)
(set digitList (decimal self))
(do: digitList (block (x) (print x))))
(method isZero ()
(& (= degree 1) (= (at: digitArray 1) 0)))
(method = (x) (locals apply isEqual)
(set isEqual true)
(if (= degree (degree x))
{(set apply (block (i) (if (= (at: digitArray i) (digit: x i))
{(set isEqual (& isEqual true))}
{(set isEqual (& isEqual false))})))
(doDigits: self apply)}
{(set isEqual false)})
isEqual)
(method set:plus: (x y) (locals apply xi yi sum resultDegree carry)
(set carry 0)
(set apply (block (i)
(if (> i (degree y))
{(set yi 0)}
{(set yi (digit: y i))})
(if (> i (degree x))
{(set xi 0)}
{(set xi (digit: x i))})
(set sum (+ (+ xi yi) carry))
(at:put: digitArray i (mod: sum base))
(set carry (asInteger (/ sum base)))))
(if (>= (degree x) (degree y))
{(if (= degree (+ (degree x) 1))
{(set degree (+ (degree x) 1))
(doDigits: self apply)
self}
{(error: self #ill-fitted-receiver)})}
{(set:plus: self y x)}))
(method set:minus: (x y) (locals borrow apply diff resultDegree isValid xi yi)
(set borrow 0)
(set apply (block (i)
(if (> i (degree y))
{(set yi 0)}
{(set yi (digit: y i))})
(set xi (digit: x i))
(ifTrue: (> yi xi)
{(if (= i degree)
{(set borrow 1)}
{(set xi (+ base xi))
(digit:put: x (+ i 1) (- (digit: x (+ i 1)) 1))})})
(set diff (- xi yi))
(at:put: digitArray i diff)))
(if (>= (degree x) (degree y))
{(if (= degree (degree x))
{(set resultDegree degree)
(makeEmpty: self resultDegree)
(doDigits: self apply)
(set degree resultDegree)
(trim self)}
{(error: self #ill-fitted-receiver)})}
{(set borrow 1)})
borrow)
(method + (x) (locals deg result)
(if (>= degree (degree x))
{(set deg (+ (degree self) 1))}
{(set deg (+ (degree x) 1))})
(set result (new: Natural 0))
(makeEmpty: result deg)
(set:plus: result self x)
(trim result)
result)
(method subtract:withDifference:ifNegative: (aNatural diffBlock negativeBlock)
(locals result borrow deg)
(ifFalse: (>= degree (degree aNatural))
{(value negativeBlock)})
(set result (new: Natural 0))
(makeEmpty: result degree)
(set borrow (set:minus: result self aNatural))
(if (= borrow 0)
{(trim result)
(value diffBlock result)}
{(value negativeBlock)}))
(method - (x) (locals result diff negative )
(set diff (block (z) z))
(set negative {(error: self #difference-not-a-natural-number)})
(subtract:withDifference:ifNegative: self x diff negative))
; (method - (x) (locals result borrow deg)
; (ifFalse: (>= degree (degree x))
; {(error: self #difference-not-a-natural-number)})
; (set result (new: Natural 0))
; (makeEmpty: result degree)
; (set borrow (set:minus: result self x))
; (if (= borrow 0)
; {(trim result)
; (decimal result)}
; {(error: self #difference-not-a-natural-number)})
; )
(method set:multiply: (x y) (locals i j carry)
(ifFalse: (= degree (+ (degree x) (degree y)))
{(error: self #ill-fitted-receiver)})
;(set carry 0)
(makeEmpty: self degree)
(set i 0)
; (println self)
; (println degree)
; (println #x-is)
; (println x)
; (println #y-is)
; (println y)
; (println #deg-x-is)
; (println (degree x))
; (println #deg-y-is)
; (println (degree y))
(whileTrue: {(< i (degree x))}
{(set carry 0)
(set j 0)
(whileTrue: {(< j (degree y))}
{(set carry (+ carry (+ (* (digit: x (+ i 1)) (digit: y (+ j 1))) (digit: self (+ (+ i j) 1)))))
(digit:put: self (+ (+ i j) 1) (mod: carry base))
(set carry (asInteger (/ carry base)))
(set j (+ j 1))})
(digit:put: self (+ (+ i j) 1) carry)
(set i (+ i 1))})
;carry
self)
(method * (x) (locals result)
(set result (new: Natural 0))
(makeEmpty: result (+ (degree x) degree))
(set:multiply: result self x)
(trim result)
result)
(method < (x) (locals result diff negative)
(set diff (block (x) false))
(set negative {true})
(subtract:withDifference:ifNegative: self x diff negative))
)