[jackhill/mal.git] / make / numbers.mk

#
# mal (Make a Lisp) number types
#

ifndef __mal_numbers_included
__mal_numbers_included := true

_TOP_DIR := $(dir $(lastword $(MAKEFILE_LIST)))
include $(_TOP_DIR)util.mk

LIST20_X := x x x x x x x x x x x x x x x x x x x x
LIST100_X := $(foreach x,$(LIST20_X),X X X X X)
LIST100_0 := $(foreach x,$(LIST20_X),0 0 0 0 0)
LIST100_9 := $(foreach x,$(LIST20_X),9 9 9 9 9)

###
### general numeric utility functions
###

int_encode = $(strip $(call _reverse,\
               $(eval __temp := $(1))\
               $(foreach a,0 1 2 3 4 5 6 7 8 9,\
                 $(eval __temp := $$(subst $$a,$$a$$(SPACE),$(__temp))))$(__temp)))

int_decode = $(strip $(call _join,$(call _reverse,$(1))))

# trim extaneous zero digits off the end (front of number)
_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)))
trim_zeros = $(strip $(if $(call _EQ,0,$(strip $(1))),$(1),$(call _reverse,$(call _trim_zeros,$(call _reverse,$(1))))))

# drop the last element of a list of words/digits
drop_last = $(call _reverse,$(wordlist 2,$(words $(1)),$(call _reverse,$(1))))

### utility function tests

#$(info $(filter-out 1,$(filter 1%,1 132 456)))
#$(info (int_encode 13): [$(call int_encode,13)])
#$(info (int_encode 156463): [$(call int_encode,156463)])
#$(info (int_decode (int_encode 156463)): [$(call int_decode,$(call int_encode,156463))])

#$(info trim_zeros(0 0 0): [$(call trim_zeros,0 0 0)])


### 
### comparisons
###

# compare two digits and return 'true' if digit 1 is less than or
# equal to digit 2
_lte_digit = $(strip \
              $(if $(call _EQ,$(1),$(2)),\
                true,\
                $(if $(call _EQ,0,$(1)),\
                  true,\
                  $(if $(wordlist $(1),$(2),$(LIST20_X)),\
                    true,\
                    ))))

# compare two lists of digits (MSB->LSB) of equal length and return
# 'true' if number 1 is less than number 2
_lte_digits = $(strip \
                $(if $(strip $(1)),\
                  $(if $(call _EQ,$(word 1,$(1)),$(word 1,$(2))),\
                    $(call _lte_digits,$(wordlist 2,$(words $(1)),$(1)),$(wordlist 2,$(words $(2)),$(2))),\
                    $(if $(call _lte_digit,$(word 1,$(1)),$(word 1,$(2))),true,)),\
                  true))

### lte/less than or equal to

int_lte_encoded = $(strip \
                    $(foreach len1,$(words $(1)),$(foreach len2,$(words $(2)),\
                      $(if $(call _EQ,$(len1),$(len2)),\
                        $(call _lte_digits,$(call _reverse,$(1)),$(call _reverse,$(2))),\
                        $(if $(wordlist $(len1),$(len2),$(LIST100_X)),\
                          true,\
                          )))))

int_lte = $(call int_lte_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))

### lt/less than

int_lt_encoded = $(strip \
                   $(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
                     ,\
                     $(call int_lte_encoded,$(1),$(2))))

int_lt = $(call int_lt_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))

### gte/greater than or equal to

int_gte_encoded = $(strip \
                $(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
                  true,\
                  $(if $(call int_lte_encoded,$(1),$(2)),,true)))

int_gte = $(call int_gte_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))

### gt/greater than

int_gt_encoded = $(strip \
               $(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
                 ,\
                 $(call int_gte_encoded,$(1),$(2))))

int_gt = $(call int_gt_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))

#$(info _lte_digit,7,8: [$(call _lte_digit,7,8)])
#$(info _lte_digit,8,8: [$(call _lte_digit,8,8)])
#$(info _lte_digit,2,1: [$(call _lte_digit,2,1)])
#$(info _lte_digit,0,0: [$(call _lte_digit,0,0)])
#$(info _lte_digit,0,1: [$(call _lte_digit,0,1)])
#$(info _lte_digit,1,0: [$(call _lte_digit,1,0)])

