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);;
}