Re: [PATCH 3/3] Handle (-1) + (1) and (-3) - (-2) with bigints

[Ori Bernstein <ori@xxxxxxxxxxxxxx>]

Pushed, thanks!

On Tue, 19 Feb 2019 08:19:09 -0500
"S. Gilles" <sgilles@xxxxxxxxxxxx> wrote:

> ---
>  lib/std/bigint.myr      |  42 ++++++++++---
>  lib/std/test/bigint.myr | 135 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 167 insertions(+), 10 deletions(-)
> 
> diff --git a/lib/std/bigint.myr b/lib/std/bigint.myr
> index c13f0df9..7b0f4bc0 100644
> --- a/lib/std/bigint.myr
> +++ b/lib/std/bigint.myr
> @@ -40,6 +40,7 @@ pkg std =
>  	const bigiszero	: (a : bigint# -> bool)
>  	const bigiseven	: (a : bigint# -> bool)
>  	const bigcmp	: (a : bigint#, b : bigint# -> order)
> +	const bigcmpabs	: (a : bigint#, b : bigint# -> order)
>  	generic bigcmpi	: (a : bigint#, b : @a -> order) :: numeric,integral @a
>  
>  	/* shorthand for comparisons */
> @@ -412,6 +413,23 @@ const bigcmp = {a, b
>  	-> `Equal
>  }
>  
> +const bigcmpabs = {a, b
> +	if a.dig.len < b.dig.len
> +		-> `Before
> +	elif a.dig.len > b.dig.len
> +		-> `After
> +	else
> +		for var i = a.dig.len; i > 0; i--
> +			var da = (a.dig[i - 1]  : int64)
> +			var db = (b.dig[i - 1]  : int64)
> +			if da != db
> +				-> signedorder(da - db)
> +			;;
> +		;;
> +	;;
> +	-> `Equal
> +}
> +
>  const signedorder = {sign
>  	if sign < 0
>  		-> `Before 
> @@ -430,14 +448,16 @@ const bigadd = {a, b
>  	elif b.sign == 0
>  		-> a
>  	else
> -		match bigcmp(a, b)
> -		| `Before: /* a is negative */
> +		match bigcmpabs(a, b)
> +		| `Before: /* (1) + (-2) or (-1) + (2) */
>  			a.sign = b.sign
> -			-> usub(b, a)
> -		| `After: /* b is negative */
> +			var r = bigdup(b)
> +			usub(r, a)
> +			-> bigsteal(a, r)
> +		| `After: /* (2) + (-1) or (-2) + (1) */
>  			-> usub(a, b)
>  		| `Equal:
> -			die("Impossible. Equal vals with different sign.")
> +			-> bigclear(a)
>  		;;
>  	;;
>  }
> @@ -482,11 +502,13 @@ const bigsub = {a, b
>  	elif a.sign != b.sign
>  		-> uadd(a, b)
>  	else
> -		match bigcmp(a, b)
> -		| `Before: /* a is negative */
> -			a.sign = b.sign
> -			-> usub(b, a)
> -		| `After: /* b is negative */
> +		match bigcmpabs(a, b)
> +		| `Before: /* (-1) - (-2) or (1) - (2) */
> +			var r = bigdup(b)
> +			usub(r, a)
> +			r.sign = -1 * b.sign
> +			-> bigsteal(a, r)
> +		| `After: /* (-2) - (-1) or (2) - (1) */
>  			-> usub(a, b)
>  		| `Equal:
>  			-> bigclear(a)
> diff --git a/lib/std/test/bigint.myr b/lib/std/test/bigint.myr
> index d312ce41..2467143c 100644
> --- a/lib/std/test/bigint.myr
> +++ b/lib/std/test/bigint.myr
> @@ -16,10 +16,13 @@ type cmd = union
>  const main = {
>  	testr.run([
>  		[.name = "smoke-test", .fn = smoketest],
> +		[.name = "matches-small", .fn = matchsmall],
>  		[.name = "comparisons", .fn = comparisons],
>  		[.name = "format-zero", .fn = fmtzero],
>  		[.name = "division", .fn = smokediv],
>  		[.name = "modulo", .fn = smokemod],
> +		[.name = "add-negatives", .fn = addneg],
> +		[.name = "sub-negatives", .fn = subneg],
>  	][:])
>  }
>  
> @@ -49,6 +52,55 @@ const smoketest = {ct
>  	testr.check(ct, std.eq(buf[:n], "517347321949036993306"), "simple smoke test failed")
>  }
>  
> +const matchsmall = {c
> +	var nums = [ -5, -3, -2, -1, 0, 1, 2, 4, 8, 10 ][:]
> +	for a : nums
> +		for b : nums
> +			var p = std.mkbigint(a)
> +			var q = std.mkbigint(b)
> +
> +			var radd = std.mkbigint(a + b)
> +			var sadd = std.bigdup(p)
> +			std.bigadd(sadd, q)
> +			testr.check(c, std.bigeq(radd, sadd), "{} + {} != {} (was {})", a, b, a + b, sadd)
> +
> +			var rsub = std.mkbigint(a - b)
> +			var ssub = std.bigdup(p)
> +			std.bigsub(ssub, q)
> +			testr.check(c, std.bigeq(rsub, ssub), "{} - {} != {} (was {})", a, b, a - b, ssub)
> +
> +			var rmul = std.mkbigint(a * b)
> +			var smul = std.bigdup(p)
> +			std.bigmul(smul, q)
> +			testr.check(c, std.bigeq(rmul, smul), "{} * {} != {} (was {})", a, b, a * b, smul)
> +
> +
> +			if b != 0
> +				if a > 0 && b > 0
> +					var rmod = std.mkbigint(a % b)
> +					var smod = std.bigdup(p)
> +					std.bigmod(smod, q)
> +					testr.check(c, std.bigeq(rmod, smod), "{} % {} != {} (was {})", a, b, a % b, smod)
> +					std.bigfree(rmod)
> +				;;
> +
> +				var rdiv = std.mkbigint(a / b)
> +				var sdiv = std.bigdup(p)
> +				std.bigdiv(sdiv, q)
> +				testr.check(c, std.bigeq(rdiv, sdiv), "{} / {} != {} (was {})", a, b, a / b, sdiv)
> +
> +				std.bigfree(rdiv)
> +			;;
> +
> +			std.bigfree(p)
> +			std.bigfree(q)
> +			std.bigfree(radd)
> +			std.bigfree(rsub)
> +			std.bigfree(rmul)
> +		;;
> +	;;
> +}
> +
>  const comparisons = {c
>  	/* some comparison tests */
>  	var a = try(std.bigparse("1234_5678_1234_6789_6666_7777_8888"))
> @@ -122,7 +174,90 @@ const smokemod = {c
>  		std.mk(`Val "755578"), \
>  		std.mk(`Val "75557863709417659441940"))), \
>  		"27076504425474791131220")
> +}
> +
> +const addneg = {c
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "-1"), \
> +		std.mk(`Val "1"))), \
> +		"0")
> +
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "4"), \
> +		std.mk(`Val "-2"))), \
> +		"2")
> +
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "3"), \
> +		std.mk(`Val "-6"))), \
> +		"-3")
>  
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "-4"), \
> +		std.mk(`Val "8"))), \
> +		"4")
> +
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "-10"), \
> +		std.mk(`Val "5"))), \
> +		"-5")
> +
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "-6"), \
> +		std.mk(`Val "-12"))), \
> +		"-18")
> +
> +	run(c, std.mk(`Add (\
> +		std.mk(`Val "7"), \
> +		std.mk(`Val "-7"))), \
> +		"0")
> +}
> +
> +const subneg = {c
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-1"), \
> +		std.mk(`Val "1"))), \
> +		"-2")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "1"), \
> +		std.mk(`Val "-1"))), \
> +		"2")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "4"), \
> +		std.mk(`Val "-2"))), \
> +		"6")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "3"), \
> +		std.mk(`Val "-6"))), \
> +		"9")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-4"), \
> +		std.mk(`Val "8"))), \
> +		"-12")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-10"), \
> +		std.mk(`Val "5"))), \
> +		"-15")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-6"), \
> +		std.mk(`Val "-12"))), \
> +		"6")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-14"), \
> +		std.mk(`Val "-7"))), \
> +		"-7")
> +
> +	run(c, std.mk(`Sub (\
> +		std.mk(`Val "-8"), \
> +		std.mk(`Val "-8"))), \
> +		"0")
>  }
>  
>  const run = {c : testr.ctx#, e : cmd#, res : byte[:]
> -- 
> 2.20.1
> 
> 


-- 
Ori Bernstein <ori@xxxxxxxxxxxxxx>