#$(info _lte_digits,1 2 3,1 2 4: [$(call _lte_digits,1 2 3,1 2 4)])
#$(info _lte_digits,1 2 4,1 2 4: [$(call _lte_digits,1 2 4,1 2 4)])
#$(info _lte_digits,1 2 5,1 2 4: [$(call _lte_digits,1 2 5,1 2 4)])
#$(info _lte_digits,4 1,9 0: [$(call _lte_digits,4 1,9 0)])

#$(info int_lte_encoded,1,1: [$(call int_lte_encoded,1,1)])
#$(info int_lte_encoded,1,2: [$(call int_lte_encoded,1,2)])
#$(info int_lte_encoded,2,1: [$(call int_lte_encoded,2,1)])
#$(info int_lte_encoded,0,3: [$(call int_lte_encoded,0,3)])
#$(info int_lte_encoded,3,0: [$(call int_lte_encoded,3,0)])
#$(info int_lte_encoded,1 4,0 9: [$(call int_lte_encoded,1 4,0 9)])
#$(info int_lte_encoded,4 3 2 1,4 3 2 1: [$(call int_lte_encoded,4 3 2 1,4 3 2 1)])
#$(info int_lte_encoded,5 3 2 1,4 3 2 1: [$(call int_lte_encoded,5 3 2 1,4 3 2 1)])
#$(info int_lte_encoded,4 3 2 1,5 3 2 1: [$(call int_lte_encoded,4 3 2 1,5 3 2 1)])

#$(info int_lte,1,1: [$(call int_lte,1,1)])
#$(info int_lte,1,2: [$(call int_lte,1,2)])
#$(info int_lte,2,1: [$(call int_lte,2,1)])
#$(info int_lte,0,3: [$(call int_lte,0,3)])
#$(info int_lte,3,0: [$(call int_lte,3,0)])
#$(info int_lte,1234,1234: [$(call int_lte,1234,1234)])
#$(info int_lte,1235,1234: [$(call int_lte,1235,1234)])
#$(info int_lte,1234,1235: [$(call int_lte,1234,1235)])
#
#$(info int_lt,1,1: [$(call int_lt,1,1)])
#$(info int_lt,1,2: [$(call int_lt,1,2)])
#$(info int_lt,2,1: [$(call int_lt,2,1)])
#$(info int_lt,0,3: [$(call int_lt,0,3)])
#$(info int_lt,3,0: [$(call int_lt,3,0)])
#$(info int_lt,1234,1234: [$(call int_lt,1234,1234)])
#$(info int_lt,1235,1234: [$(call int_lt,1235,1234)])
#$(info int_lt,1234,1235: [$(call int_lt,1234,1235)])
#
#$(info int_gte,1,1: [$(call int_gte,1,1)])
#$(info int_gte,1,2: [$(call int_gte,1,2)])
#$(info int_gte,2,1: [$(call int_gte,2,1)])
#$(info int_gte,0,3: [$(call int_gte,0,3)])
#$(info int_gte,3,0: [$(call int_gte,3,0)])
#$(info int_gte,1234,1234: [$(call int_gte,1234,1234)])
#$(info int_gte,1235,1234: [$(call int_gte,1235,1234)])
#$(info int_gte,1234,1235: [$(call int_gte,1234,1235)])
#
#$(info int_gt,1,1: [$(call int_gt,1,1)])
#$(info int_gt,1,2: [$(call int_gt,1,2)])
#$(info int_gt,2,1: [$(call int_gt,2,1)])
#$(info int_gt,0,3: [$(call int_gt,0,3)])
#$(info int_gt,3,0: [$(call int_gt,3,0)])
#$(info int_gt,1234,1234: [$(call int_gt,1234,1234)])
#$(info int_gt,1235,1234: [$(call int_gt,1235,1234)])
#$(info int_gt,1234,1235: [$(call int_gt,1234,1235)])


###
### addition
###


# add_digits_with_carry
_add_digit = $(words $(if $(strip $(1)),$(wordlist 1,$(1),$(LIST20_X)),) \
                     $(if $(strip $(2)),$(wordlist 1,$(2),$(LIST20_X)),))

# add one to a single digit
_inc_digit = $(words $(wordlist 1,$(if $(1),$(1),0),$(LIST20_X)) x)

# add two encoded numbers digit by digit without resolving carries
# (each digit will be larger than 9 if there is a carry value)
_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))),)

