shithub: mc

Download patch

ref: 94eff65320912b8192b353d74413db461c19f16a
parent: 063b2a4e134589a8a1d635708eb0eb39d5a76bfb
author: Ori Bernstein <ori@eigenstate.org>
date: Wed Feb 4 17:24:02 EST 2015 

Clean up bigint division and tests.


--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -23,6 +23,7 @@
 	const bigfree	: (a : bigint# -> void)
 	const bigdup	: (a : bigint# -> bigint#)
 	const bigassign	: (d : bigint#, s : bigint# -> bigint#)
+	const bigmove	: (d : bigint#, s : bigint# -> bigint#)
 	const bigparse	: (s : byte[:] -> option(bigint#))
 	const bigbfmt	: (b : byte[:], a : bigint#, base : int -> size)
 	const bigfmt	: (a : bigint#, base : int -> byte[:])
@@ -45,6 +46,7 @@
 	const bigdivmod	: (a : bigint#, b : bigint# -> (bigint#, bigint#))
 	const bigshl	: (a : bigint#, b : bigint# -> bigint#)
 	const bigshr	: (a : bigint#, b : bigint# -> bigint#)
+	const bigmodpow	: (b : bigint#, e : bigint#, m : bigint# -> bigint#)
 	/*
 	const bigpow	: (a : bigint#, b : bigint# -> bigint#)
 	*/
@@ -61,6 +63,8 @@
 	*/
 ;;
 
+/* DEBUG */
+extern const put : (fmt : byte[:], ap : ... -> void)
 
 const Base = 0x100000000ul
 
@@ -100,6 +104,15 @@
 	-> d
 }
 
+const bigmove = {d, s
+	slfree(d.dig)
+	d.dig = s.dig
+	s.dig = [][:]
+	s.sign = 0
+	-> d
+}
+
+
 const bigfmt = {a, base
 	var buf
 	var n
@@ -416,11 +429,7 @@
 
 	(q, r) = bigdivmod(a, b)
 	bigfree(r)
-	slfree(a.dig)
-	a.dig = q.dig
-	a.sign = q.sign
-	free(q)
-	-> a
+	-> bigmove(a, q)
 }
 const bigmod = {a : bigint#, b : bigint# -> bigint#
 	var q, r
@@ -427,11 +436,7 @@
 
 	(q, r) = bigdivmod(a, b)
 	bigfree(q)
-	slfree(a.dig)
-	a.dig = r.dig
-	a.sign = r.sign
-	free(r)
-	-> a
+	-> bigmove(a, r)
 }
 
 /* a /= b */
@@ -534,6 +539,23 @@
 	/* undo the biasing for remainder */
 	bigshri(u, shift)
 	-> (trim(q), trim(u))
+}
+
+/* computes b^e % m */
+const bigmodpow = {base, exp, mod
+	var r
+
+	r = mkbigint(1)
+    	while !bigiszero(exp)
+		if exp.dig[0] & 1 == 0
+			bigmul(r, base)
+			bigmod(r, mod)
+		;;
+		bigshri(exp, 1)
+		bigmul(base, base)
+		bigmod(base, mod)
+	;;
+	-> bigmove(base, r)
 }
 
 /* returns the number of leading zeros */
--- a/test/stdbigint.myr
+++ b/test/stdbigint.myr
@@ -1,5 +1,18 @@
 use std
 
+type cmd = union
+	`Add (cmd#, cmd#)
+	`Sub (cmd#, cmd#)
+	`Mul (cmd#, cmd#)
+	`Div (cmd#, cmd#)
+	`Mod (cmd#, cmd#)
+	`Shl (cmd#, cmd#)
+	`Shr (cmd#, cmd#)
+	`Modpow (cmd#, cmd#, cmd#)
+	`Val byte[:]
+	`Res cmd#
+;;
+
 const main = {
 	var a, b, c, d, e
 	var buf : byte[4096], n
@@ -24,63 +37,80 @@
 	n = std.bigbfmt(buf[:], a, 0)
 	std.put("%s\n", buf[:n])
 
-	/* smoke test */
-	match std.bigparse("1234_5678_1234_6789_6666_7777_8888")
-	| `std.Some val: a = val
-	| `std.None: std.die("Failed to parse a\n")
-	;;
-	match std.bigparse("1234_5678_1234_6789_6666_7777")
-	| `std.Some val: b = val
-	| `std.None: std.die("Failed to parse b\n")
-	;;
+	/* smoke test for division */
+	run(std.mk(`Res \
+			std.mk(`Div (\
+				std.mk(`Val "1234_5678_1234_6789_6666_7777_8888"), \
+				std.mk(`Val "1234_5678_1234_6789_6666_7777")))))
+	run(std.mk(`Res \
+		std.mk(`Div (\
+			std.mk(`Val "0xffff_1234_1234_1234_1234"), \
+			std.mk(`Val "0xf010_1234_2314")))))
+	run(std.mk(`Res \
+		std.mk(`Div (\
+			std.mk(`Val "5192296858534810493479828944327220"), \
+			std.mk(`Val "75557863709417659441940")))))
 
-	n = std.bigbfmt(buf[:], a, 0)
-	std.put("%s / ", buf[:n])
-	n = std.bigbfmt(buf[:], b, 0)
-	std.put("%s == ", buf[:n])
+	/*
+	a = try(std.bigparse("2988348162058574136915891421498819466320163312926952423791023078876139"))
+	b = try(std.bigparse("2351399303373464486466122544523690094744975233415544072992656881240319"))
+	c = try(std.bigparse("10000000000000000000000000000000000000000"))
 
-	std.bigdiv(a, b)
-
 	n = std.bigbfmt(buf[:], a, 0)
-	std.put("%s\n", buf[:n])
-
-	match std.bigparse("0xffff_1234_1234_1234_1234")
-	| `std.Some val: a = val
-	n = std.bigbfmt(buf[:], a, 0)
-	| `std.None: std.die("Failed to parse a\n")
-	;;
-	match std.bigparse("0xf010_1234_2314")
-	| `std.Some val: b = val
-	| `std.None: std.die("Failed to parse b\n")
-	;;
-
-	n = std.bigbfmt(buf[:], a, 0)
-	std.put("%s / ", buf[:n])
+	std.put("%s ^ ", buf[:n])
 	n = std.bigbfmt(buf[:], b, 0)
+	std.put("%s %% ", buf[:n])
+	n = std.bigbfmt(buf[:], c, 0)
 	std.put("%s == ", buf[:n])
 
-	std.bigdiv(a, b)
+	std.bigmodpow(a, b, c)
 
 	n = std.bigbfmt(buf[:], a, 0)
 	std.put("%s\n", buf[:n])
+	*/
+}
 
-	match std.bigparse("5192296858534810493479828944327220")
-	| `std.Some val: a = val
-	n = std.bigbfmt(buf[:], a, 0)
-	| `std.None: std.die("Failed to parse a\n")
+const run = {e : cmd#
+	var buf : byte[4096]
+	var v, n
+
+	match e#
+	| `Add (x, y):	-> binop("+", std.bigadd, x, y)
+	| `Sub (x, y):	-> binop("-", std.bigsub, x, y)
+	| `Mul (x, y):	-> binop("*", std.bigmul, x, y)
+	| `Div (x, y):	-> binop("/", std.bigdiv, x, y)
+	| `Mod (x, y):	-> binop("%", std.bigmod, x, y)
+	| `Shl (x, y):	-> binop("<<", std.bigshl, x, y)
+	| `Shr (x, y):	-> binop(">>", std.bigshr, x, y)
+	| `Val x:
+		v = try(std.bigparse(x))
+		n = std.bigbfmt(buf[:], v, 0)
+		std.put("%s", buf[:n])
+		-> v
+	| `Res r:
+		v = run(r)
+		n = std.bigbfmt(buf[:], v, 0)
+		std.put(" == %s\n", buf[:n])
+	| `Modpow (x, y, m):
+		n = std.bigbfmt(buf[:], std.bigmodpow(run(x), run(y), run(m)), 0)
+		std.put("(%s ^ %s) % %s = %s\n", x, y, m, buf[:n])
 	;;
-	match std.bigparse("75557863709417659441940")
-	| `std.Some val: b = val
-	| `std.None: std.die("Failed to parse b\n")
-	;;
+}
 
-	n = std.bigbfmt(buf[:], a, 0)
-	std.put("%s / ", buf[:n])
-	n = std.bigbfmt(buf[:], b, 0)
-	std.put("%s == ", buf[:n])
+const binop = {name, op, x, y
+	var a, b
 
-	std.bigdiv(a, b)
+	a = run(x)
+	std.put(" %s ", name)
+	b = run(y)
+	op(a, b)
+	std.bigfree(b)
+	-> a
+}
 
-	n = std.bigbfmt(buf[:], a, 0)
-	std.put("%s\n", buf[:n])
+generic try = {x : std.option(@a)
+	match x
+	| `std.Some v:	-> v
+	| `std.None:	std.die("failed to get val")
+	;;
 }