summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorS. Gilles <sgilles@math.umd.edu>2019-02-19 08:19:09 -0500
committerOri Bernstein <ori@markovcorp.com>2019-02-19 13:26:17 -0800
commit16a7bb8f8cc86b22ce157e0944f66f60a556590f (patch)
tree3fdc20763fd9b92082d9355eda679e24e539375a /lib
parent36f4100dcea54700c0441a4667f601bcb5b1c59e (diff)
downloadmc-16a7bb8f8cc86b22ce157e0944f66f60a556590f.tar.gz
Handle (-1) + (1) and (-3) - (-2) with bigints
Diffstat (limited to 'lib')
-rw-r--r--lib/std/bigint.myr42
-rw-r--r--lib/std/test/bigint.myr135
2 files changed, 167 insertions, 10 deletions
diff --git a/lib/std/bigint.myr b/lib/std/bigint.myr
index c13f0df..7b0f4bc 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 d312ce4..2467143 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[:]