# take the result of _add and resolve the carry values digit by digit
_resolve_carries = $(strip \
             $(if $(1),\
               $(foreach num,$(word 1,$(1)),\
                 $(if $(filter-out 1,$(filter 1%,$(num))),\
                   $(call _resolve_carries,$(call _inc_digit,$(word 2,$(1))) $(wordlist 3,$(words $(1)),$(1)),$(2) $(patsubst 1%,%,$(num))),\
                   $(call _resolve_carries,$(wordlist 2,$(words $(1)),$(1)),$(2) $(num)))),\
               $(2)))

# add two encoded numbers, returns encoded number
int_add_encoded = $(call _resolve_carries,$(call _add,$(1),$(2)))

# add two unencoded numbers, returns unencoded number
int_add = $(call int_decode,$(call int_add_encoded,$(call int_encode,$(1)),$(call int_encode,$(2))))

### addition tests

#$(info _add_digit(7,6,1): [$(call _add_digit,7,6,1)])
#$(info _add_digit(7,6,0): [$(call _add_digit,7,6,0)])
#$(info _add_digit(7,6,0): [$(call _add_digit,7,6,0)])
#$(info _carries(12 14 15): [$(call _carries,12 14 15)])
#$(info _inc_digit(0): $(call _inc_digit,0))
#$(info _inc_digit(1): $(call _inc_digit,1))
#$(info _inc_digit(9): $(call _inc_digit,9))
#$(info _inc_digit(18): $(call _inc_digit,18))
#$(info int_add_encoded(0,0): [$(call int_add_encoded,0,0)])

#$(info int_add(1,2): [$(call int_add,1,2)])
#$(info int_add(9,9): [$(call int_add,9,9)])
#$(info int_add(0,9): [$(call int_add,0,9)])
#$(info int_add(9,0): [$(call int_add,9,0)])
#$(info int_add(0,0): [$(call int_add,0,0)])
#$(info int_add(123,456): [$(call int_add,123,456)])
#$(info int_add(678,789): [$(call int_add,678,789)])
#$(info int_add(1,12): [$(call int_add,1,12)])
#$(info int_add(123,5): [$(call int_add,123,5)])
#$(info int_add(123456,9): [$(call int_add,123456,9)])
#$(info int_add(999999991,9): [$(call int_add,999999991,9)])

###
### subtraction
###

_get_zeros = $(if $(call _EQ,0,$(word 1,$(1))),$(call _get_zeros,$(wordlist 2,$(words $(1)),$(1)),$(2) 0),$(2))

# return a 9's complement of a single digit
_complement9 = $(strip \
                 $(if $(call _EQ,0,$(1)),9,\
                 $(if $(call _EQ,1,$(1)),8,\
                 $(if $(call _EQ,2,$(1)),7,\
                 $(if $(call _EQ,3,$(1)),6,\
                 $(if $(call _EQ,4,$(1)),5,\
                 $(if $(call _EQ,5,$(1)),4,\
                 $(if $(call _EQ,6,$(1)),3,\
                 $(if $(call _EQ,7,$(1)),2,\
                 $(if $(call _EQ,8,$(1)),1,\
                 $(if $(call _EQ,9,$(1)),0)))))))))))

# return a 10's complement of a single digit
_complement10 = $(call _inc_digit,$(call _complement9,$(1)))

# 
_complement_rest = $(if $(strip $(1)),\
                     $(strip \
                       $(call _complement10,$(word 1,$(1))) \
                       $(foreach digit,$(wordlist 2,$(words $(1)),$(1)),\
                         $(call _complement9,$(digit)))),)

# return the complement of a number
_complement = $(strip $(call _get_zeros,$(1)) \
                      $(call _complement_rest,$(wordlist $(call _inc_digit,$(words $(call _get_zeros,$(1)))),$(words $(1)),$(1))))

# subtracted encoded number 2 from encoded number 1 and return and
# encoded number result
int_sub_encoded = $(strip \
                $(if $(call _EQ,0,$(strip $(2))),\
                  $(1),\
                  $(call trim_zeros,\
                    $(call drop_last,\
                      $(call int_add_encoded,\
                        $(1),\
                        $(wordlist 1,$(words $(1)),$(call _complement,$(2)) $(LIST100_9)))))))

