2 # mal (Make a Lisp) number types
5 ifndef __mal_numbers_included
6 __mal_numbers_included
:= true
8 _TOP_DIR
:= $(dir $(lastword
$(MAKEFILE_LIST
)))
9 include $(_TOP_DIR
)util.mk
11 LIST20_X
:= x x x x x x x x x x x x x x x x x x x x
12 LIST100_X
:= $(foreach x
,$(LIST20_X
),X X X X X
)
13 LIST100_0
:= $(foreach x
,$(LIST20_X
),0 0 0 0 0)
14 LIST100_9
:= $(foreach x
,$(LIST20_X
),9 9 9 9 9)
17 ### general numeric utility functions
20 int_encode
= $(strip $(call _reverse
,\
21 $(eval __temp
:= $(1))\
22 $(foreach a
,0 1 2 3 4 5 6 7 8 9,\
23 $(eval __temp
:= $$(subst $$a,$$a$$(SPACE
),$(__temp
))))$(__temp
)))
25 int_decode
= $(strip $(call _join
,$(call _reverse
,$(1))))
27 # trim extaneous zero digits off the end (front of number)
28 _trim_zeros
= $(if
$(call _EQ
,0,$(strip $(1))),0,$(if
$(call _EQ
,0,$(word 1,$(1))),$(call _trim_zeros
,$(wordlist
2,$(words $(1)),$(1))),$(1)))
29 trim_zeros
= $(strip $(if
$(call _EQ
,0,$(strip $(1))),$(1),$(call _reverse
,$(call _trim_zeros
,$(call _reverse
,$(1))))))
31 # drop the last element of a list of words/digits
32 drop_last
= $(call _reverse
,$(wordlist
2,$(words $(1)),$(call _reverse
,$(1))))
34 ### utility function tests
36 #$(info $(filter-out 1,$(filter 1%,1 132 456)))
37 #$(info (int_encode 13): [$(call int_encode,13)])
38 #$(info (int_encode 156463): [$(call int_encode,156463)])
39 #$(info (int_decode (int_encode 156463)): [$(call int_decode,$(call int_encode,156463))])
41 #$(info trim_zeros(0 0 0): [$(call trim_zeros,0 0 0)])
48 # compare two digits and return 'true' if digit 1 is less than or
50 _lte_digit
= $(strip \
51 $(if
$(call _EQ
,$(1),$(2)),\
53 $(if
$(call _EQ
,0,$(1)),\
55 $(if
$(wordlist
$(1),$(2),$(LIST20_X
)),\
59 # compare two lists of digits (MSB->LSB) of equal length and return
60 # 'true' if number 1 is less than number 2
61 _lte_digits
= $(strip \
63 $(if
$(call _EQ
,$(word 1,$(1)),$(word 1,$(2))),\
64 $(call _lte_digits
,$(wordlist
2,$(words $(1)),$(1)),$(wordlist
2,$(words $(2)),$(2))),\
65 $(if
$(call _lte_digit
,$(word 1,$(1)),$(word 1,$(2))),true
,)),\
68 ### lte/less than or equal to
70 int_lte_encoded
= $(strip \
71 $(foreach len1
,$(words $(1)),$(foreach len2
,$(words $(2)),\
72 $(if
$(call _EQ
,$(len1
),$(len2
)),\
73 $(call _lte_digits
,$(call _reverse
,$(1)),$(call _reverse
,$(2))),\
74 $(if
$(wordlist
$(len1
),$(len2
),$(LIST100_X
)),\
78 int_lte
= $(call int_lte_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2)))
82 int_lt_encoded
= $(strip \
83 $(if
$(call _EQ
,$(strip $(1)),$(strip $(2))),\
85 $(call int_lte_encoded
,$(1),$(2))))
87 int_lt
= $(call int_lt_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2)))
89 ### gte/greater than or equal to
91 int_gte_encoded
= $(strip \
92 $(if
$(call _EQ
,$(strip $(1)),$(strip $(2))),\
94 $(if
$(call int_lte_encoded
,$(1),$(2)),,true
)))
96 int_gte
= $(call int_gte_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2)))
100 int_gt_encoded
= $(strip \
101 $(if
$(call _EQ
,$(strip $(1)),$(strip $(2))),\
103 $(call int_gte_encoded
,$(1),$(2))))
105 int_gt
= $(call int_gt_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2)))
107 #$(info _lte_digit,7,8: [$(call _lte_digit,7,8)])
108 #$(info _lte_digit,8,8: [$(call _lte_digit,8,8)])
109 #$(info _lte_digit,2,1: [$(call _lte_digit,2,1)])
110 #$(info _lte_digit,0,0: [$(call _lte_digit,0,0)])
111 #$(info _lte_digit,0,1: [$(call _lte_digit,0,1)])
112 #$(info _lte_digit,1,0: [$(call _lte_digit,1,0)])
114 #$(info _lte_digits,1 2 3,1 2 4: [$(call _lte_digits,1 2 3,1 2 4)])
115 #$(info _lte_digits,1 2 4,1 2 4: [$(call _lte_digits,1 2 4,1 2 4)])
116 #$(info _lte_digits,1 2 5,1 2 4: [$(call _lte_digits,1 2 5,1 2 4)])
117 #$(info _lte_digits,4 1,9 0: [$(call _lte_digits,4 1,9 0)])
119 #$(info int_lte_encoded,1,1: [$(call int_lte_encoded,1,1)])
120 #$(info int_lte_encoded,1,2: [$(call int_lte_encoded,1,2)])
121 #$(info int_lte_encoded,2,1: [$(call int_lte_encoded,2,1)])
122 #$(info int_lte_encoded,0,3: [$(call int_lte_encoded,0,3)])
123 #$(info int_lte_encoded,3,0: [$(call int_lte_encoded,3,0)])
124 #$(info int_lte_encoded,1 4,0 9: [$(call int_lte_encoded,1 4,0 9)])
125 #$(info int_lte_encoded,4 3 2 1,4 3 2 1: [$(call int_lte_encoded,4 3 2 1,4 3 2 1)])
126 #$(info int_lte_encoded,5 3 2 1,4 3 2 1: [$(call int_lte_encoded,5 3 2 1,4 3 2 1)])
127 #$(info int_lte_encoded,4 3 2 1,5 3 2 1: [$(call int_lte_encoded,4 3 2 1,5 3 2 1)])
129 #$(info int_lte,1,1: [$(call int_lte,1,1)])
130 #$(info int_lte,1,2: [$(call int_lte,1,2)])
131 #$(info int_lte,2,1: [$(call int_lte,2,1)])
132 #$(info int_lte,0,3: [$(call int_lte,0,3)])
133 #$(info int_lte,3,0: [$(call int_lte,3,0)])
134 #$(info int_lte,1234,1234: [$(call int_lte,1234,1234)])
135 #$(info int_lte,1235,1234: [$(call int_lte,1235,1234)])
136 #$(info int_lte,1234,1235: [$(call int_lte,1234,1235)])
138 #$(info int_lt,1,1: [$(call int_lt,1,1)])
139 #$(info int_lt,1,2: [$(call int_lt,1,2)])
140 #$(info int_lt,2,1: [$(call int_lt,2,1)])
141 #$(info int_lt,0,3: [$(call int_lt,0,3)])
142 #$(info int_lt,3,0: [$(call int_lt,3,0)])
143 #$(info int_lt,1234,1234: [$(call int_lt,1234,1234)])
144 #$(info int_lt,1235,1234: [$(call int_lt,1235,1234)])
145 #$(info int_lt,1234,1235: [$(call int_lt,1234,1235)])
147 #$(info int_gte,1,1: [$(call int_gte,1,1)])
148 #$(info int_gte,1,2: [$(call int_gte,1,2)])
149 #$(info int_gte,2,1: [$(call int_gte,2,1)])
150 #$(info int_gte,0,3: [$(call int_gte,0,3)])
151 #$(info int_gte,3,0: [$(call int_gte,3,0)])
152 #$(info int_gte,1234,1234: [$(call int_gte,1234,1234)])
153 #$(info int_gte,1235,1234: [$(call int_gte,1235,1234)])
154 #$(info int_gte,1234,1235: [$(call int_gte,1234,1235)])
156 #$(info int_gt,1,1: [$(call int_gt,1,1)])
157 #$(info int_gt,1,2: [$(call int_gt,1,2)])
158 #$(info int_gt,2,1: [$(call int_gt,2,1)])
159 #$(info int_gt,0,3: [$(call int_gt,0,3)])
160 #$(info int_gt,3,0: [$(call int_gt,3,0)])
161 #$(info int_gt,1234,1234: [$(call int_gt,1234,1234)])
162 #$(info int_gt,1235,1234: [$(call int_gt,1235,1234)])
163 #$(info int_gt,1234,1235: [$(call int_gt,1234,1235)])
171 # add_digits_with_carry
172 _add_digit
= $(words $(if
$(strip $(1)),$(wordlist
1,$(1),$(LIST20_X
)),) \
173 $(if
$(strip $(2)),$(wordlist
1,$(2),$(LIST20_X
)),))
175 # add one to a single digit
176 _inc_digit
= $(words $(wordlist
1,$(if
$(1),$(1),0),$(LIST20_X
)) x
)
178 # add two encoded numbers digit by digit without resolving carries
179 # (each digit will be larger than 9 if there is a carry value)
180 _add
= $(if
$(1)$(2),$(call _add_digit
,$(word 1,$(1)),$(word 1,$(2))) $(call _add
,$(wordlist
2,$(words $(1)),$(1)),$(wordlist
2,$(words $(2)),$(2))),)
182 # take the result of _add and resolve the carry values digit by digit
183 _resolve_carries
= $(strip \
185 $(foreach num
,$(word 1,$(1)),\
186 $(if
$(filter-out 1,$(filter 1%,$(num
))),\
187 $(call _resolve_carries
,$(call _inc_digit
,$(word 2,$(1))) $(wordlist
3,$(words $(1)),$(1)),$(2) $(patsubst 1%,%,$(num
))),\
188 $(call _resolve_carries
,$(wordlist
2,$(words $(1)),$(1)),$(2) $(num
)))),\
191 # add two encoded numbers, returns encoded number
192 int_add_encoded
= $(call _resolve_carries
,$(call _add
,$(1),$(2)))
194 # add two unencoded numbers, returns unencoded number
195 int_add
= $(call int_decode
,$(call int_add_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2))))
199 #$(info _add_digit(7,6,1): [$(call _add_digit,7,6,1)])
200 #$(info _add_digit(7,6,0): [$(call _add_digit,7,6,0)])
201 #$(info _add_digit(7,6,0): [$(call _add_digit,7,6,0)])
202 #$(info _carries(12 14 15): [$(call _carries,12 14 15)])
203 #$(info _inc_digit(0): $(call _inc_digit,0))
204 #$(info _inc_digit(1): $(call _inc_digit,1))
205 #$(info _inc_digit(9): $(call _inc_digit,9))
206 #$(info _inc_digit(18): $(call _inc_digit,18))
207 #$(info int_add_encoded(0,0): [$(call int_add_encoded,0,0)])
209 #$(info int_add(1,2): [$(call int_add,1,2)])
210 #$(info int_add(9,9): [$(call int_add,9,9)])
211 #$(info int_add(0,9): [$(call int_add,0,9)])
212 #$(info int_add(9,0): [$(call int_add,9,0)])
213 #$(info int_add(0,0): [$(call int_add,0,0)])
214 #$(info int_add(123,456): [$(call int_add,123,456)])
215 #$(info int_add(678,789): [$(call int_add,678,789)])
216 #$(info int_add(1,12): [$(call int_add,1,12)])
217 #$(info int_add(123,5): [$(call int_add,123,5)])
218 #$(info int_add(123456,9): [$(call int_add,123456,9)])
219 #$(info int_add(999999991,9): [$(call int_add,999999991,9)])
225 _get_zeros
= $(if
$(call _EQ
,0,$(word 1,$(1))),$(call _get_zeros
,$(wordlist
2,$(words $(1)),$(1)),$(2) 0),$(2))
227 # return a 9's complement of a single digit
228 _complement9
= $(strip \
229 $(if
$(call _EQ
,0,$(1)),9,\
230 $(if
$(call _EQ
,1,$(1)),8,\
231 $(if
$(call _EQ
,2,$(1)),7,\
232 $(if
$(call _EQ
,3,$(1)),6,\
233 $(if
$(call _EQ
,4,$(1)),5,\
234 $(if
$(call _EQ
,5,$(1)),4,\
235 $(if
$(call _EQ
,6,$(1)),3,\
236 $(if
$(call _EQ
,7,$(1)),2,\
237 $(if
$(call _EQ
,8,$(1)),1,\
238 $(if
$(call _EQ
,9,$(1)),0)))))))))))
240 # return a 10's complement of a single digit
241 _complement10
= $(call _inc_digit
,$(call _complement9
,$(1)))
244 _complement_rest
= $(if
$(strip $(1)),\
246 $(call _complement10
,$(word 1,$(1))) \
247 $(foreach digit
,$(wordlist
2,$(words $(1)),$(1)),\
248 $(call _complement9
,$(digit
)))),)
250 # return the complement of a number
251 _complement
= $(strip $(call _get_zeros
,$(1)) \
252 $(call _complement_rest
,$(wordlist
$(call _inc_digit
,$(words $(call _get_zeros
,$(1)))),$(words $(1)),$(1))))
254 # subtracted encoded number 2 from encoded number 1 and return and
255 # encoded number result
256 int_sub_encoded
= $(strip \
257 $(if
$(call _EQ
,0,$(strip $(2))),\
261 $(call int_add_encoded
,\
263 $(wordlist
1,$(words $(1)),$(call _complement
,$(2)) $(LIST100_9
)))))))
265 # subtract unencoded number 2 from unencoded number 1 and return
267 int_sub
= $(call int_decode
,$(call int_sub_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2))))
269 ### subtraction tests
271 #$(info _get_zeros(5 7): [$(call _get_zeros,5 7)])
272 #$(info _get_zeros(0 0 0 2): [$(call _get_zeros,0 0 0 2)])
273 #$(info _get_zeros(0 0 0 2 5): [$(call _get_zeros,0 0 0 2 5)])
275 #$(info _complement(0): [$(call _complement,0)])
276 #$(info _complement(1): [$(call _complement,1)])
277 #$(info _complement(9): [$(call _complement,9)])
278 #$(info _complement(5 7): [$(call _complement,5 7)])
279 #$(info _complement(0 0 0 2): [$(call _complement,0 0 0 2)])
280 #$(info _complement(0 0 0 5 4 3 2 1): [$(call _complement,0 0 0 5 4 3 2 1)])
282 #$(info int_sub_encoded(0 0 1, 3 1): [$(call int_sub_encoded,0 0 1,3 1)])
283 #$(info int_sub_encoded(2, 2): [$(call int_sub_encoded,2,2)])
285 #$(info int_sub(2,1): [$(call int_sub,2,1)])
286 #$(info int_sub(2,0): [$(call int_sub,2,0)])
287 #$(info int_sub(2,2): [$(call int_sub,2,2)])
288 #$(info int_sub(100,13): [$(call int_sub,100,13)])
289 #$(info int_sub(100,99): [$(call int_sub,100,99)])
290 #$(info int_sub(91,19): [$(call int_sub,91,19)])
297 # multiply two digits
298 #_mult_digit = $(words $(foreach x,$(1),$(2)))
299 _mult_digit
= $(strip \
300 $(words $(foreach x
,$(wordlist
1,$(1),$(LIST20_X
)),\
301 $(wordlist
1,$(2),$(LIST20_X
)))))
303 # multipy every digit of number 1 with number 2
304 # params: digits, digit, indent_zeros, results
305 _mult_row
= $(if
$(strip $(1)),$(call _mult_row
,$(wordlist
2,$(words $(1)),$(1)),$(2),$(3)0,$(4) $(call _mult_digit
,$(word 1,$(1)),$(2))$(3)),$(4))
307 # multiply every digit of number 2 with every digit of number 1 adding
308 # correct zero padding to the end of each result
309 # params: digits, digits, indent_zeros, results
310 _mult_each
= $(if
$(strip $(2)),$(call _mult_each
,$(1),$(wordlist
2,$(words $(2)),$(2)),$(3)0,$(4) $(call _mult_row
,$(1),$(word 1,$(2)),$(3))),$(4))
312 # add up a bunch of unencoded numbers. Basically reduce into the first number
313 _add_many
= $(if
$(word 2,$(1)),$(call _add_many
,$(call int_add
,$(word 1,$(1)),$(word 2,$(1))) $(wordlist
3,$(words $(1)),$(1))),$(1))
315 # multiply two encoded numbers, returns encoded number
316 int_mult_encoded
= $(call trim_zeros
,$(call int_encode
,$(call _add_many
,$(call _mult_each
,$(1),$(2)))))
318 # multiply two unencoded numbers, returns unencoded number
319 int_mult
= $(call int_decode
,$(call int_mult_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2))))
321 #$(info _mult_digit(8,6): [$(call _mult_digit,8,6)])
322 #$(info _mult_digit(7,6): [$(call _mult_digit,7,6)])
323 #$(info _mult_row(8,6): [$(call _mult_row,8,6)])
324 #$(info _mult_row(8 7,6): [$(call _mult_row,8 7,6)])
325 #$(info _mult_row(8 7 3,6): [$(call _mult_row,8 7 3,6)])
326 #$(info _mult_each(8 7 6, 4 3 2): [$(call _mult_each,8 7 6,4 3 2)])
327 #$(info _add_many(123 234 345 456): [$(call _add_many,123 234 345 456)])
329 #$(info int_mult_encoded(8 7 3,6): [$(call int_mult_encoded,8 7 3,6)])
330 #$(info int_mult_encoded(8 7 3,0): [$(call int_mult_encoded,8 7 3,0)])
332 #$(info int_mult(378,6): [$(call int_mult,378,6)])
333 #$(info int_mult(678,234): [$(call int_mult,678,234)])
334 #$(info int_mult(1,23456): [$(call int_mult,1,23456)])
335 #$(info int_mult(0,23456): [$(call int_mult,0,23456)])
336 #$(info int_mult(0,0): [$(call int_mult,0,0)])
342 # return list of zeros needed to pad number 2 to the same length as number 1
343 _zero_pad
= $(strip $(wordlist
1,$(call int_sub
,$(words $(1)),$(words $(2))),$(LIST100_0
)))
345 # num1, num2, zero pad, result_accumulator
347 # - B = pad with zeros to make same digit length as A
350 # - A = subtract B from A
351 # - C = C + 10^(B pad.length)
353 # - if B.length < origin B.length: break
354 # - chop least significant digit of B
356 $(if
$(call int_lte_encoded
,$(3) $(2),$(1)),\
357 $(call _div
,$(call int_sub_encoded
,$(1),$(3) $(2)),$(2),$(3),$(call int_add_encoded
,$(4),$(3) 1)),\
359 $(call _div
,$(1),$(2),$(wordlist
2,$(words $(3)),$(3)),$(4)),\
362 # divide two encoded numbers, returns encoded number
363 int_div_encoded
= $(strip \
364 $(if
$(call _EQ
,0,$(1)),\
366 $(if
$(call _EQ
,$(1),$(2)),\
368 $(if
$(call int_gt_encoded
,$(2),$(1)),\
370 $(call _div
,$(1),$(2),$(call _zero_pad
,$(1),$(2)),0)))))
372 # divide two unencoded numbers, returns unencoded number
373 int_div
= $(call int_decode
,$(call int_div_encoded
,$(call int_encode
,$(1)),$(call int_encode
,$(2))))
377 #$(info _zero_pad(1 2 3 4,1 3): [$(call _zero_pad,1 2 3 4,1 3)])
378 #$(info _zero_pad(1 2,1 3): [$(call _zero_pad,1 2,1 3)])
379 #$(info _zero_pad(2,1 3): [$(call _zero_pad,1 2,1 3)])
381 #$(info int_div_encoded(2,1): [$(call int_div_encoded,2,1)])
382 #$(info int_div_encoded(3,1): [$(call int_div_encoded,3,1)])
383 #$(info int_div_encoded(3,2): [$(call int_div_encoded,3,2)])
384 #$(info int_div_encoded(0,7): [$(call int_div_encoded,0,7)])
385 #$(info int_div_encoded(0 3,0 2): [$(call int_div_encoded,0 3,0 2)])
386 #$(info int_div_encoded(0 3,5): [$(call int_div_encoded,0 3,5)])
388 #$(info int_div(5,1): [$(call int_div,5,1)])
389 #$(info int_div(5,2): [$(call int_div,5,2)])
390 #$(info int_div(123,7): [$(call int_div,123,7)])
391 #$(info int_div(100,7): [$(call int_div,100,7)])
394 ### combination tests
396 # (/ (- (+ 515 (* 222 311)) 300) 41)
397 #$(info int_mult,222,311: [$(call int_mult,222,311)])
398 #$(info int_add(515,69042): [$(call int_add,515,69042)])
399 #$(info int_sub(69557,300): [$(call int_sub,69557,300)])
400 #$(info int_div(69257,41): [$(call int_div,69257,41)])
402 ###############################################################