summaryrefslogtreecommitdiff
path: root/libstd/bigint.myr
diff options
context:
space:
mode:
authorOri Bernstein <ori@eigenstate.org>2014-09-15 22:45:50 -0400
committerOri Bernstein <ori@eigenstate.org>2014-09-15 22:47:01 -0400
commit83b338addfe2942fe18283be01064fc169214961 (patch)
tree30a83116110b1eb28c568ce6016119ba613a3104 /libstd/bigint.myr
parentdd97266db3c7c7a663c3654dbc843242b8cb7b80 (diff)
downloadmc-83b338addfe2942fe18283be01064fc169214961.tar.gz
Add comparison functionality to bigint.
Diffstat (limited to 'libstd/bigint.myr')
-rw-r--r--libstd/bigint.myr100
1 files changed, 61 insertions, 39 deletions
diff --git a/libstd/bigint.myr b/libstd/bigint.myr
index 53f34b6..19c1c9e 100644
--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -33,6 +33,8 @@ pkg std =
/* some useful predicates */
const bigiszero : (a : bigint# -> bool)
+ const bigeq : (a : bigint#, b : bigint# -> bool)
+ generic bigeqi : (a : bigint#, b : @a::(numeric,integral) -> bool)
const bigcmp : (a : bigint#, b : bigint# -> order)
/* bigint*bigint -> bigint ops */
@@ -60,6 +62,7 @@ pkg std =
*/
;;
+
const Base = 0x100000000ul
generic mkbigint = {v : @a::(integral,numeric)
@@ -117,13 +120,13 @@ const bigfmt = {a, base
}
/* for now, just dump out something for debugging... */
-const bigbfmt = {buf, val, base
+const bigbfmt = {buf, x, base
const digitchars = [
'0','1','2','3','4','5','6','7','8','9',
'a','b','c','d','e','f', 'g', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
't', 'u', 'v', 'w', 'x', 'y', 'z']
- var v
+ var v, val
var n, i
var tmp, rem, b
@@ -135,13 +138,7 @@ const bigbfmt = {buf, val, base
b = mkbigint(base)
;;
n = 0
- if val.sign == 0
- n += encode(buf, '0')
- elif val.sign == -1
- n += encode(buf, '-')
- ;;
-
- val = bigdup(val)
+ val = bigdup(x)
/* generate the digits in reverse order */
while !bigiszero(val)
(v, rem) = bigdivmod(val, b)
@@ -156,6 +153,14 @@ const bigbfmt = {buf, val, base
;;
bigfree(val)
bigfree(b)
+
+ /* this is done last, so we get things right when we reverse the string */
+ if x.sign == 0
+ n += encode(buf[n:], '0')
+ elif x.sign == -1
+ n += encode(buf[n:], '-')
+ ;;
+
/* we only generated ascii digits, so this works for reversing. */
for i = 0; i < n/2; i++
tmp = buf[i]
@@ -220,6 +225,28 @@ const bigiszero = {v
-> v.dig.len == 0
}
+const bigeq = {a, b
+ var i
+
+ if a.sign != b.sign || a.dig.len != b.dig.len
+ -> false
+ ;;
+ for i = 0; i < a.dig.len; i++
+ if a.dig[i] != b.dig[i]
+ -> false
+ ;;
+ ;;
+ -> true
+}
+
+generic bigeqi = {a, b
+ var v
+ var dig : uint32[2]
+
+ bigdigit(&v, b < 0, b castto(uint64), dig[:])
+ -> bigeq(a, &v)
+}
+
const bigcmp = {a, b
var i
@@ -560,16 +587,16 @@ generic bigaddi = {a, b
var bigb : bigint
var dig : uint32[2]
- bigdigit(&bigb, b castto(int64), dig[:])
+ bigdigit(&bigb, b < 0, b castto(uint64), dig[:])
bigadd(a, &bigb)
-> a
}
-generic bigsubi = {a, b
+generic bigsubi = {a, b : @a::(numeric,integral)
var bigb : bigint
var dig : uint32[2]
- bigdigit(&bigb, b castto(int64), dig[:])
+ bigdigit(&bigb, b < 0, b castto(uint64), dig[:])
bigsub(a, &bigb)
-> a
}
@@ -578,7 +605,7 @@ generic bigmuli = {a, b
var bigb : bigint
var dig : uint32[2]
- bigdigit(&bigb, b castto(int64), dig[:])
+ bigdigit(&bigb, b < 0, b castto(uint64), dig[:])
bigmul(a, &bigb)
-> a
}
@@ -587,35 +614,11 @@ generic bigdivi = {a, b
var bigb : bigint
var dig : uint32[2]
- bigdigit(&bigb, b castto(int64), dig[:])
+ bigdigit(&bigb, b < 0, b castto(uint64), dig[:])
bigdiv(a, &bigb)
-> a
}
-const bigdigit = {v : bigint#, sval, dig
- var val
-
- if sval == 0
- v.sign = 0
- elif sval < 0
- v.sign = -1
- val = (-sval) castto(uint64)
- else
- v.sign = 1
- val = sval castto(uint64)
- ;;
- if val == 0
- v.dig = [][:]
- elif val > Base
- v.dig = dig[:1]
- v.dig[0] = val castto(uint32)
- else
- v.dig = dig
- v.dig[0] = val castto(uint32)
- v.dig[1] = (val >> 32) castto(uint32)
- ;;
-}
-
/*
a << s, with integer arg.
logical left shift. any other type would be illogical.
@@ -625,6 +628,7 @@ generic bigshli = {a, s : @a::(numeric,integral)
var t, carry
var i
+ assert(s >= 0, "shift amount must be positive")
off = (s castto(uint64)) / 32
shift = (s castto(uint64)) % 32
@@ -656,6 +660,7 @@ generic bigshri = {a, s
var t, carry
var i
+ assert(s >= 0, "shift amount must be positive")
off = (s castto(uint64)) / 32
shift = (s castto(uint64)) % 32
@@ -663,7 +668,7 @@ generic bigshri = {a, s
for i = 0; i < a.dig.len - off; i++
a.dig[i] = a.dig[i + off]
;;
- for i = a.dig.len; i < a.dig.len + off; i++
+ for i = a.dig.len - off; i < a.dig.len; i++
a.dig[i] = 0
;;
/* and shift over by the remainder */
@@ -676,6 +681,23 @@ generic bigshri = {a, s
-> trim(a)
}
+/* creates a bigint on the stack; should not be modified. */
+const bigdigit = {v, isneg : bool, val : uint64, dig
+ if isneg
+ val = -val
+ ;;
+ if val == 0
+ v.dig = [][:]
+ elif val > Base
+ v.dig = dig[:1]
+ v.dig[0] = val castto(uint32)
+ else
+ v.dig = dig
+ v.dig[0] = val castto(uint32)
+ v.dig[1] = (val >> 32) castto(uint32)
+ ;;
+}
+
/* trims leading zeros */
const trim = {a
var i