# subtract unencoded number 2 from unencoded number 1 and return
# unencoded result
int_sub = $(call int_decode,$(call int_sub_encoded,$(call int_encode,$(1)),$(call int_encode,$(2))))

### subtraction tests

#$(info _get_zeros(5 7): [$(call _get_zeros,5 7)])
#$(info _get_zeros(0 0 0 2): [$(call _get_zeros,0 0 0 2)])
#$(info _get_zeros(0 0 0 2 5): [$(call _get_zeros,0 0 0 2 5)])

#$(info _complement(0): [$(call _complement,0)])
#$(info _complement(1): [$(call _complement,1)])
#$(info _complement(9): [$(call _complement,9)])
#$(info _complement(5 7): [$(call _complement,5 7)])
#$(info _complement(0 0 0 2): [$(call _complement,0 0 0 2)])
#$(info _complement(0 0 0 5 4 3 2 1): [$(call _complement,0 0 0 5 4 3 2 1)])

#$(info int_sub_encoded(0 0 1, 3 1): [$(call int_sub_encoded,0 0 1,3 1)])
#$(info int_sub_encoded(2, 2): [$(call int_sub_encoded,2,2)])

#$(info int_sub(2,1): [$(call int_sub,2,1)])
#$(info int_sub(2,0): [$(call int_sub,2,0)])
#$(info int_sub(2,2): [$(call int_sub,2,2)])
#$(info int_sub(100,13): [$(call int_sub,100,13)])
#$(info int_sub(100,99): [$(call int_sub,100,99)])
#$(info int_sub(91,19): [$(call int_sub,91,19)])


###
### multiplication
###

# multiply two digits
#_mult_digit = $(words $(foreach x,$(1),$(2)))
_mult_digit = $(strip \
                $(words $(foreach x,$(wordlist 1,$(1),$(LIST20_X)),\
                        $(wordlist 1,$(2),$(LIST20_X)))))

# multipy every digit of number 1 with number 2
# params: digits, digit, indent_zeros, results
_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))

# multiply every digit of number 2 with every digit of number 1 adding
# correct zero padding to the end of each result
# params: digits, digits, indent_zeros, results
_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))

# add up a bunch of unencoded numbers. Basically reduce into the first number
_add_many = $(if $(word 2,$(1)),$(call _add_many,$(call int_add,$(word 1,$(1)),$(word 2,$(1))) $(wordlist  3,$(words $(1)),$(1))),$(1))

# multiply two encoded numbers, returns encoded number
int_mult_encoded = $(call trim_zeros,$(call int_encode,$(call _add_many,$(call _mult_each,$(1),$(2)))))

# multiply two unencoded numbers, returns unencoded number
int_mult = $(call int_decode,$(call int_mult_encoded,$(call int_encode,$(1)),$(call int_encode,$(2))))

#$(info _mult_digit(8,6): [$(call _mult_digit,8,6)])
#$(info _mult_digit(7,6): [$(call _mult_digit,7,6)])
#$(info _mult_row(8,6): [$(call _mult_row,8,6)])
#$(info _mult_row(8 7,6): [$(call _mult_row,8 7,6)])
#$(info _mult_row(8 7 3,6): [$(call _mult_row,8 7 3,6)])
#$(info _mult_each(8 7 6, 4 3 2): [$(call _mult_each,8 7 6,4 3 2)])
#$(info _add_many(123 234 345 456): [$(call _add_many,123 234 345 456)])

#$(info int_mult_encoded(8 7 3,6): [$(call int_mult_encoded,8 7 3,6)])
#$(info int_mult_encoded(8 7 3,0): [$(call int_mult_encoded,8 7 3,0)])

#$(info int_mult(378,6): [$(call int_mult,378,6)])
#$(info int_mult(678,234): [$(call int_mult,678,234)])
#$(info int_mult(1,23456): [$(call int_mult,1,23456)])
#$(info int_mult(0,23456): [$(call int_mult,0,23456)])
#$(info int_mult(0,0): [$(call int_mult,0,0)])

###
### division
###

# return list of zeros needed to pad number 2 to the same length as number 1
_zero_pad = $(strip $(wordlist 1,$(call int_sub,$(words $(1)),$(words $(2))),$(LIST100_0)))

