ref: bf9480715e20b52f96625603cca8b0b3abbd6317
parent: 2c27f80bb5f4d8084f1d8cf9d01c4377dba92c2f
author: Ori Bernstein <[email protected]>
date: Mon Sep 15 18:45:50 EDT 2014
Add comparison functionality to bigint.
--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -33,6 +33,8 @@
/* 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 @@
*/
;;
+
const Base = 0x100000000ul
generic mkbigint = {v : @a::(integral,numeric)@@ -117,13 +120,13 @@
}
/* for now, just dump out something for debugging... */
-const bigbfmt = {buf, val, base+const bigbfmt = {buf, x, baseconst 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 @@
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 @@
;;
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 @@
-> 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, bvar i
@@ -560,16 +587,16 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 */
@@ -674,6 +679,23 @@
carry = t << (32 - shift)
;;
-> 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 */