shithub: mc

Download patch

ref: 38a875c05a009fdd298e7a93086654c8b78b2f63
parent: 961b64f18bcd6f6280a79638fd0634ff915cc4aa
author: Ori Bernstein <ori@eigenstate.org>
date: Wed Feb 4 19:21:59 EST 2015 

Add more stdbigint test cases.


--- a/libstd/bigint.myr
+++ b/libstd/bigint.myr
@@ -63,9 +63,6 @@
 	*/
 ;;
 
-/* DEBUG */
-extern const put : (fmt : byte[:], ap : ... -> void)
-
 const Base = 0x100000000ul
 
 generic mkbigint = {v : @a::(integral,numeric)
@@ -99,14 +96,14 @@
 
 const bigassign = {d, s
 	slfree(d.dig)
+	d# = s#
 	d.dig = sldup(s.dig)
-	d.sign = s.sign
 	-> d
 }
 
 const bigmove = {d, s
 	slfree(d.dig)
-	d.dig = s.dig
+	d# = s#
 	s.dig = [][:]
 	s.sign = 0
 	-> d
@@ -145,7 +142,13 @@
 
 	if base < 0 || base > 36
 		die("invalid base in bigbfmt\n")
-	elif base == 0
+	;;
+
+	if bigiszero(x)
+		n
+	;;
+
+	if base == 0
 		b = mkbigint(10)
 	else
 		b = mkbigint(base)
@@ -445,11 +448,11 @@
 	 Implements bigint division using Algorithm D from
 	 Knuth: Seminumerical algorithms, Section 4.3.1.
 	 */
+	var m : int64, n : int64
 	var qhat, rhat, carry, shift
 	var x, y, z, w, p, t /* temporaries */
 	var b0, aj
 	var u, v
-	var m : int64, n : int64
 	var i, j : int64
 	var q
 
@@ -537,17 +540,18 @@
 
 	;;
 	/* undo the biasing for remainder */
-	bigshri(u, shift)
+	u = bigshri(u, shift)
 	-> (trim(q), trim(u))
 }
 
 /* computes b^e % m */
 const bigmodpow = {base, exp, mod
-	var r
+	var r, n
 
 	r = mkbigint(1)
+	n = 0
     	while !bigiszero(exp)
-		if exp.dig[0] & 1 == 0
+		if exp.dig[0] & 1 != 0
 			bigmul(r, base)
 			bigmod(r, mod)
 		;;
--- a/test/data/stdbigint-expected
+++ b/test/data/stdbigint-expected
@@ -1,4 +1,9 @@
 517347321949036993306
+0 == 0
 1234567812346789666677778888 / 123456781234678966667777 == 10000
 1208908684563961789813300 / 263951815549716 == 4580035496
 5192296858534810493479828944327220 / 75557863709417659441940 == 68719476751
+75557863709417659441940 / 5192296858534810493479828944327220 == 0
+5192296858534810493479828944327220 % 75557863709417659441940 == 257025710597479990280
+(1 ^ 3) % 2 == 1
+(5192296858534810493479828944327220 ^ 75557863709417659441940) % 755578 == 49054
--- a/test/stdbigint.myr
+++ b/test/stdbigint.myr
@@ -15,8 +15,9 @@
 
 const main = {
 	var a, b, c, d, e
-	var buf : byte[4096], n
+	var buf : byte[64], n
 
+	/* a few combined ops */
 	a = std.mkbigint(1234)
 	b = std.mkbigint(0x7fffffff)
 	c = std.mkbigint(7919)
@@ -37,6 +38,8 @@
 	n = std.bigbfmt(buf[:], a, 0)
 	std.put("%s\n", buf[:n])
 
+	/* make sure we format '0' correctly */
+	run(std.mk(`Res (std.mk(`Val "0"))))
 	/* smoke test for division */
 	run(std.mk(`Res \
 			std.mk(`Div (\
@@ -50,11 +53,42 @@
 		std.mk(`Div (\
 			std.mk(`Val "5192296858534810493479828944327220"), \
 			std.mk(`Val "75557863709417659441940")))))
+	run(std.mk(`Res \
+		std.mk(`Div (\
+			std.mk(`Val "75557863709417659441940"), \
+			std.mk(`Val "5192296858534810493479828944327220")))))
+
+	/* smoke test for mod */
+	run(std.mk(`Res \
+		std.mk(`Mod (\
+			std.mk(`Val "5192296858534810493479828944327220"), \
+			std.mk(`Val "75557863709417659441940")))))
+
+	run(std.mk(`Res \
+		std.mk(`Modpow (\
+			std.mk(`Val "1"), \
+			std.mk(`Val "3"), \
+			std.mk(`Val "2")))))
+
+	run(std.mk(`Res \
+		std.mk(`Modpow (\
+			std.mk(`Val "5192296858534810493479828944327220"), \
+			std.mk(`Val "75557863709417659441940"), \
+			std.mk(`Val "755578")))))
+	/* BOTCHED
+	run(std.mk(`Res \
+		std.mk(`Modpow (\
+			std.mk(`Val "5192296858534810493479828944327220"), \
+			std.mk(`Val "755578"), \
+			std.mk(`Val "75557863709417659441940")))))
+	*/
+
 }
 
 const run = {e : cmd#
-	var buf : byte[4096]
-	var v, n
+	var buf : byte[2048]
+	var a, b, c	/* scratch vars */
+	var n		/* buf len */
 
 	match e#
 	| `Add (x, y):	-> binop("+", std.bigadd, x, y)
@@ -65,17 +99,23 @@
 	| `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)
+		a = try(std.bigparse(x))
+		n = std.bigbfmt(buf[:], a, 0)
 		std.put("%s", buf[:n])
-		-> v
+		-> a
 	| `Res r:
-		v = run(r)
-		n = std.bigbfmt(buf[:], v, 0)
+		a = run(r)
+		n = std.bigbfmt(buf[:], a, 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])
+		-> a
+	| `Modpow (x, y, z):
+		std.put("("); 
+		a = run(x)
+		std.put(" ^ ")
+		b = run(y)
+		std.put(") %% ")
+		c = run(z)
+		-> std.bigmodpow(a, b, c)
 	;;
 }