# num1, num2, zero pad, result_accumulator
# algorithm:
# - B = pad with zeros to make same digit length as A
# - loop
#    - if (B <= A)
#        - A = subtract B from A
#        - C = C + 10^(B pad.length)
#    - else
#        - if B.length < origin B.length: break
#        - chop least significant digit of B
_div = $(strip \
         $(if $(call int_lte_encoded,$(3) $(2),$(1)),\
           $(call _div,$(call int_sub_encoded,$(1),$(3) $(2)),$(2),$(3),$(call int_add_encoded,$(4),$(3) 1)),\
           $(if $(3),\
             $(call _div,$(1),$(2),$(wordlist 2,$(words $(3)),$(3)),$(4)),\
             $(4))))

# divide two encoded numbers, returns encoded number
int_div_encoded = $(strip \
                $(if $(call _EQ,0,$(1)),\
                  0,\
                  $(if $(call _EQ,$(1),$(2)),\
                    1,\
                    $(if $(call int_gt_encoded,$(2),$(1)),\
                      0,\
                      $(call _div,$(1),$(2),$(call _zero_pad,$(1),$(2)),0)))))

# divide two unencoded numbers, returns unencoded number
int_div = $(call int_decode,$(call int_div_encoded,$(call int_encode,$(1)),$(call int_encode,$(2))))

### division tests

#$(info _zero_pad(1 2 3 4,1 3): [$(call _zero_pad,1 2 3 4,1 3)])
#$(info _zero_pad(1 2,1 3): [$(call _zero_pad,1 2,1 3)])
#$(info _zero_pad(2,1 3): [$(call _zero_pad,1 2,1 3)])
#
#$(info int_div_encoded(2,1): [$(call int_div_encoded,2,1)])
#$(info int_div_encoded(3,1): [$(call int_div_encoded,3,1)])
#$(info int_div_encoded(3,2): [$(call int_div_encoded,3,2)])
#$(info int_div_encoded(0,7): [$(call int_div_encoded,0,7)])
#$(info int_div_encoded(0 3,0 2): [$(call int_div_encoded,0 3,0 2)])
#$(info int_div_encoded(0 3,5): [$(call int_div_encoded,0 3,5)])
#
#$(info int_div(5,1): [$(call int_div,5,1)])
#$(info int_div(5,2): [$(call int_div,5,2)])
#$(info int_div(123,7): [$(call int_div,123,7)])
#$(info int_div(100,7): [$(call int_div,100,7)])


### combination tests

# (/ (- (+ 515 (* 222 311)) 300) 41)
#$(info int_mult,222,311: [$(call int_mult,222,311)])
#$(info int_add(515,69042): [$(call int_add,515,69042)])
#$(info int_sub(69557,300): [$(call int_sub,69557,300)])
#$(info int_div(69257,41): [$(call int_div,69257,41)])

###############################################################

all:
	@true

endif

# vim: ts=2 et
Commit	Line	Data
f4c8a091 JM	1	#
	2	# mal (Make a Lisp) number types
	3	#
	4
	5	ifndef __mal_numbers_included
	6	__mal_numbers_included := true
	7
	8	_TOP_DIR := $(dir $(lastword $(MAKEFILE_LIST)))
	9	include $(_TOP_DIR)util.mk
	10
	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)
	15
	16	###
	17	### general numeric utility functions
	18	###
	19
	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)))
	24
	25	int_decode = $(strip $(call _join,$(call _reverse,$(1))))
	26
	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))))))
	30
	31	# drop the last element of a list of words/digits
	32	drop_last = $(call _reverse,$(wordlist 2,$(words $(1)),$(call _reverse,$(1))))
	33
	34	### utility function tests
	35
	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))])
	40
	41	#$(info trim_zeros(0 0 0): [$(call trim_zeros,0 0 0)])
	42
	43
	44	###
	45	### comparisons
	46	###
	47
	48	# compare two digits and return 'true' if digit 1 is less than or
	49	# equal to digit 2
	50	_lte_digit = $(strip \
	51	$(if $(call _EQ,$(1),$(2)),\
	52	true,\
	53	$(if $(call _EQ,0,$(1)),\
	54	true,\
	55	$(if $(wordlist $(1),$(2),$(LIST20_X)),\
	56	true,\
	57	))))
	58
	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 \
	62	$(if $(strip $(1)),\
	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,)),\
