summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorS. Gilles <sgilles@math.umd.edu>2019-10-24 09:33:29 -0400
committerOri Bernstein <ori@eigenstate.org>2019-10-24 08:17:21 -0700
commite9b59bee4efb648e323dfb6269209b59c575806f (patch)
treee53b8761181d2715b6aca5eb15156a26f39c29ec /lib
parent076f4d371d887d25c3ac3851589f161131f57c88 (diff)
downloadmc-e9b59bee4efb648e323dfb6269209b59c575806f.tar.gz
Allow bigdivmod to return remainders between 2^31 and 2^32
Diffstat (limited to 'lib')
-rw-r--r--lib/std/bigint.myr2
-rw-r--r--lib/std/test/bigint.myr46
2 files changed, 47 insertions, 1 deletions
diff --git a/lib/std/bigint.myr b/lib/std/bigint.myr
index 3f169a8..9213007 100644
--- a/lib/std/bigint.myr
+++ b/lib/std/bigint.myr
@@ -702,7 +702,7 @@ const bigdivmod = {a : bigint#, b : bigint# -> (bigint#, bigint#)
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 --git a/lib/std/test/bigint.myr b/lib/std/test/bigint.myr
index c87f1f3..d50b0ff 100644
--- a/lib/std/test/bigint.myr
+++ b/lib/std/test/bigint.myr
@@ -23,6 +23,7 @@ const main = {
[.name = "modulo", .fn = smokemod],
[.name = "add-negatives", .fn = addneg],
[.name = "sub-negatives", .fn = subneg],
+ [.name = "bigdivmod", .fn = somebigdivmod],
][:])
}
@@ -314,3 +315,48 @@ generic try = {x : std.option(@a)
| `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)
+ ;;
+}