shithub: mc

Download patch

ref: 16a7bb8f8cc86b22ce157e0944f66f60a556590f
parent: 36f4100dcea54700c0441a4667f601bcb5b1c59e
author: S. Gilles <sgilles@math.umd.edu>
date: Tue Feb 19 03:19:09 EST 2019 

Handle (-1) + (1) and (-3) - (-2) with bigints


--- a/lib/std/bigint.myr
+++ b/lib/std/bigint.myr
@@ -40,6 +40,7 @@
 	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 @@
 	-> `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 @@
 	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 @@
 	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)
--- a/lib/std/test/bigint.myr
+++ b/lib/std/test/bigint.myr
@@ -16,10 +16,13 @@
 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 @@
 	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 @@
 		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[:]