66	true))
67
68	### lte/less than or equal to
69
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)),\
75	true,\
76	)))))
77
78	int_lte = $(call int_lte_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))
79
80	### lt/less than
81
82	int_lt_encoded = $(strip \
83	$(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
84	,\
85	$(call int_lte_encoded,$(1),$(2))))
86
87	int_lt = $(call int_lt_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))
88
89	### gte/greater than or equal to
90
91	int_gte_encoded = $(strip \
92	$(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
93	true,\
94	$(if $(call int_lte_encoded,$(1),$(2)),,true)))
95
96	int_gte = $(call int_gte_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))
97
98	### gt/greater than
99
100	int_gt_encoded = $(strip \
101	$(if $(call _EQ,$(strip $(1)),$(strip $(2))),\
102	,\
103	$(call int_gte_encoded,$(1),$(2))))
104
105	int_gt = $(call int_gt_encoded,$(call int_encode,$(1)),$(call int_encode,$(2)))
106
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)])
113
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)])
118
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)])
128
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)])
137	#
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)])
146	#
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)])
155	#
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)])
164
165
166	###
167	### addition
168	###
169
170
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)),))
174
175	# add one to a single digit
176	_inc_digit = $(words $(wordlist 1,$(if $(1),$(1),0),$(LIST20_X)) x)
177
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))),)
181
182	# take the result of _add and resolve the carry values digit by digit
183	_resolve_carries = $(strip \
184	$(if $(1),\
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)))),\
189	$(2)))
190
191	# add two encoded numbers, returns encoded number
192	int_add_encoded = $(call _resolve_carries,$(call _add,$(1),$(2)))
193
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))))
196
197	### addition tests
198
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)])
208
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)])
220
221	###
222	### subtraction
223	###
224
225	_get_zeros = $(if $(call _EQ,0,$(word 1,$(1))),$(call _get_zeros,$(wordlist 2,$(words $(1)),$(1)),$(2) 0),$(2))
226
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)))))))))))
239
240	# return a 10's complement of a single digit
241	_complement10 = $(call _inc_digit,$(call _complement9,$(1)))
242
243	#
244	_complement_rest = $(if $(strip $(1)),\
245	$(strip \
246	$(call _complement10,$(word 1,$(1))) \
247	$(foreach digit,$(wordlist 2,$(words $(1)),$(1)),\
248	$(call _complement9,$(digit)))),)
249
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))))
253
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))),\
258	$(1),\
259	$(call trim_zeros,\
260	$(call drop_last,\
261	$(call int_add_encoded,\
262	$(1),\
263	$(wordlist 1,$(words $(1)),$(call _complement,$(2)) $(LIST100_9)))))))
264
265	# subtract unencoded number 2 from unencoded number 1 and return
266	# unencoded result
267	int_sub = $(call int_decode,$(call int_sub_encoded,$(call int_encode,$(1)),$(call int_encode,$(2))))
268
269	### subtraction tests
270
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)])
274
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)])
281
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)])
284
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)])
291
292
293	###
294	### multiplication
295	###
296
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)))))
302
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))
306
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))
311
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))
314
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)))))
317
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))))
320
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)])
328
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)])
331
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)])
337
338	###
339	### division
340	###
341
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)))
344
345	# num1, num2, zero pad, result_accumulator
346	# algorithm:
347	# - B = pad with zeros to make same digit length as A
348	# - loop
349	# - if (B <= A)
350	# - A = subtract B from A
351	# - C = C + 10^(B pad.length)
352	# - else
353	# - if B.length < origin B.length: break
354	# - chop least significant digit of B
355	_div = $(strip \
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)),\
358	$(if $(3),\
359	$(call _div,$(1),$(2),$(wordlist 2,$(words $(3)),$(3)),$(4)),\
360	$(4))))
361
362	# divide two encoded numbers, returns encoded number
363	int_div_encoded = $(strip \
364	$(if $(call _EQ,0,$(1)),\
365	0,\
366	$(if $(call _EQ,$(1),$(2)),\
367	1,\
368	$(if $(call int_gt_encoded,$(2),$(1)),\
369	0,\
370	$(call _div,$(1),$(2),$(call _zero_pad,$(1),$(2)),0)))))
371
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))))
374
375	### division tests
376
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)])
380	#
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)])
387	#
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)])
392
393
394	### combination tests
395
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)])
401
402	###############################################################
403
404	all:
405	@true
406
407	endif
408
409	# vim: ts=2 et