shithub: mc

Download patch

ref: e9b59bee4efb648e323dfb6269209b59c575806f
parent: 076f4d371d887d25c3ac3851589f161131f57c88
author: S. Gilles <sgilles@math.umd.edu>
date: Thu Oct 24 05:33:29 EDT 2019

Allow bigdivmod to return remainders between 2^31 and 2^32

diff -u a/lib/std/bigint.myr b/lib/std/bigint.myr
--- a/lib/std/bigint.myr
+++ b/lib/std/bigint.myr
@@ -702,7 +702,7 @@
 			carry = (carry << 32) + aj - (q.dig[j-1] : uint64)*b0
 		;;
 		q = trim(q)
-		-> (q, trim(mkbigint((carry : int32))))
+		-> (q, trim(mkbigint(carry)))
 	;;
 
 	u = bigdup(a)
diff -u a/lib/std/test/bigint.myr b/lib/std/test/bigint.myr
--- a/lib/std/test/bigint.myr
+++ b/lib/std/test/bigint.myr
@@ -23,6 +23,7 @@
 		[.name = "modulo", .fn = smokemod],
 		[.name = "add-negatives", .fn = addneg],
 		[.name = "sub-negatives", .fn = subneg],
+		[.name = "bigdivmod", .fn = somebigdivmod],
 	][:])
 }
 
@@ -312,5 +313,50 @@
 	match x
 	| `std.Some v:	-> v
 	| `std.None:	std.die("failed to get val")
+	;;
+}
+
+const somebigdivmod = {c
+	var inputs : (byte[:], byte[:], byte[:], byte[:])[:] = [
+		/* ( a,  b,  a/b,  a%b),  */
+		("6185103187", 	"3519152458", 	"1", 	"2665950729"),
+		("6980766832", 	"3087864937", 	"2", 	"805036958"),
+		("4991855479", 	"6447381549", 	"0", 	"4991855479"),
+		("6119892968", 	"8374603717", 	"0", 	"6119892968"),
+		("7442542736", 	"5989044918", 	"1", 	"1453497818"),
+		("4580939187", 	"4661174670", 	"0", 	"4580939187"),
+		("4935237814", 	"3140079933", 	"1", 	"1795157881"),
+		("1010425087", 	"446887574", 	"2", 	"116649939"),
+		("1892124804", 	"4011235814", 	"0", 	"1892124804"),
+		("2457899196", 	"1885658848", 	"1", 	"572240348"),
+		("262030672", 	"1329267171", 	"0", 	"262030672"),
+		("8430016289", 	"6215302855", 	"1", 	"2214713434"),
+		("3347587073", 	"3855445301", 	"0", 	"3347587073"),
+		("8014059310", 	"4622364950", 	"1", 	"3391694360"),
+		("2934470708", 	"6439081239", 	"0", 	"2934470708"),
+		("420917856", 	"5020252044", 	"0", 	"420917856"),
+		("3862040257", 	"4601227994", 	"0", 	"3862040257"),
+		("4439858911", 	"4387180962", 	"1", 	"52677949"),
+		("165706876", 	"7452574618", 	"0", 	"165706876"),
+		("268686047", 	"3047271875", 	"0", 	"268686047"),
+		("83484791", 	"4899367309", 	"0", 	"83484791"),
+		("1242378916", 	"4909326080", 	"0", 	"1242378916"),
+		("980437482", 	"2305509838", 	"0", 	"980437482"),
+		("118982655", 	"5051748984", 	"0", 	"118982655"),
+		("8521162809", 	"2888108066", 	"2", 	"2744946677"),
+		("4600797553", 	"7579789288", 	"0", 	"4600797553"),
+		("5533774720", 	"3320264831", 	"1", 	"2213509889"),
+	][:]
+
+	for (aS, bS, qS, rS) : inputs
+		var a     = try(std.bigparse(aS))
+		var b     = try(std.bigparse(bS))
+		var q_exp = try(std.bigparse(qS))
+		var r_exp = try(std.bigparse(rS))
+
+		var q_act, r_act
+		(q_act, r_act) = std.bigdivmod(a, b)
+		testr.check(c, std.bigeq(q_exp, q_act), "expected {} / {} to be {}, was {}", a, b, q_exp, q_act)
+		testr.check(c, std.bigeq(r_exp, r_act), "expected {} % {} to be {}, was {}", a, b, r_exp, r_act)
 	;;
 }
--- a/lib/std/bigint.myr
+++ b/lib/std/bigint.myr
@@ -702,7 +702,7 @@
 			carry = (carry << 32) + aj - (q.dig[j-1] : uint64)*b0
 		;;
 		q = trim(q)
-		-> (q, trim(mkbigint((carry : int32))))
+		-> (q, trim(mkbigint(carry)))
 	;;
 
 	u = bigdup(a)
diff -u a/lib/std/test/bigint.myr b/lib/std/test/bigint.myr
--- a/lib/std/test/bigint.myr
+++ b/lib/std/test/bigint.myr
@@ -23,6 +23,7 @@
 		[.name = "modulo", .fn = smokemod],
 		[.name = "add-negatives", .fn = addneg],
 		[.name = "sub-negatives", .fn = subneg],
+		[.name = "bigdivmod", .fn = somebigdivmod],
 	][:])
 }
 
@@ -312,5 +313,50 @@
 	match x
 	| `std.Some v:	-> v
 	| `std.None:	std.die("failed to get val")
+	;;
+}
+
+const somebigdivmod = {c
+	var inputs : (byte[:], byte[:], byte[:], byte[:])[:] = [
+		/* ( a,  b,  a/b,  a%b),  */
+		("6185103187", 	"3519152458", 	"1", 	"2665950729"),
+		("6980766832", 	"3087864937", 	"2", 	"805036958"),
+		("4991855479", 	"6447381549", 	"0", 	"4991855479"),
+		("6119892968", 	"8374603717", 	"0", 	"6119892968"),
+		("7442542736", 	"5989044918", 	"1", 	"1453497818"),
+		("4580939187", 	"4661174670", 	"0", 	"4580939187"),
+		("4935237814", 	"3140079933", 	"1", 	"1795157881"),
+		("1010425087", 	"446887574", 	"2", 	"116649939"),
+		("1892124804", 	"4011235814", 	"0", 	"1892124804"),
+		("2457899196", 	"1885658848", 	"1", 	"572240348"),
+		("262030672", 	"1329267171", 	"0", 	"262030672"),
+		("8430016289", 	"6215302855", 	"1", 	"2214713434"),
+		("3347587073", 	"3855445301", 	"0", 	"3347587073"),
+		("8014059310", 	"4622364950", 	"1", 	"3391694360"),
+		("2934470708", 	"6439081239", 	"0", 	"2934470708"),
+		("420917856", 	"5020252044", 	"0", 	"420917856"),
+		("3862040257", 	"4601227994", 	"0", 	"3862040257"),
+		("4439858911", 	"4387180962", 	"1", 	"52677949"),
+		("165706876", 	"7452574618", 	"0", 	"165706876"),
+		("268686047", 	"3047271875", 	"0", 	"268686047"),
+		("83484791", 	"4899367309", 	"0", 	"83484791"),
+		("1242378916", 	"4909326080", 	"0", 	"1242378916"),
+		("980437482", 	"2305509838", 	"0", 	"980437482"),
+		("118982655", 	"5051748984", 	"0", 	"118982655"),
+		("8521162809", 	"2888108066", 	"2", 	"2744946677"),
+		("4600797553", 	"7579789288", 	"0", 	"4600797553"),
+		("5533774720", 	"3320264831", 	"1", 	"2213509889"),
+	][:]
+
+	for (aS, bS, qS, rS) : inputs
+		var a     = try(std.bigparse(aS))
+		var b     = try(std.bigparse(bS))
+		var q_exp = try(std.bigparse(qS))
+		var r_exp = try(std.bigparse(rS))
+
+		var q_act, r_act
+		(q_act, r_act) = std.bigdivmod(a, b)
+		testr.check(c, std.bigeq(q_exp, q_act), "expected {} / {} to be {}, was {}", a, b, q_exp, q_act)
+		testr.check(c, std.bigeq(r_exp, r_act), "expected {} % {} to be {}, was {}", a, b, r_exp, r_act)
 	;;
 }
--- a/lib/std/test/bigint.myr
+++ b/lib/std/test/bigint.myr
@@ -23,6 +23,7 @@
 		[.name = "modulo", .fn = smokemod],
 		[.name = "add-negatives", .fn = addneg],
 		[.name = "sub-negatives", .fn = subneg],
+		[.name = "bigdivmod", .fn = somebigdivmod],
 	][:])
 }
 
@@ -312,5 +313,50 @@
 	match x
 	| `std.Some v:	-> v
 	| `std.None:	std.die("failed to get val")
+	;;
+}
+
+const somebigdivmod = {c
+	var inputs : (byte[:], byte[:], byte[:], byte[:])[:] = [
+		/* ( a,  b,  a/b,  a%b),  */
+		("6185103187", 	"3519152458", 	"1", 	"2665950729"),
+		("6980766832", 	"3087864937", 	"2", 	"805036958"),
+		("4991855479", 	"6447381549", 	"0", 	"4991855479"),
+		("6119892968", 	"8374603717", 	"0", 	"6119892968"),
+		("7442542736", 	"5989044918", 	"1", 	"1453497818"),
+		("4580939187", 	"4661174670", 	"0", 	"4580939187"),
+		("4935237814", 	"3140079933", 	"1", 	"1795157881"),
+		("1010425087", 	"446887574", 	"2", 	"116649939"),
+		("1892124804", 	"4011235814", 	"0", 	"1892124804"),
+		("2457899196", 	"1885658848", 	"1", 	"572240348"),
+		("262030672", 	"1329267171", 	"0", 	"262030672"),
+		("8430016289", 	"6215302855", 	"1", 	"2214713434"),
+		("3347587073", 	"3855445301", 	"0", 	"3347587073"),
+		("8014059310", 	"4622364950", 	"1", 	"3391694360"),
+		("2934470708", 	"6439081239", 	"0", 	"2934470708"),
+		("420917856", 	"5020252044", 	"0", 	"420917856"),
+		("3862040257", 	"4601227994", 	"0", 	"3862040257"),
+		("4439858911", 	"4387180962", 	"1", 	"52677949"),
+		("165706876", 	"7452574618", 	"0", 	"165706876"),
+		("268686047", 	"3047271875", 	"0", 	"268686047"),
+		("83484791", 	"4899367309", 	"0", 	"83484791"),
+		("1242378916", 	"4909326080", 	"0", 	"1242378916"),
+		("980437482", 	"2305509838", 	"0", 	"980437482"),
+		("118982655", 	"5051748984", 	"0", 	"118982655"),
+		("8521162809", 	"2888108066", 	"2", 	"2744946677"),
+		("4600797553", 	"7579789288", 	"0", 	"4600797553"),
+		("5533774720", 	"3320264831", 	"1", 	"2213509889"),
+	][:]
+
+	for (aS, bS, qS, rS) : inputs
+		var a     = try(std.bigparse(aS))
+		var b     = try(std.bigparse(bS))
+		var q_exp = try(std.bigparse(qS))
+		var r_exp = try(std.bigparse(rS))
+
+		var q_act, r_act
+		(q_act, r_act) = std.bigdivmod(a, b)
+		testr.check(c, std.bigeq(q_exp, q_act), "expected {} / {} to be {}, was {}", a, b, q_exp, q_act)
+		testr.check(c, std.bigeq(r_exp, r_act), "expected {} % {} to be {}, was {}", a, b, r_exp, r_act)
 	;;
 }