obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

11 files changed, 4713 insertions, 0 deletions

diff --git a/libgo/go/big/arith.go b/libgo/go/big/arith.go
new file mode 100644
index 000000000..a4048d6d7
--- /dev/null
+++ b/libgo/go/big/arith.go
@@ -0,0 +1,259 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file provides Go implementations of elementary multi-precision
+// arithmetic operations on word vectors. Needed for platforms without
+// assembly implementations of these routines.
+
+package big
+
+// TODO(gri) Decide if Word needs to remain exported.
+
+type Word uintptr
+
+const (
+	// Compute the size _S of a Word in bytes.
+	_m    = ^Word(0)
+	_logS = _m>>8&1 + _m>>16&1 + _m>>32&1
+	_S    = 1 << _logS
+
+	_W = _S << 3 // word size in bits
+	_B = 1 << _W // digit base
+	_M = _B - 1  // digit mask
+
+	_W2 = _W / 2   // half word size in bits
+	_B2 = 1 << _W2 // half digit base
+	_M2 = _B2 - 1  // half digit mask
+)
+
+
+// ----------------------------------------------------------------------------
+// Elementary operations on words
+//
+// These operations are used by the vector operations below.
+
+// z1<<_W + z0 = x+y+c, with c == 0 or 1
+func addWW_g(x, y, c Word) (z1, z0 Word) {
+	yc := y + c
+	z0 = x + yc
+	if z0 < x || yc < y {
+		z1 = 1
+	}
+	return
+}
+
+
+// z1<<_W + z0 = x-y-c, with c == 0 or 1
+func subWW_g(x, y, c Word) (z1, z0 Word) {
+	yc := y + c
+	z0 = x - yc
+	if z0 > x || yc < y {
+		z1 = 1
+	}
+	return
+}
+
+
+// z1<<_W + z0 = x*y
+func mulWW(x, y Word) (z1, z0 Word) { return mulWW_g(x, y) }
+// Adapted from Warren, Hacker's Delight, p. 132.
+func mulWW_g(x, y Word) (z1, z0 Word) {
+	x0 := x & _M2
+	x1 := x >> _W2
+	y0 := y & _M2
+	y1 := y >> _W2
+	w0 := x0 * y0
+	t := x1*y0 + w0>>_W2
+	w1 := t & _M2
+	w2 := t >> _W2
+	w1 += x0 * y1
+	z1 = x1*y1 + w2 + w1>>_W2
+	z0 = x * y
+	return
+}
+
+
+// z1<<_W + z0 = x*y + c
+func mulAddWWW_g(x, y, c Word) (z1, z0 Word) {
+	z1, zz0 := mulWW(x, y)
+	if z0 = zz0 + c; z0 < zz0 {
+		z1++
+	}
+	return
+}
+
+
+// Length of x in bits.
+func bitLen(x Word) (n int) {
+	for ; x >= 0x100; x >>= 8 {
+		n += 8
+	}
+	for ; x > 0; x >>= 1 {
+		n++
+	}
+	return
+}
+
+
+// log2 computes the integer binary logarithm of x.
+// The result is the integer n for which 2^n <= x < 2^(n+1).
+// If x == 0, the result is -1.
+func log2(x Word) int {
+	return bitLen(x) - 1
+}
+
+
+// Number of leading zeros in x.
+func leadingZeros(x Word) uint {
+	return uint(_W - bitLen(x))
+}
+
+
+// q = (u1<<_W + u0 - r)/y
+func divWW(x1, x0, y Word) (q, r Word) { return divWW_g(x1, x0, y) }
+// Adapted from Warren, Hacker's Delight, p. 152.
+func divWW_g(u1, u0, v Word) (q, r Word) {
+	if u1 >= v {
+		return 1<<_W - 1, 1<<_W - 1
+	}
+
+	s := leadingZeros(v)
+	v <<= s
+
+	vn1 := v >> _W2
+	vn0 := v & _M2
+	un32 := u1<<s | u0>>(_W-s)
+	un10 := u0 << s
+	un1 := un10 >> _W2
+	un0 := un10 & _M2
+	q1 := un32 / vn1
+	rhat := un32 - q1*vn1
+
+again1:
+	if q1 >= _B2 || q1*vn0 > _B2*rhat+un1 {
+		q1--
+		rhat += vn1
+		if rhat < _B2 {
+			goto again1
+		}
+	}
+
+	un21 := un32*_B2 + un1 - q1*v
+	q0 := un21 / vn1
+	rhat = un21 - q0*vn1
+
+again2:
+	if q0 >= _B2 || q0*vn0 > _B2*rhat+un0 {
+		q0--
+		rhat += vn1
+		if rhat < _B2 {
+			goto again2
+		}
+	}
+
+	return q1*_B2 + q0, (un21*_B2 + un0 - q0*v) >> s
+}
+
+
+func addVV(z, x, y []Word) (c Word) { return addVV_g(z, x, y) }
+func addVV_g(z, x, y []Word) (c Word) {
+	for i := range z {
+		c, z[i] = addWW_g(x[i], y[i], c)
+	}
+	return
+}
+
+
+func subVV(z, x, y []Word) (c Word) { return subVV_g(z, x, y) }
+func subVV_g(z, x, y []Word) (c Word) {
+	for i := range z {
+		c, z[i] = subWW_g(x[i], y[i], c)
+	}
+	return
+}
+
+
+func addVW(z, x []Word, y Word) (c Word) { return addVW_g(z, x, y) }
+func addVW_g(z, x []Word, y Word) (c Word) {
+	c = y
+	for i := range z {
+		c, z[i] = addWW_g(x[i], c, 0)
+	}
+	return
+}
+
+
+func subVW(z, x []Word, y Word) (c Word) { return subVW_g(z, x, y) }
+func subVW_g(z, x []Word, y Word) (c Word) {
+	c = y
+	for i := range z {
+		c, z[i] = subWW_g(x[i], c, 0)
+	}
+	return
+}
+
+
+func shlVW(z, x []Word, s Word) (c Word) { return shlVW_g(z, x, s) }
+func shlVW_g(z, x []Word, s Word) (c Word) {
+	if n := len(z); n > 0 {
+		ŝ := _W - s
+		w1 := x[n-1]
+		c = w1 >> ŝ
+		for i := n - 1; i > 0; i-- {
+			w := w1
+			w1 = x[i-1]
+			z[i] = w<<s | w1>>ŝ
+		}
+		z[0] = w1 << s
+	}
+	return
+}
+
+
+func shrVW(z, x []Word, s Word) (c Word) { return shrVW_g(z, x, s) }
+func shrVW_g(z, x []Word, s Word) (c Word) {
+	if n := len(z); n > 0 {
+		ŝ := _W - s
+		w1 := x[0]
+		c = w1 << ŝ
+		for i := 0; i < n-1; i++ {
+			w := w1
+			w1 = x[i+1]
+			z[i] = w>>s | w1<<ŝ
+		}
+		z[n-1] = w1 >> s
+	}
+	return
+}
+
+
+func mulAddVWW(z, x []Word, y, r Word) (c Word) { return mulAddVWW_g(z, x, y, r) }
+func mulAddVWW_g(z, x []Word, y, r Word) (c Word) {
+	c = r
+	for i := range z {
+		c, z[i] = mulAddWWW_g(x[i], y, c)
+	}
+	return
+}
+
+
+func addMulVVW(z, x []Word, y Word) (c Word) { return addMulVVW_g(z, x, y) }
+func addMulVVW_g(z, x []Word, y Word) (c Word) {
+	for i := range z {
+		z1, z0 := mulAddWWW_g(x[i], y, z[i])
+		c, z[i] = addWW_g(z0, c, 0)
+		c += z1
+	}
+	return
+}
+
+
+func divWVW(z []Word, xn Word, x []Word, y Word) (r Word) { return divWVW_g(z, xn, x, y) }
+func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word) {
+	r = xn
+	for i := len(z) - 1; i >= 0; i-- {
+		z[i], r = divWW_g(r, x[i], y)
+	}
+	return
+}
diff --git a/libgo/go/big/arith_decl.go b/libgo/go/big/arith_decl.go
new file mode 100644
index 000000000..c456d5f67
--- /dev/null
+++ b/libgo/go/big/arith_decl.go
@@ -0,0 +1,18 @@
+// Copyright 2010 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package big
+
+// implemented in arith_$GOARCH.s
+func mulWW(x, y Word) (z1, z0 Word)
+func divWW(x1, x0, y Word) (q, r Word)
+func addVV(z, x, y []Word) (c Word)
+func subVV(z, x, y []Word) (c Word)
+func addVW(z, x []Word, y Word) (c Word)
+func subVW(z, x []Word, y Word) (c Word)
+func shlVW(z, x []Word, s Word) (c Word)
+func shrVW(z, x []Word, s Word) (c Word)
+func mulAddVWW(z, x []Word, y, r Word) (c Word)
+func addMulVVW(z, x []Word, y Word) (c Word)
+func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
diff --git a/libgo/go/big/arith_test.go b/libgo/go/big/arith_test.go
new file mode 100644
index 000000000..934b302df
--- /dev/null
+++ b/libgo/go/big/arith_test.go
@@ -0,0 +1,342 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package big
+
+import "testing"
+
+
+type funWW func(x, y, c Word) (z1, z0 Word)
+type argWW struct {
+	x, y, c, z1, z0 Word
+}
+
+var sumWW = []argWW{
+	{0, 0, 0, 0, 0},
+	{0, 1, 0, 0, 1},
+	{0, 0, 1, 0, 1},
+	{0, 1, 1, 0, 2},
+	{12345, 67890, 0, 0, 80235},
+	{12345, 67890, 1, 0, 80236},
+	{_M, 1, 0, 1, 0},
+	{_M, 0, 1, 1, 0},
+	{_M, 1, 1, 1, 1},
+	{_M, _M, 0, 1, _M - 1},
+	{_M, _M, 1, 1, _M},
+}
+
+
+func testFunWW(t *testing.T, msg string, f funWW, a argWW) {
+	z1, z0 := f(a.x, a.y, a.c)
+	if z1 != a.z1 || z0 != a.z0 {
+		t.Errorf("%s%+v\n\tgot z1:z0 = %#x:%#x; want %#x:%#x", msg, a, z1, z0, a.z1, a.z0)
+	}
+}
+
+
+func TestFunWW(t *testing.T) {
+	for _, a := range sumWW {
+		arg := a
+		testFunWW(t, "addWW_g", addWW_g, arg)
+
+		arg = argWW{a.y, a.x, a.c, a.z1, a.z0}
+		testFunWW(t, "addWW_g symmetric", addWW_g, arg)
+
+		arg = argWW{a.z0, a.x, a.c, a.z1, a.y}
+		testFunWW(t, "subWW_g", subWW_g, arg)
+
+		arg = argWW{a.z0, a.y, a.c, a.z1, a.x}
+		testFunWW(t, "subWW_g symmetric", subWW_g, arg)
+	}
+}
+
+
+type funVV func(z, x, y []Word) (c Word)
+type argVV struct {
+	z, x, y nat
+	c       Word
+}
+
+var sumVV = []argVV{
+	{},
+	{nat{0}, nat{0}, nat{0}, 0},
+	{nat{1}, nat{1}, nat{0}, 0},
+	{nat{0}, nat{_M}, nat{1}, 1},
+	{nat{80235}, nat{12345}, nat{67890}, 0},
+	{nat{_M - 1}, nat{_M}, nat{_M}, 1},
+	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, nat{1, 0, 0, 0}, 1},
+	{nat{0, 0, 0, _M}, nat{_M, _M, _M, _M - 1}, nat{1, 0, 0, 0}, 0},
+	{nat{0, 0, 0, 0}, nat{_M, 0, _M, 0}, nat{1, _M, 0, _M}, 1},
+}
+
+
+func testFunVV(t *testing.T, msg string, f funVV, a argVV) {
+	z := make(nat, len(a.z))
+	c := f(z, a.x, a.y)
+	for i, zi := range z {
+		if zi != a.z[i] {
+			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
+			break
+		}
+	}
+	if c != a.c {
+		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
+	}
+}
+
+
+func TestFunVV(t *testing.T) {
+	for _, a := range sumVV {
+		arg := a
+		testFunVV(t, "addVV_g", addVV_g, arg)
+		testFunVV(t, "addVV", addVV, arg)
+
+		arg = argVV{a.z, a.y, a.x, a.c}
+		testFunVV(t, "addVV_g symmetric", addVV_g, arg)
+		testFunVV(t, "addVV symmetric", addVV, arg)
+
+		arg = argVV{a.x, a.z, a.y, a.c}
+		testFunVV(t, "subVV_g", subVV_g, arg)
+		testFunVV(t, "subVV", subVV, arg)
+
+		arg = argVV{a.y, a.z, a.x, a.c}
+		testFunVV(t, "subVV_g symmetric", subVV_g, arg)
+		testFunVV(t, "subVV symmetric", subVV, arg)
+	}
+}
+
+
+type funVW func(z, x []Word, y Word) (c Word)
+type argVW struct {
+	z, x nat
+	y    Word
+	c    Word
+}
+
+var sumVW = []argVW{
+	{},
+	{nil, nil, 2, 2},
+	{nat{0}, nat{0}, 0, 0},
+	{nat{1}, nat{0}, 1, 0},
+	{nat{1}, nat{1}, 0, 0},
+	{nat{0}, nat{_M}, 1, 1},
+	{nat{0, 0, 0, 0}, nat{_M, _M, _M, _M}, 1, 1},
+}
+
+var prodVW = []argVW{
+	{},
+	{nat{0}, nat{0}, 0, 0},
+	{nat{0}, nat{_M}, 0, 0},
+	{nat{0}, nat{0}, _M, 0},
+	{nat{1}, nat{1}, 1, 0},
+	{nat{22793}, nat{991}, 23, 0},
+	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0},
+	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0},
+	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0},
+	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, _M >> (_W - 1)},
+	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, _M >> (_W - 7)},
+	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, _M >> (_W - 7)},
+}
+
+var lshVW = []argVW{
+	{},
+	{nat{0}, nat{0}, 0, 0},
+	{nat{0}, nat{0}, 1, 0},
+	{nat{0}, nat{0}, 20, 0},
+
+	{nat{_M}, nat{_M}, 0, 0},
+	{nat{_M << 1 & _M}, nat{_M}, 1, 1},
+	{nat{_M << 20 & _M}, nat{_M}, 20, _M >> (_W - 20)},
+
+	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
+	{nat{_M << 1 & _M, _M, _M}, nat{_M, _M, _M}, 1, 1},
+	{nat{_M << 20 & _M, _M, _M}, nat{_M, _M, _M}, 20, _M >> (_W - 20)},
+}
+
+var rshVW = []argVW{
+	{},
+	{nat{0}, nat{0}, 0, 0},
+	{nat{0}, nat{0}, 1, 0},
+	{nat{0}, nat{0}, 20, 0},
+
+	{nat{_M}, nat{_M}, 0, 0},
+	{nat{_M >> 1}, nat{_M}, 1, _M << (_W - 1) & _M},
+	{nat{_M >> 20}, nat{_M}, 20, _M << (_W - 20) & _M},
+
+	{nat{_M, _M, _M}, nat{_M, _M, _M}, 0, 0},
+	{nat{_M, _M, _M >> 1}, nat{_M, _M, _M}, 1, _M << (_W - 1) & _M},
+	{nat{_M, _M, _M >> 20}, nat{_M, _M, _M}, 20, _M << (_W - 20) & _M},
+}
+
+
+func testFunVW(t *testing.T, msg string, f funVW, a argVW) {
+	z := make(nat, len(a.z))
+	c := f(z, a.x, a.y)
+	for i, zi := range z {
+		if zi != a.z[i] {
+			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
+			break
+		}
+	}
+	if c != a.c {
+		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
+	}
+}
+
+
+func TestFunVW(t *testing.T) {
+	for _, a := range sumVW {
+		arg := a
+		testFunVW(t, "addVW_g", addVW_g, arg)
+		testFunVW(t, "addVW", addVW, arg)
+
+		arg = argVW{a.x, a.z, a.y, a.c}
+		testFunVW(t, "subVW_g", subVW_g, arg)
+		testFunVW(t, "subVW", subVW, arg)
+	}
+
+	for _, a := range lshVW {
+		arg := a
+		testFunVW(t, "shlVW_g", shlVW_g, arg)
+		testFunVW(t, "shlVW", shlVW, arg)
+	}
+
+	for _, a := range rshVW {
+		arg := a
+		testFunVW(t, "shrVW_g", shrVW_g, arg)
+		testFunVW(t, "shrVW", shrVW, arg)
+	}
+}
+
+
+type funVWW func(z, x []Word, y, r Word) (c Word)
+type argVWW struct {
+	z, x nat
+	y, r Word
+	c    Word
+}
+
+var prodVWW = []argVWW{
+	{},
+	{nat{0}, nat{0}, 0, 0, 0},
+	{nat{991}, nat{0}, 0, 991, 0},
+	{nat{0}, nat{_M}, 0, 0, 0},
+	{nat{991}, nat{_M}, 0, 991, 0},
+	{nat{0}, nat{0}, _M, 0, 0},
+	{nat{991}, nat{0}, _M, 991, 0},
+	{nat{1}, nat{1}, 1, 0, 0},
+	{nat{992}, nat{1}, 1, 991, 0},
+	{nat{22793}, nat{991}, 23, 0, 0},
+	{nat{22800}, nat{991}, 23, 7, 0},
+	{nat{0, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 0, 0},
+	{nat{7, 0, 0, 22793}, nat{0, 0, 0, 991}, 23, 7, 0},
+	{nat{0, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 0, 0},
+	{nat{991, 0, 0, 0}, nat{7893475, 7395495, 798547395, 68943}, 0, 991, 0},
+	{nat{0, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 0, 0},
+	{nat{991, 0, 0, 0}, nat{0, 0, 0, 0}, 894375984, 991, 0},
+	{nat{_M << 1 & _M}, nat{_M}, 1 << 1, 0, _M >> (_W - 1)},
+	{nat{_M<<1&_M + 1}, nat{_M}, 1 << 1, 1, _M >> (_W - 1)},
+	{nat{_M << 7 & _M}, nat{_M}, 1 << 7, 0, _M >> (_W - 7)},
+	{nat{_M<<7&_M + 1<<6}, nat{_M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
+	{nat{_M << 7 & _M, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 0, _M >> (_W - 7)},
+	{nat{_M<<7&_M + 1<<6, _M, _M, _M}, nat{_M, _M, _M, _M}, 1 << 7, 1 << 6, _M >> (_W - 7)},
+}
+
+
+func testFunVWW(t *testing.T, msg string, f funVWW, a argVWW) {
+	z := make(nat, len(a.z))
+	c := f(z, a.x, a.y, a.r)
+	for i, zi := range z {
+		if zi != a.z[i] {
+			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
+			break
+		}
+	}
+	if c != a.c {
+		t.Errorf("%s%+v\n\tgot c = %#x; want %#x", msg, a, c, a.c)
+	}
+}
+
+
+// TODO(gri) mulAddVWW and divWVW are symmetric operations but
+//           their signature is not symmetric. Try to unify.
+
+type funWVW func(z []Word, xn Word, x []Word, y Word) (r Word)
+type argWVW struct {
+	z  nat
+	xn Word
+	x  nat
+	y  Word
+	r  Word
+}
+
+func testFunWVW(t *testing.T, msg string, f funWVW, a argWVW) {
+	z := make(nat, len(a.z))
+	r := f(z, a.xn, a.x, a.y)
+	for i, zi := range z {
+		if zi != a.z[i] {
+			t.Errorf("%s%+v\n\tgot z[%d] = %#x; want %#x", msg, a, i, zi, a.z[i])
+			break
+		}
+	}
+	if r != a.r {
+		t.Errorf("%s%+v\n\tgot r = %#x; want %#x", msg, a, r, a.r)
+	}
+}
+
+
+func TestFunVWW(t *testing.T) {
+	for _, a := range prodVWW {
+		arg := a
+		testFunVWW(t, "mulAddVWW_g", mulAddVWW_g, arg)
+		testFunVWW(t, "mulAddVWW", mulAddVWW, arg)
+
+		if a.y != 0 && a.r < a.y {
+			arg := argWVW{a.x, a.c, a.z, a.y, a.r}
+			testFunWVW(t, "divWVW_g", divWVW_g, arg)
+			testFunWVW(t, "divWVW", divWVW, arg)
+		}
+	}
+}
+
+
+var mulWWTests = []struct {
+	x, y Word
+	q, r Word
+}{
+	{_M, _M, _M - 1, 1},
+	// 32 bit only: {0xc47dfa8c, 50911, 0x98a4, 0x998587f4},
+}
+
+
+func TestMulWW(t *testing.T) {
+	for i, test := range mulWWTests {
+		q, r := mulWW_g(test.x, test.y)
+		if q != test.q || r != test.r {
+			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
+		}
+	}
+}
+
+
+var mulAddWWWTests = []struct {
+	x, y, c Word
+	q, r    Word
+}{
+	// TODO(agl): These will only work on 64-bit platforms.
+	// {15064310297182388543, 0xe7df04d2d35d5d80, 13537600649892366549, 13644450054494335067, 10832252001440893781},
+	// {15064310297182388543, 0xdab2f18048baa68d, 13644450054494335067, 12869334219691522700, 14233854684711418382},
+	{_M, _M, 0, _M - 1, 1},
+	{_M, _M, _M, _M, 0},
+}
+
+
+func TestMulAddWWW(t *testing.T) {
+	for i, test := range mulAddWWWTests {
+		q, r := mulAddWWW_g(test.x, test.y, test.c)
+		if q != test.q || r != test.r {
+			t.Errorf("#%d got (%x, %x) want (%x, %x)", i, q, r, test.q, test.r)
+		}
+	}
+}
diff --git a/libgo/go/big/calibrate_test.go b/libgo/go/big/calibrate_test.go
new file mode 100644
index 000000000..c6cd2e693
--- /dev/null
+++ b/libgo/go/big/calibrate_test.go
@@ -0,0 +1,92 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file prints execution times for the Mul benchmark
+// given different Karatsuba thresholds. The result may be
+// used to manually fine-tune the threshold constant. The
+// results are somewhat fragile; use repeated runs to get
+// a clear picture.
+
+// Usage: gotest -calibrate
+
+package big
+
+import (
+	"flag"
+	"fmt"
+	"testing"
+	"time"
+)
+
+
+var calibrate = flag.Bool("calibrate", false, "run calibration test")
+
+
+// measure returns the time to run f
+func measure(f func()) int64 {
+	const N = 100
+	start := time.Nanoseconds()
+	for i := N; i > 0; i-- {
+		f()
+	}
+	stop := time.Nanoseconds()
+	return (stop - start) / N
+}
+
+
+func computeThresholds() {
+	fmt.Printf("Multiplication times for varying Karatsuba thresholds\n")
+	fmt.Printf("(run repeatedly for good results)\n")
+
+	// determine Tk, the work load execution time using basic multiplication
+	karatsubaThreshold = 1e9 // disable karatsuba
+	Tb := measure(benchmarkMulLoad)
+	fmt.Printf("Tb = %dns\n", Tb)
+
+	// thresholds
+	n := 8 // any lower values for the threshold lead to very slow multiplies
+	th1 := -1
+	th2 := -1
+
+	var deltaOld int64
+	for count := -1; count != 0; count-- {
+		// determine Tk, the work load execution time using Karatsuba multiplication
+		karatsubaThreshold = n // enable karatsuba
+		Tk := measure(benchmarkMulLoad)
+
+		// improvement over Tb
+		delta := (Tb - Tk) * 100 / Tb
+
+		fmt.Printf("n = %3d  Tk = %8dns  %4d%%", n, Tk, delta)
+
+		// determine break-even point
+		if Tk < Tb && th1 < 0 {
+			th1 = n
+			fmt.Print("  break-even point")
+		}
+
+		// determine diminishing return
+		if 0 < delta && delta < deltaOld && th2 < 0 {
+			th2 = n
+			fmt.Print("  diminishing return")
+		}
+		deltaOld = delta
+
+		fmt.Println()
+
+		// trigger counter
+		if th1 >= 0 && th2 >= 0 && count < 0 {
+			count = 20 // this many extra measurements after we got both thresholds
+		}
+
+		n++
+	}
+}
+
+
+func TestCalibrate(t *testing.T) {
+	if *calibrate {
+		computeThresholds()
+	}
+}
diff --git a/libgo/go/big/hilbert_test.go b/libgo/go/big/hilbert_test.go
new file mode 100644
index 000000000..66a21214d
--- /dev/null
+++ b/libgo/go/big/hilbert_test.go
@@ -0,0 +1,173 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// A little test program and benchmark for rational arithmetics.
+// Computes a Hilbert matrix, its inverse, multiplies them
+// and verifies that the product is the identity matrix.
+
+package big
+
+import (
+	"fmt"
+	"testing"
+)
+
+
+type matrix struct {
+	n, m int
+	a    []*Rat
+}
+
+
+func (a *matrix) at(i, j int) *Rat {
+	if !(0 <= i && i < a.n && 0 <= j && j < a.m) {
+		panic("index out of range")
+	}
+	return a.a[i*a.m+j]
+}
+
+
+func (a *matrix) set(i, j int, x *Rat) {
+	if !(0 <= i && i < a.n && 0 <= j && j < a.m) {
+		panic("index out of range")
+	}
+	a.a[i*a.m+j] = x
+}
+
+
+func newMatrix(n, m int) *matrix {
+	if !(0 <= n && 0 <= m) {
+		panic("illegal matrix")
+	}
+	a := new(matrix)
+	a.n = n
+	a.m = m
+	a.a = make([]*Rat, n*m)
+	return a
+}
+
+
+func newUnit(n int) *matrix {
+	a := newMatrix(n, n)
+	for i := 0; i < n; i++ {
+		for j := 0; j < n; j++ {
+			x := NewRat(0, 1)
+			if i == j {
+				x.SetInt64(1)
+			}
+			a.set(i, j, x)
+		}
+	}
+	return a
+}
+
+
+func newHilbert(n int) *matrix {
+	a := newMatrix(n, n)
+	for i := 0; i < n; i++ {
+		for j := 0; j < n; j++ {
+			a.set(i, j, NewRat(1, int64(i+j+1)))
+		}
+	}
+	return a
+}
+
+
+func newInverseHilbert(n int) *matrix {
+	a := newMatrix(n, n)
+	for i := 0; i < n; i++ {
+		for j := 0; j < n; j++ {
+			x1 := new(Rat).SetInt64(int64(i + j + 1))
+			x2 := new(Rat).SetInt(new(Int).Binomial(int64(n+i), int64(n-j-1)))
+			x3 := new(Rat).SetInt(new(Int).Binomial(int64(n+j), int64(n-i-1)))
+			x4 := new(Rat).SetInt(new(Int).Binomial(int64(i+j), int64(i)))
+
+			x1.Mul(x1, x2)
+			x1.Mul(x1, x3)
+			x1.Mul(x1, x4)
+			x1.Mul(x1, x4)
+
+			if (i+j)&1 != 0 {
+				x1.Neg(x1)
+			}
+
+			a.set(i, j, x1)
+		}
+	}
+	return a
+}
+
+
+func (a *matrix) mul(b *matrix) *matrix {
+	if a.m != b.n {
+		panic("illegal matrix multiply")
+	}
+	c := newMatrix(a.n, b.m)
+	for i := 0; i < c.n; i++ {
+		for j := 0; j < c.m; j++ {
+			x := NewRat(0, 1)
+			for k := 0; k < a.m; k++ {
+				x.Add(x, new(Rat).Mul(a.at(i, k), b.at(k, j)))
+			}
+			c.set(i, j, x)
+		}
+	}
+	return c
+}
+
+
+func (a *matrix) eql(b *matrix) bool {
+	if a.n != b.n || a.m != b.m {
+		return false
+	}
+	for i := 0; i < a.n; i++ {
+		for j := 0; j < a.m; j++ {
+			if a.at(i, j).Cmp(b.at(i, j)) != 0 {
+				return false
+			}
+		}
+	}
+	return true
+}
+
+
+func (a *matrix) String() string {
+	s := ""
+	for i := 0; i < a.n; i++ {
+		for j := 0; j < a.m; j++ {
+			s += fmt.Sprintf("\t%s", a.at(i, j))
+		}
+		s += "\n"
+	}
+	return s
+}
+
+
+func doHilbert(t *testing.T, n int) {
+	a := newHilbert(n)
+	b := newInverseHilbert(n)
+	I := newUnit(n)
+	ab := a.mul(b)
+	if !ab.eql(I) {
+		if t == nil {
+			panic("Hilbert failed")
+		}
+		t.Errorf("a   = %s\n", a)
+		t.Errorf("b   = %s\n", b)
+		t.Errorf("a*b = %s\n", ab)
+		t.Errorf("I   = %s\n", I)
+	}
+}
+
+
+func TestHilbert(t *testing.T) {
+	doHilbert(t, 10)
+}
+
+
+func BenchmarkHilbert(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		doHilbert(nil, 10)
+	}
+}
diff --git a/libgo/go/big/int.go b/libgo/go/big/int.go
new file mode 100644
index 000000000..46e008734
--- /dev/null
+++ b/libgo/go/big/int.go
@@ -0,0 +1,741 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file implements signed multi-precision integers.
+
+package big
+
+import (
+	"fmt"
+	"rand"
+)
+
+// An Int represents a signed multi-precision integer.
+// The zero value for an Int represents the value 0.
+type Int struct {
+	neg bool // sign
+	abs nat  // absolute value of the integer
+}
+
+
+var intOne = &Int{false, natOne}
+
+
+// Sign returns:
+//
+//	-1 if x <  0
+//	 0 if x == 0
+//	+1 if x >  0
+//
+func (x *Int) Sign() int {
+	if len(x.abs) == 0 {
+		return 0
+	}
+	if x.neg {
+		return -1
+	}
+	return 1
+}
+
+
+// SetInt64 sets z to x and returns z.
+func (z *Int) SetInt64(x int64) *Int {
+	neg := false
+	if x < 0 {
+		neg = true
+		x = -x
+	}
+	z.abs = z.abs.setUint64(uint64(x))
+	z.neg = neg
+	return z
+}
+
+
+// NewInt allocates and returns a new Int set to x.
+func NewInt(x int64) *Int {
+	return new(Int).SetInt64(x)
+}
+
+
+// Set sets z to x and returns z.
+func (z *Int) Set(x *Int) *Int {
+	z.abs = z.abs.set(x.abs)
+	z.neg = x.neg
+	return z
+}
+
+
+// Abs sets z to |x| (the absolute value of x) and returns z.
+func (z *Int) Abs(x *Int) *Int {
+	z.abs = z.abs.set(x.abs)
+	z.neg = false
+	return z
+}
+
+
+// Neg sets z to -x and returns z.
+func (z *Int) Neg(x *Int) *Int {
+	z.abs = z.abs.set(x.abs)
+	z.neg = len(z.abs) > 0 && !x.neg // 0 has no sign
+	return z
+}
+
+
+// Add sets z to the sum x+y and returns z.
+func (z *Int) Add(x, y *Int) *Int {
+	neg := x.neg
+	if x.neg == y.neg {
+		// x + y == x + y
+		// (-x) + (-y) == -(x + y)
+		z.abs = z.abs.add(x.abs, y.abs)
+	} else {
+		// x + (-y) == x - y == -(y - x)
+		// (-x) + y == y - x == -(x - y)
+		if x.abs.cmp(y.abs) >= 0 {
+			z.abs = z.abs.sub(x.abs, y.abs)
+		} else {
+			neg = !neg
+			z.abs = z.abs.sub(y.abs, x.abs)
+		}
+	}
+	z.neg = len(z.abs) > 0 && neg // 0 has no sign
+	return z
+}
+
+
+// Sub sets z to the difference x-y and returns z.
+func (z *Int) Sub(x, y *Int) *Int {
+	neg := x.neg
+	if x.neg != y.neg {
+		// x - (-y) == x + y
+		// (-x) - y == -(x + y)
+		z.abs = z.abs.add(x.abs, y.abs)
+	} else {
+		// x - y == x - y == -(y - x)
+		// (-x) - (-y) == y - x == -(x - y)
+		if x.abs.cmp(y.abs) >= 0 {
+			z.abs = z.abs.sub(x.abs, y.abs)
+		} else {
+			neg = !neg
+			z.abs = z.abs.sub(y.abs, x.abs)
+		}
+	}
+	z.neg = len(z.abs) > 0 && neg // 0 has no sign
+	return z
+}
+
+
+// Mul sets z to the product x*y and returns z.
+func (z *Int) Mul(x, y *Int) *Int {
+	// x * y == x * y
+	// x * (-y) == -(x * y)
+	// (-x) * y == -(x * y)
+	// (-x) * (-y) == x * y
+	z.abs = z.abs.mul(x.abs, y.abs)
+	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
+	return z
+}
+
+
+// MulRange sets z to the product of all integers
+// in the range [a, b] inclusively and returns z.
+// If a > b (empty range), the result is 1.
+func (z *Int) MulRange(a, b int64) *Int {
+	switch {
+	case a > b:
+		return z.SetInt64(1) // empty range
+	case a <= 0 && b >= 0:
+		return z.SetInt64(0) // range includes 0
+	}
+	// a <= b && (b < 0 || a > 0)
+
+	neg := false
+	if a < 0 {
+		neg = (b-a)&1 == 0
+		a, b = -b, -a
+	}
+
+	z.abs = z.abs.mulRange(uint64(a), uint64(b))
+	z.neg = neg
+	return z
+}
+
+
+// Binomial sets z to the binomial coefficient of (n, k) and returns z.
+func (z *Int) Binomial(n, k int64) *Int {
+	var a, b Int
+	a.MulRange(n-k+1, n)
+	b.MulRange(1, k)
+	return z.Quo(&a, &b)
+}
+
+
+// Quo sets z to the quotient x/y for y != 0 and returns z.
+// If y == 0, a division-by-zero run-time panic occurs.
+// See QuoRem for more details.
+func (z *Int) Quo(x, y *Int) *Int {
+	z.abs, _ = z.abs.div(nil, x.abs, y.abs)
+	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
+	return z
+}
+
+
+// Rem sets z to the remainder x%y for y != 0 and returns z.
+// If y == 0, a division-by-zero run-time panic occurs.
+// See QuoRem for more details.
+func (z *Int) Rem(x, y *Int) *Int {
+	_, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
+	z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
+	return z
+}
+
+
+// QuoRem sets z to the quotient x/y and r to the remainder x%y
+// and returns the pair (z, r) for y != 0.
+// If y == 0, a division-by-zero run-time panic occurs.
+//
+// QuoRem implements T-division and modulus (like Go):
+//
+//	q = x/y      with the result truncated to zero
+//	r = x - y*q
+//
+// (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
+//
+func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
+	z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
+	z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign
+	return z, r
+}
+
+
+// Div sets z to the quotient x/y for y != 0 and returns z.
+// If y == 0, a division-by-zero run-time panic occurs.
+// See DivMod for more details.
+func (z *Int) Div(x, y *Int) *Int {
+	y_neg := y.neg // z may be an alias for y
+	var r Int
+	z.QuoRem(x, y, &r)
+	if r.neg {
+		if y_neg {
+			z.Add(z, intOne)
+		} else {
+			z.Sub(z, intOne)
+		}
+	}
+	return z
+}
+
+
+// Mod sets z to the modulus x%y for y != 0 and returns z.
+// If y == 0, a division-by-zero run-time panic occurs.
+// See DivMod for more details.
+func (z *Int) Mod(x, y *Int) *Int {
+	y0 := y // save y
+	if z == y || alias(z.abs, y.abs) {
+		y0 = new(Int).Set(y)
+	}
+	var q Int
+	q.QuoRem(x, y, z)
+	if z.neg {
+		if y0.neg {
+			z.Sub(z, y0)
+		} else {
+			z.Add(z, y0)
+		}
+	}
+	return z
+}
+
+
+// DivMod sets z to the quotient x div y and m to the modulus x mod y
+// and returns the pair (z, m) for y != 0.
+// If y == 0, a division-by-zero run-time panic occurs.
+//
+// DivMod implements Euclidean division and modulus (unlike Go):
+//
+//	q = x div y  such that
+//	m = x - y*q  with 0 <= m < |q|
+//
+// (See Raymond T. Boute, ``The Euclidean definition of the functions
+// div and mod''. ACM Transactions on Programming Languages and
+// Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
+// ACM press.)
+//
+func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
+	y0 := y // save y
+	if z == y || alias(z.abs, y.abs) {
+		y0 = new(Int).Set(y)
+	}
+	z.QuoRem(x, y, m)
+	if m.neg {
+		if y0.neg {
+			z.Add(z, intOne)
+			m.Sub(m, y0)
+		} else {
+			z.Sub(z, intOne)
+			m.Add(m, y0)
+		}
+	}
+	return z, m
+}
+
+
+// Cmp compares x and y and returns:
+//
+//   -1 if x <  y
+//    0 if x == y
+//   +1 if x >  y
+//
+func (x *Int) Cmp(y *Int) (r int) {
+	// x cmp y == x cmp y
+	// x cmp (-y) == x
+	// (-x) cmp y == y
+	// (-x) cmp (-y) == -(x cmp y)
+	switch {
+	case x.neg == y.neg:
+		r = x.abs.cmp(y.abs)
+		if x.neg {
+			r = -r
+		}
+	case x.neg:
+		r = -1
+	default:
+		r = 1
+	}
+	return
+}
+
+
+func (x *Int) String() string {
+	s := ""
+	if x.neg {
+		s = "-"
+	}
+	return s + x.abs.string(10)
+}
+
+
+func fmtbase(ch int) int {
+	switch ch {
+	case 'b':
+		return 2
+	case 'o':
+		return 8
+	case 'd':
+		return 10
+	case 'x':
+		return 16
+	}
+	return 10
+}
+
+
+// Format is a support routine for fmt.Formatter. It accepts
+// the formats 'b' (binary), 'o' (octal), 'd' (decimal) and
+// 'x' (hexadecimal).
+//
+func (x *Int) Format(s fmt.State, ch int) {
+	if x.neg {
+		fmt.Fprint(s, "-")
+	}
+	fmt.Fprint(s, x.abs.string(fmtbase(ch)))
+}
+
+
+// Int64 returns the int64 representation of z.
+// If z cannot be represented in an int64, the result is undefined.
+func (x *Int) Int64() int64 {
+	if len(x.abs) == 0 {
+		return 0
+	}
+	v := int64(x.abs[0])
+	if _W == 32 && len(x.abs) > 1 {
+		v |= int64(x.abs[1]) << 32
+	}
+	if x.neg {
+		v = -v
+	}
+	return v
+}
+
+
+// SetString sets z to the value of s, interpreted in the given base,
+// and returns z and a boolean indicating success. If SetString fails,
+// the value of z is undefined.
+//
+// If the base argument is 0, the string prefix determines the actual
+// conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the
+// ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects
+// base 2. Otherwise the selected base is 10.
+//
+func (z *Int) SetString(s string, base int) (*Int, bool) {
+	if len(s) == 0 || base < 0 || base == 1 || 16 < base {
+		return z, false
+	}
+
+	neg := s[0] == '-'
+	if neg || s[0] == '+' {
+		s = s[1:]
+		if len(s) == 0 {
+			return z, false
+		}
+	}
+
+	var scanned int
+	z.abs, _, scanned = z.abs.scan(s, base)
+	if scanned != len(s) {
+		return z, false
+	}
+	z.neg = len(z.abs) > 0 && neg // 0 has no sign
+
+	return z, true
+}
+
+
+// SetBytes interprets b as the bytes of a big-endian, unsigned integer and
+// sets z to that value.
+func (z *Int) SetBytes(b []byte) *Int {
+	const s = _S
+	z.abs = z.abs.make((len(b) + s - 1) / s)
+
+	j := 0
+	for len(b) >= s {
+		var w Word
+
+		for i := s; i > 0; i-- {
+			w <<= 8
+			w |= Word(b[len(b)-i])
+		}
+
+		z.abs[j] = w
+		j++
+		b = b[0 : len(b)-s]
+	}
+
+	if len(b) > 0 {
+		var w Word
+
+		for i := len(b); i > 0; i-- {
+			w <<= 8
+			w |= Word(b[len(b)-i])
+		}
+
+		z.abs[j] = w
+	}
+
+	z.abs = z.abs.norm()
+	z.neg = false
+	return z
+}
+
+
+// Bytes returns the absolute value of x as a big-endian byte array.
+func (z *Int) Bytes() []byte {
+	const s = _S
+	b := make([]byte, len(z.abs)*s)
+
+	for i, w := range z.abs {
+		wordBytes := b[(len(z.abs)-i-1)*s : (len(z.abs)-i)*s]
+		for j := s - 1; j >= 0; j-- {
+			wordBytes[j] = byte(w)
+			w >>= 8
+		}
+	}
+
+	i := 0
+	for i < len(b) && b[i] == 0 {
+		i++
+	}
+
+	return b[i:]
+}
+
+
+// BitLen returns the length of the absolute value of z in bits.
+// The bit length of 0 is 0.
+func (z *Int) BitLen() int {
+	return z.abs.bitLen()
+}
+
+
+// Exp sets z = x**y mod m. If m is nil, z = x**y.
+// See Knuth, volume 2, section 4.6.3.
+func (z *Int) Exp(x, y, m *Int) *Int {
+	if y.neg || len(y.abs) == 0 {
+		neg := x.neg
+		z.SetInt64(1)
+		z.neg = neg
+		return z
+	}
+
+	var mWords nat
+	if m != nil {
+		mWords = m.abs
+	}
+
+	z.abs = z.abs.expNN(x.abs, y.abs, mWords)
+	z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 // 0 has no sign
+	return z
+}
+
+
+// GcdInt sets d to the greatest common divisor of a and b, which must be
+// positive numbers.
+// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
+// If either a or b is not positive, GcdInt sets d = x = y = 0.
+func GcdInt(d, x, y, a, b *Int) {
+	if a.neg || b.neg {
+		d.SetInt64(0)
+		if x != nil {
+			x.SetInt64(0)
+		}
+		if y != nil {
+			y.SetInt64(0)
+		}
+		return
+	}
+
+	A := new(Int).Set(a)
+	B := new(Int).Set(b)
+
+	X := new(Int)
+	Y := new(Int).SetInt64(1)
+
+	lastX := new(Int).SetInt64(1)
+	lastY := new(Int)
+
+	q := new(Int)
+	temp := new(Int)
+
+	for len(B.abs) > 0 {
+		r := new(Int)
+		q, r = q.QuoRem(A, B, r)
+
+		A, B = B, r
+
+		temp.Set(X)
+		X.Mul(X, q)
+		X.neg = !X.neg
+		X.Add(X, lastX)
+		lastX.Set(temp)
+
+		temp.Set(Y)
+		Y.Mul(Y, q)
+		Y.neg = !Y.neg
+		Y.Add(Y, lastY)
+		lastY.Set(temp)
+	}
+
+	if x != nil {
+		*x = *lastX
+	}
+
+	if y != nil {
+		*y = *lastY
+	}
+
+	*d = *A
+}
+
+
+// ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.
+// If it returns true, z is prime with probability 1 - 1/4^n.
+// If it returns false, z is not prime.
+func ProbablyPrime(z *Int, n int) bool {
+	return !z.neg && z.abs.probablyPrime(n)
+}
+
+
+// Rand sets z to a pseudo-random number in [0, n) and returns z. 
+func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
+	z.neg = false
+	if n.neg == true || len(n.abs) == 0 {
+		z.abs = nil
+		return z
+	}
+	z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
+	return z
+}
+
+
+// ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where
+// p is a prime) and returns z.
+func (z *Int) ModInverse(g, p *Int) *Int {
+	var d Int
+	GcdInt(&d, z, nil, g, p)
+	// x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking
+	// that modulo p results in g*x = 1, therefore x is the inverse element.
+	if z.neg {
+		z.Add(z, p)
+	}
+	return z
+}
+
+
+// Lsh sets z = x << n and returns z.
+func (z *Int) Lsh(x *Int, n uint) *Int {
+	z.abs = z.abs.shl(x.abs, n)
+	z.neg = x.neg
+	return z
+}
+
+
+// Rsh sets z = x >> n and returns z.
+func (z *Int) Rsh(x *Int, n uint) *Int {
+	if x.neg {
+		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
+		t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0
+		t = t.shr(t, n)
+		z.abs = t.add(t, natOne)
+		z.neg = true // z cannot be zero if x is negative
+		return z
+	}
+
+	z.abs = z.abs.shr(x.abs, n)
+	z.neg = false
+	return z
+}
+
+
+// And sets z = x & y and returns z.
+func (z *Int) And(x, y *Int) *Int {
+	if x.neg == y.neg {
+		if x.neg {
+			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
+			x1 := nat{}.sub(x.abs, natOne)
+			y1 := nat{}.sub(y.abs, natOne)
+			z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
+			z.neg = true // z cannot be zero if x and y are negative
+			return z
+		}
+
+		// x & y == x & y
+		z.abs = z.abs.and(x.abs, y.abs)
+		z.neg = false
+		return z
+	}
+
+	// x.neg != y.neg
+	if x.neg {
+		x, y = y, x // & is symmetric
+	}
+
+	// x & (-y) == x & ^(y-1) == x &^ (y-1)
+	y1 := nat{}.sub(y.abs, natOne)
+	z.abs = z.abs.andNot(x.abs, y1)
+	z.neg = false
+	return z
+}
+
+
+// AndNot sets z = x &^ y and returns z.
+func (z *Int) AndNot(x, y *Int) *Int {
+	if x.neg == y.neg {
+		if x.neg {
+			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
+			x1 := nat{}.sub(x.abs, natOne)
+			y1 := nat{}.sub(y.abs, natOne)
+			z.abs = z.abs.andNot(y1, x1)
+			z.neg = false
+			return z
+		}
+
+		// x &^ y == x &^ y
+		z.abs = z.abs.andNot(x.abs, y.abs)
+		z.neg = false
+		return z
+	}
+
+	if x.neg {
+		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
+		x1 := nat{}.sub(x.abs, natOne)
+		z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
+		z.neg = true // z cannot be zero if x is negative and y is positive
+		return z
+	}
+
+	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
+	y1 := nat{}.add(y.abs, natOne)
+	z.abs = z.abs.and(x.abs, y1)
+	z.neg = false
+	return z
+}
+
+
+// Or sets z = x | y and returns z.
+func (z *Int) Or(x, y *Int) *Int {
+	if x.neg == y.neg {
+		if x.neg {
+			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
+			x1 := nat{}.sub(x.abs, natOne)
+			y1 := nat{}.sub(y.abs, natOne)
+			z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
+			z.neg = true // z cannot be zero if x and y are negative
+			return z
+		}
+
+		// x | y == x | y
+		z.abs = z.abs.or(x.abs, y.abs)
+		z.neg = false
+		return z
+	}
+
+	// x.neg != y.neg
+	if x.neg {
+		x, y = y, x // | is symmetric
+	}
+
+	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
+	y1 := nat{}.sub(y.abs, natOne)
+	z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
+	z.neg = true // z cannot be zero if one of x or y is negative
+	return z
+}
+
+
+// Xor sets z = x ^ y and returns z.
+func (z *Int) Xor(x, y *Int) *Int {
+	if x.neg == y.neg {
+		if x.neg {
+			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
+			x1 := nat{}.sub(x.abs, natOne)
+			y1 := nat{}.sub(y.abs, natOne)
+			z.abs = z.abs.xor(x1, y1)
+			z.neg = false
+			return z
+		}
+
+		// x ^ y == x ^ y
+		z.abs = z.abs.xor(x.abs, y.abs)
+		z.neg = false
+		return z
+	}
+
+	// x.neg != y.neg
+	if x.neg {
+		x, y = y, x // ^ is symmetric
+	}
+
+	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
+	y1 := nat{}.sub(y.abs, natOne)
+	z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
+	z.neg = true // z cannot be zero if only one of x or y is negative
+	return z
+}
+
+
+// Not sets z = ^x and returns z.
+func (z *Int) Not(x *Int) *Int {
+	if x.neg {
+		// ^(-x) == ^(^(x-1)) == x-1
+		z.abs = z.abs.sub(x.abs, natOne)
+		z.neg = false
+		return z
+	}
+
+	// ^x == -x-1 == -(x+1)
+	z.abs = z.abs.add(x.abs, natOne)
+	z.neg = true // z cannot be zero if x is positive
+	return z
+}
diff --git a/libgo/go/big/int_test.go b/libgo/go/big/int_test.go
new file mode 100644
index 000000000..fc981e1da
--- /dev/null
+++ b/libgo/go/big/int_test.go
@@ -0,0 +1,1055 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package big
+
+import (
+	"bytes"
+	"encoding/hex"
+	"fmt"
+	"testing"
+	"testing/quick"
+)
+
+
+func isNormalized(x *Int) bool {
+	if len(x.abs) == 0 {
+		return !x.neg
+	}
+	// len(x.abs) > 0
+	return x.abs[len(x.abs)-1] != 0
+}
+
+
+type funZZ func(z, x, y *Int) *Int
+type argZZ struct {
+	z, x, y *Int
+}
+
+
+var sumZZ = []argZZ{
+	{NewInt(0), NewInt(0), NewInt(0)},
+	{NewInt(1), NewInt(1), NewInt(0)},
+	{NewInt(1111111110), NewInt(123456789), NewInt(987654321)},
+	{NewInt(-1), NewInt(-1), NewInt(0)},
+	{NewInt(864197532), NewInt(-123456789), NewInt(987654321)},
+	{NewInt(-1111111110), NewInt(-123456789), NewInt(-987654321)},
+}
+
+
+var prodZZ = []argZZ{
+	{NewInt(0), NewInt(0), NewInt(0)},
+	{NewInt(0), NewInt(1), NewInt(0)},
+	{NewInt(1), NewInt(1), NewInt(1)},
+	{NewInt(-991 * 991), NewInt(991), NewInt(-991)},
+	// TODO(gri) add larger products
+}
+
+
+func TestSignZ(t *testing.T) {
+	var zero Int
+	for _, a := range sumZZ {
+		s := a.z.Sign()
+		e := a.z.Cmp(&zero)
+		if s != e {
+			t.Errorf("got %d; want %d for z = %v", s, e, a.z)
+		}
+	}
+}
+
+
+func TestSetZ(t *testing.T) {
+	for _, a := range sumZZ {
+		var z Int
+		z.Set(a.z)
+		if !isNormalized(&z) {
+			t.Errorf("%v is not normalized", z)
+		}
+		if (&z).Cmp(a.z) != 0 {
+			t.Errorf("got z = %v; want %v", z, a.z)
+		}
+	}
+}
+
+
+func TestAbsZ(t *testing.T) {
+	var zero Int
+	for _, a := range sumZZ {
+		var z Int
+		z.Abs(a.z)
+		var e Int
+		e.Set(a.z)
+		if e.Cmp(&zero) < 0 {
+			e.Sub(&zero, &e)
+		}
+		if z.Cmp(&e) != 0 {
+			t.Errorf("got z = %v; want %v", z, e)
+		}
+	}
+}
+
+
+func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
+	var z Int
+	f(&z, a.x, a.y)
+	if !isNormalized(&z) {
+		t.Errorf("%s%v is not normalized", z, msg)
+	}
+	if (&z).Cmp(a.z) != 0 {
+		t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
+	}
+}
+
+
+func TestSumZZ(t *testing.T) {
+	AddZZ := func(z, x, y *Int) *Int { return z.Add(x, y) }
+	SubZZ := func(z, x, y *Int) *Int { return z.Sub(x, y) }
+	for _, a := range sumZZ {
+		arg := a
+		testFunZZ(t, "AddZZ", AddZZ, arg)
+
+		arg = argZZ{a.z, a.y, a.x}
+		testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
+
+		arg = argZZ{a.x, a.z, a.y}
+		testFunZZ(t, "SubZZ", SubZZ, arg)
+
+		arg = argZZ{a.y, a.z, a.x}
+		testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
+	}
+}
+
+
+func TestProdZZ(t *testing.T) {
+	MulZZ := func(z, x, y *Int) *Int { return z.Mul(x, y) }
+	for _, a := range prodZZ {
+		arg := a
+		testFunZZ(t, "MulZZ", MulZZ, arg)
+
+		arg = argZZ{a.z, a.y, a.x}
+		testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
+	}
+}
+
+
+// mulBytes returns x*y via grade school multiplication. Both inputs
+// and the result are assumed to be in big-endian representation (to
+// match the semantics of Int.Bytes and Int.SetBytes).
+func mulBytes(x, y []byte) []byte {
+	z := make([]byte, len(x)+len(y))
+
+	// multiply
+	k0 := len(z) - 1
+	for j := len(y) - 1; j >= 0; j-- {
+		d := int(y[j])
+		if d != 0 {
+			k := k0
+			carry := 0
+			for i := len(x) - 1; i >= 0; i-- {
+				t := int(z[k]) + int(x[i])*d + carry
+				z[k], carry = byte(t), t>>8
+				k--
+			}
+			z[k] = byte(carry)
+		}
+		k0--
+	}
+
+	// normalize (remove leading 0's)
+	i := 0
+	for i < len(z) && z[i] == 0 {
+		i++
+	}
+
+	return z[i:]
+}
+
+
+func checkMul(a, b []byte) bool {
+	var x, y, z1 Int
+	x.SetBytes(a)
+	y.SetBytes(b)
+	z1.Mul(&x, &y)
+
+	var z2 Int
+	z2.SetBytes(mulBytes(a, b))
+
+	return z1.Cmp(&z2) == 0
+}
+
+
+func TestMul(t *testing.T) {
+	if err := quick.Check(checkMul, nil); err != nil {
+		t.Error(err)
+	}
+}
+
+
+var mulRangesZ = []struct {
+	a, b int64
+	prod string
+}{
+	// entirely positive ranges are covered by mulRangesN
+	{-1, 1, "0"},
+	{-2, -1, "2"},
+	{-3, -2, "6"},
+	{-3, -1, "-6"},
+	{1, 3, "6"},
+	{-10, -10, "-10"},
+	{0, -1, "1"},                      // empty range
+	{-1, -100, "1"},                   // empty range
+	{-1, 1, "0"},                      // range includes 0
+	{-1e9, 0, "0"},                    // range includes 0
+	{-1e9, 1e9, "0"},                  // range includes 0
+	{-10, -1, "3628800"},              // 10!
+	{-20, -2, "-2432902008176640000"}, // -20!
+	{-99, -1,
+		"-933262154439441526816992388562667004907159682643816214685929" +
+			"638952175999932299156089414639761565182862536979208272237582" +
+			"511852109168640000000000000000000000", // -99!
+	},
+}
+
+
+func TestMulRangeZ(t *testing.T) {
+	var tmp Int
+	// test entirely positive ranges
+	for i, r := range mulRangesN {
+		prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
+		if prod != r.prod {
+			t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
+		}
+	}
+	// test other ranges
+	for i, r := range mulRangesZ {
+		prod := tmp.MulRange(r.a, r.b).String()
+		if prod != r.prod {
+			t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
+		}
+	}
+}
+
+
+var stringTests = []struct {
+	in   string
+	out  string
+	base int
+	val  int64
+	ok   bool
+}{
+	{in: "", ok: false},
+	{in: "a", ok: false},
+	{in: "z", ok: false},
+	{in: "+", ok: false},
+	{in: "-", ok: false},
+	{in: "0b", ok: false},
+	{in: "0x", ok: false},
+	{in: "2", base: 2, ok: false},
+	{in: "0b2", base: 0, ok: false},
+	{in: "08", ok: false},
+	{in: "8", base: 8, ok: false},
+	{in: "0xg", base: 0, ok: false},
+	{in: "g", base: 16, ok: false},
+	{"0", "0", 0, 0, true},
+	{"0", "0", 10, 0, true},
+	{"0", "0", 16, 0, true},
+	{"+0", "0", 0, 0, true},
+	{"-0", "0", 0, 0, true},
+	{"10", "10", 0, 10, true},
+	{"10", "10", 10, 10, true},
+	{"10", "10", 16, 16, true},
+	{"-10", "-10", 16, -16, true},
+	{"+10", "10", 16, 16, true},
+	{"0x10", "16", 0, 16, true},
+	{in: "0x10", base: 16, ok: false},
+	{"-0x10", "-16", 0, -16, true},
+	{"+0x10", "16", 0, 16, true},
+	{"00", "0", 0, 0, true},
+	{"0", "0", 8, 0, true},
+	{"07", "7", 0, 7, true},
+	{"7", "7", 8, 7, true},
+	{"023", "19", 0, 19, true},
+	{"23", "23", 8, 19, true},
+	{"cafebabe", "cafebabe", 16, 0xcafebabe, true},
+	{"0b0", "0", 0, 0, true},
+	{"-111", "-111", 2, -7, true},
+	{"-0b111", "-7", 0, -7, true},
+	{"0b1001010111", "599", 0, 0x257, true},
+	{"1001010111", "1001010111", 2, 0x257, true},
+}
+
+
+func format(base int) string {
+	switch base {
+	case 2:
+		return "%b"
+	case 8:
+		return "%o"
+	case 16:
+		return "%x"
+	}
+	return "%d"
+}
+
+
+func TestGetString(t *testing.T) {
+	z := new(Int)
+	for i, test := range stringTests {
+		if !test.ok {
+			continue
+		}
+		z.SetInt64(test.val)
+
+		if test.base == 10 {
+			s := z.String()
+			if s != test.out {
+				t.Errorf("#%da got %s; want %s", i, s, test.out)
+			}
+		}
+
+		s := fmt.Sprintf(format(test.base), z)
+		if s != test.out {
+			t.Errorf("#%db got %s; want %s", i, s, test.out)
+		}
+	}
+}
+
+
+func TestSetString(t *testing.T) {
+	tmp := new(Int)
+	for i, test := range stringTests {
+		n1, ok1 := new(Int).SetString(test.in, test.base)
+		n2, ok2 := tmp.SetString(test.in, test.base)
+		expected := NewInt(test.val)
+		if ok1 != test.ok || ok2 != test.ok {
+			t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
+			continue
+		}
+		if !ok1 || !ok2 {
+			continue
+		}
+
+		if ok1 && !isNormalized(n1) {
+			t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n1)
+		}
+		if ok2 && !isNormalized(n2) {
+			t.Errorf("#%d (input '%s'): %v is not normalized", i, test.in, *n2)
+		}
+
+		if n1.Cmp(expected) != 0 {
+			t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
+		}
+		if n2.Cmp(expected) != 0 {
+			t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
+		}
+	}
+}
+
+
+// Examples from the Go Language Spec, section "Arithmetic operators"
+var divisionSignsTests = []struct {
+	x, y int64
+	q, r int64 // T-division
+	d, m int64 // Euclidian division
+}{
+	{5, 3, 1, 2, 1, 2},
+	{-5, 3, -1, -2, -2, 1},
+	{5, -3, -1, 2, -1, 2},
+	{-5, -3, 1, -2, 2, 1},
+	{1, 2, 0, 1, 0, 1},
+	{8, 4, 2, 0, 2, 0},
+}
+
+
+func TestDivisionSigns(t *testing.T) {
+	for i, test := range divisionSignsTests {
+		x := NewInt(test.x)
+		y := NewInt(test.y)
+		q := NewInt(test.q)
+		r := NewInt(test.r)
+		d := NewInt(test.d)
+		m := NewInt(test.m)
+
+		q1 := new(Int).Quo(x, y)
+		r1 := new(Int).Rem(x, y)
+		if !isNormalized(q1) {
+			t.Errorf("#%d Quo: %v is not normalized", i, *q1)
+		}
+		if !isNormalized(r1) {
+			t.Errorf("#%d Rem: %v is not normalized", i, *r1)
+		}
+		if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
+			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
+		}
+
+		q2, r2 := new(Int).QuoRem(x, y, new(Int))
+		if !isNormalized(q2) {
+			t.Errorf("#%d Quo: %v is not normalized", i, *q2)
+		}
+		if !isNormalized(r2) {
+			t.Errorf("#%d Rem: %v is not normalized", i, *r2)
+		}
+		if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
+			t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
+		}
+
+		d1 := new(Int).Div(x, y)
+		m1 := new(Int).Mod(x, y)
+		if !isNormalized(d1) {
+			t.Errorf("#%d Div: %v is not normalized", i, *d1)
+		}
+		if !isNormalized(m1) {
+			t.Errorf("#%d Mod: %v is not normalized", i, *m1)
+		}
+		if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
+			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
+		}
+
+		d2, m2 := new(Int).DivMod(x, y, new(Int))
+		if !isNormalized(d2) {
+			t.Errorf("#%d Div: %v is not normalized", i, *d2)
+		}
+		if !isNormalized(m2) {
+			t.Errorf("#%d Mod: %v is not normalized", i, *m2)
+		}
+		if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
+			t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
+		}
+	}
+}
+
+
+func checkSetBytes(b []byte) bool {
+	hex1 := hex.EncodeToString(new(Int).SetBytes(b).Bytes())
+	hex2 := hex.EncodeToString(b)
+
+	for len(hex1) < len(hex2) {
+		hex1 = "0" + hex1
+	}
+
+	for len(hex1) > len(hex2) {
+		hex2 = "0" + hex2
+	}
+
+	return hex1 == hex2
+}
+
+
+func TestSetBytes(t *testing.T) {
+	if err := quick.Check(checkSetBytes, nil); err != nil {
+		t.Error(err)
+	}
+}
+
+
+func checkBytes(b []byte) bool {
+	b2 := new(Int).SetBytes(b).Bytes()
+	return bytes.Compare(b, b2) == 0
+}
+
+
+func TestBytes(t *testing.T) {
+	if err := quick.Check(checkSetBytes, nil); err != nil {
+		t.Error(err)
+	}
+}
+
+
+func checkQuo(x, y []byte) bool {
+	u := new(Int).SetBytes(x)
+	v := new(Int).SetBytes(y)
+
+	if len(v.abs) == 0 {
+		return true
+	}
+
+	r := new(Int)
+	q, r := new(Int).QuoRem(u, v, r)
+
+	if r.Cmp(v) >= 0 {
+		return false
+	}
+
+	uprime := new(Int).Set(q)
+	uprime.Mul(uprime, v)
+	uprime.Add(uprime, r)
+
+	return uprime.Cmp(u) == 0
+}
+
+
+var quoTests = []struct {
+	x, y string
+	q, r string
+}{
+	{
+		"476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
+		"9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
+		"50911",
+		"1",
+	},
+	{
+		"11510768301994997771168",
+		"1328165573307167369775",
+		"8",
+		"885443715537658812968",
+	},
+}
+
+
+func TestQuo(t *testing.T) {
+	if err := quick.Check(checkQuo, nil); err != nil {
+		t.Error(err)
+	}
+
+	for i, test := range quoTests {
+		x, _ := new(Int).SetString(test.x, 10)
+		y, _ := new(Int).SetString(test.y, 10)
+		expectedQ, _ := new(Int).SetString(test.q, 10)
+		expectedR, _ := new(Int).SetString(test.r, 10)
+
+		r := new(Int)
+		q, r := new(Int).QuoRem(x, y, r)
+
+		if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
+			t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
+		}
+	}
+}
+
+
+func TestQuoStepD6(t *testing.T) {
+	// See Knuth, Volume 2, section 4.3.1, exercise 21. This code exercises
+	// a code path which only triggers 1 in 10^{-19} cases.
+
+	u := &Int{false, nat{0, 0, 1 + 1<<(_W-1), _M ^ (1 << (_W - 1))}}
+	v := &Int{false, nat{5, 2 + 1<<(_W-1), 1 << (_W - 1)}}
+
+	r := new(Int)
+	q, r := new(Int).QuoRem(u, v, r)
+	const expectedQ64 = "18446744073709551613"
+	const expectedR64 = "3138550867693340382088035895064302439801311770021610913807"
+	const expectedQ32 = "4294967293"
+	const expectedR32 = "39614081266355540837921718287"
+	if q.String() != expectedQ64 && q.String() != expectedQ32 ||
+		r.String() != expectedR64 && r.String() != expectedR32 {
+		t.Errorf("got (%s, %s) want (%s, %s) or (%s, %s)", q, r, expectedQ64, expectedR64, expectedQ32, expectedR32)
+	}
+}
+
+
+var bitLenTests = []struct {
+	in  string
+	out int
+}{
+	{"-1", 1},
+	{"0", 0},
+	{"1", 1},
+	{"2", 2},
+	{"4", 3},
+	{"0xabc", 12},
+	{"0x8000", 16},
+	{"0x80000000", 32},
+	{"0x800000000000", 48},
+	{"0x8000000000000000", 64},
+	{"0x80000000000000000000", 80},
+	{"-0x4000000000000000000000", 87},
+}
+
+
+func TestBitLen(t *testing.T) {
+	for i, test := range bitLenTests {
+		x, ok := new(Int).SetString(test.in, 0)
+		if !ok {
+			t.Errorf("#%d test input invalid: %s", i, test.in)
+			continue
+		}
+
+		if n := x.BitLen(); n != test.out {
+			t.Errorf("#%d got %d want %d", i, n, test.out)
+		}
+	}
+}
+
+
+var expTests = []struct {
+	x, y, m string
+	out     string
+}{
+	{"5", "0", "", "1"},
+	{"-5", "0", "", "-1"},
+	{"5", "1", "", "5"},
+	{"-5", "1", "", "-5"},
+	{"-2", "3", "2", "0"},
+	{"5", "2", "", "25"},
+	{"1", "65537", "2", "1"},
+	{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
+	{"0x8000000000000000", "2", "6719", "4944"},
+	{"0x8000000000000000", "3", "6719", "5447"},
+	{"0x8000000000000000", "1000", "6719", "1603"},
+	{"0x8000000000000000", "1000000", "6719", "3199"},
+	{
+		"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
+		"298472983472983471903246121093472394872319615612417471234712061",
+		"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
+		"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
+	},
+}
+
+
+func TestExp(t *testing.T) {
+	for i, test := range expTests {
+		x, ok1 := new(Int).SetString(test.x, 0)
+		y, ok2 := new(Int).SetString(test.y, 0)
+		out, ok3 := new(Int).SetString(test.out, 0)
+
+		var ok4 bool
+		var m *Int
+
+		if len(test.m) == 0 {
+			m, ok4 = nil, true
+		} else {
+			m, ok4 = new(Int).SetString(test.m, 0)
+		}
+
+		if !ok1 || !ok2 || !ok3 || !ok4 {
+			t.Errorf("#%d: error in input", i)
+			continue
+		}
+
+		z := y.Exp(x, y, m)
+		if !isNormalized(z) {
+			t.Errorf("#%d: %v is not normalized", i, *z)
+		}
+		if z.Cmp(out) != 0 {
+			t.Errorf("#%d: got %s want %s", i, z, out)
+		}
+	}
+}
+
+
+func checkGcd(aBytes, bBytes []byte) bool {
+	a := new(Int).SetBytes(aBytes)
+	b := new(Int).SetBytes(bBytes)
+
+	x := new(Int)
+	y := new(Int)
+	d := new(Int)
+
+	GcdInt(d, x, y, a, b)
+	x.Mul(x, a)
+	y.Mul(y, b)
+	x.Add(x, y)
+
+	return x.Cmp(d) == 0
+}
+
+
+var gcdTests = []struct {
+	a, b    int64
+	d, x, y int64
+}{
+	{120, 23, 1, -9, 47},
+}
+
+
+func TestGcd(t *testing.T) {
+	for i, test := range gcdTests {
+		a := NewInt(test.a)
+		b := NewInt(test.b)
+
+		x := new(Int)
+		y := new(Int)
+		d := new(Int)
+
+		expectedX := NewInt(test.x)
+		expectedY := NewInt(test.y)
+		expectedD := NewInt(test.d)
+
+		GcdInt(d, x, y, a, b)
+
+		if expectedX.Cmp(x) != 0 ||
+			expectedY.Cmp(y) != 0 ||
+			expectedD.Cmp(d) != 0 {
+			t.Errorf("#%d got (%s %s %s) want (%s %s %s)", i, x, y, d, expectedX, expectedY, expectedD)
+		}
+	}
+
+	quick.Check(checkGcd, nil)
+}
+
+
+var primes = []string{
+	"2",
+	"3",
+	"5",
+	"7",
+	"11",
+
+	"13756265695458089029",
+	"13496181268022124907",
+	"10953742525620032441",
+	"17908251027575790097",
+
+	// http://code.google.com/p/go/issues/detail?id=638
+	"18699199384836356663",
+
+	"98920366548084643601728869055592650835572950932266967461790948584315647051443",
+	"94560208308847015747498523884063394671606671904944666360068158221458669711639",
+
+	// http://primes.utm.edu/lists/small/small3.html
+	"449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
+	"230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
+	"5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
+	"203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
+}
+
+
+var composites = []string{
+	"21284175091214687912771199898307297748211672914763848041968395774954376176754",
+	"6084766654921918907427900243509372380954290099172559290432744450051395395951",
+	"84594350493221918389213352992032324280367711247940675652888030554255915464401",
+	"82793403787388584738507275144194252681",
+}
+
+
+func TestProbablyPrime(t *testing.T) {
+	for i, s := range primes {
+		p, _ := new(Int).SetString(s, 10)
+		if !ProbablyPrime(p, 20) {
+			t.Errorf("#%d prime found to be non-prime (%s)", i, s)
+		}
+	}
+
+	for i, s := range composites {
+		c, _ := new(Int).SetString(s, 10)
+		if ProbablyPrime(c, 20) {
+			t.Errorf("#%d composite found to be prime (%s)", i, s)
+		}
+	}
+}
+
+
+type intShiftTest struct {
+	in    string
+	shift uint
+	out   string
+}
+
+
+var rshTests = []intShiftTest{
+	{"0", 0, "0"},
+	{"-0", 0, "0"},
+	{"0", 1, "0"},
+	{"0", 2, "0"},
+	{"1", 0, "1"},
+	{"1", 1, "0"},
+	{"1", 2, "0"},
+	{"2", 0, "2"},
+	{"2", 1, "1"},
+	{"-1", 0, "-1"},
+	{"-1", 1, "-1"},
+	{"-1", 10, "-1"},
+	{"-100", 2, "-25"},
+	{"-100", 3, "-13"},
+	{"-100", 100, "-1"},
+	{"4294967296", 0, "4294967296"},
+	{"4294967296", 1, "2147483648"},
+	{"4294967296", 2, "1073741824"},
+	{"18446744073709551616", 0, "18446744073709551616"},
+	{"18446744073709551616", 1, "9223372036854775808"},
+	{"18446744073709551616", 2, "4611686018427387904"},
+	{"18446744073709551616", 64, "1"},
+	{"340282366920938463463374607431768211456", 64, "18446744073709551616"},
+	{"340282366920938463463374607431768211456", 128, "1"},
+}
+
+
+func TestRsh(t *testing.T) {
+	for i, test := range rshTests {
+		in, _ := new(Int).SetString(test.in, 10)
+		expected, _ := new(Int).SetString(test.out, 10)
+		out := new(Int).Rsh(in, test.shift)
+
+		if !isNormalized(out) {
+			t.Errorf("#%d: %v is not normalized", i, *out)
+		}
+		if out.Cmp(expected) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, expected)
+		}
+	}
+}
+
+
+func TestRshSelf(t *testing.T) {
+	for i, test := range rshTests {
+		z, _ := new(Int).SetString(test.in, 10)
+		expected, _ := new(Int).SetString(test.out, 10)
+		z.Rsh(z, test.shift)
+
+		if !isNormalized(z) {
+			t.Errorf("#%d: %v is not normalized", i, *z)
+		}
+		if z.Cmp(expected) != 0 {
+			t.Errorf("#%d: got %s want %s", i, z, expected)
+		}
+	}
+}
+
+
+var lshTests = []intShiftTest{
+	{"0", 0, "0"},
+	{"0", 1, "0"},
+	{"0", 2, "0"},
+	{"1", 0, "1"},
+	{"1", 1, "2"},
+	{"1", 2, "4"},
+	{"2", 0, "2"},
+	{"2", 1, "4"},
+	{"2", 2, "8"},
+	{"-87", 1, "-174"},
+	{"4294967296", 0, "4294967296"},
+	{"4294967296", 1, "8589934592"},
+	{"4294967296", 2, "17179869184"},
+	{"18446744073709551616", 0, "18446744073709551616"},
+	{"9223372036854775808", 1, "18446744073709551616"},
+	{"4611686018427387904", 2, "18446744073709551616"},
+	{"1", 64, "18446744073709551616"},
+	{"18446744073709551616", 64, "340282366920938463463374607431768211456"},
+	{"1", 128, "340282366920938463463374607431768211456"},
+}
+
+
+func TestLsh(t *testing.T) {
+	for i, test := range lshTests {
+		in, _ := new(Int).SetString(test.in, 10)
+		expected, _ := new(Int).SetString(test.out, 10)
+		out := new(Int).Lsh(in, test.shift)
+
+		if !isNormalized(out) {
+			t.Errorf("#%d: %v is not normalized", i, *out)
+		}
+		if out.Cmp(expected) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, expected)
+		}
+	}
+}
+
+
+func TestLshSelf(t *testing.T) {
+	for i, test := range lshTests {
+		z, _ := new(Int).SetString(test.in, 10)
+		expected, _ := new(Int).SetString(test.out, 10)
+		z.Lsh(z, test.shift)
+
+		if !isNormalized(z) {
+			t.Errorf("#%d: %v is not normalized", i, *z)
+		}
+		if z.Cmp(expected) != 0 {
+			t.Errorf("#%d: got %s want %s", i, z, expected)
+		}
+	}
+}
+
+
+func TestLshRsh(t *testing.T) {
+	for i, test := range rshTests {
+		in, _ := new(Int).SetString(test.in, 10)
+		out := new(Int).Lsh(in, test.shift)
+		out = out.Rsh(out, test.shift)
+
+		if !isNormalized(out) {
+			t.Errorf("#%d: %v is not normalized", i, *out)
+		}
+		if in.Cmp(out) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, in)
+		}
+	}
+	for i, test := range lshTests {
+		in, _ := new(Int).SetString(test.in, 10)
+		out := new(Int).Lsh(in, test.shift)
+		out.Rsh(out, test.shift)
+
+		if !isNormalized(out) {
+			t.Errorf("#%d: %v is not normalized", i, *out)
+		}
+		if in.Cmp(out) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, in)
+		}
+	}
+}
+
+
+var int64Tests = []int64{
+	0,
+	1,
+	-1,
+	4294967295,
+	-4294967295,
+	4294967296,
+	-4294967296,
+	9223372036854775807,
+	-9223372036854775807,
+	-9223372036854775808,
+}
+
+
+func TestInt64(t *testing.T) {
+	for i, testVal := range int64Tests {
+		in := NewInt(testVal)
+		out := in.Int64()
+
+		if out != testVal {
+			t.Errorf("#%d got %d want %d", i, out, testVal)
+		}
+	}
+}
+
+
+var bitwiseTests = []struct {
+	x, y                 string
+	and, or, xor, andNot string
+}{
+	{"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
+	{"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
+	{"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
+	{"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
+	{"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
+	{"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
+	{"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
+	{"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
+	{"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
+	{"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
+	{"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
+	{"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
+	{"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
+	{
+		"0x1000009dc6e3d9822cba04129bcbe3401",
+		"0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
+		"0x1000001186210100001000009048c2001",
+		"0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
+		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
+		"0x8c40c2d8822caa04120b8321400",
+	},
+	{
+		"0x1000009dc6e3d9822cba04129bcbe3401",
+		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
+		"0x8c40c2d8822caa04120b8321401",
+		"-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
+		"-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
+		"0x1000001186210100001000009048c2000",
+	},
+	{
+		"-0x1000009dc6e3d9822cba04129bcbe3401",
+		"-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
+		"-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
+		"-0x1000001186210100001000009048c2001",
+		"0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
+		"0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
+	},
+}
+
+
+type bitFun func(z, x, y *Int) *Int
+
+func testBitFun(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
+	expected := new(Int)
+	expected.SetString(exp, 0)
+
+	out := f(new(Int), x, y)
+	if out.Cmp(expected) != 0 {
+		t.Errorf("%s: got %s want %s", msg, out, expected)
+	}
+}
+
+
+func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *Int, exp string) {
+	self := new(Int)
+	self.Set(x)
+	expected := new(Int)
+	expected.SetString(exp, 0)
+
+	self = f(self, self, y)
+	if self.Cmp(expected) != 0 {
+		t.Errorf("%s: got %s want %s", msg, self, expected)
+	}
+}
+
+
+func TestBitwise(t *testing.T) {
+	x := new(Int)
+	y := new(Int)
+	for _, test := range bitwiseTests {
+		x.SetString(test.x, 0)
+		y.SetString(test.y, 0)
+
+		testBitFun(t, "and", (*Int).And, x, y, test.and)
+		testBitFunSelf(t, "and", (*Int).And, x, y, test.and)
+		testBitFun(t, "andNot", (*Int).AndNot, x, y, test.andNot)
+		testBitFunSelf(t, "andNot", (*Int).AndNot, x, y, test.andNot)
+		testBitFun(t, "or", (*Int).Or, x, y, test.or)
+		testBitFunSelf(t, "or", (*Int).Or, x, y, test.or)
+		testBitFun(t, "xor", (*Int).Xor, x, y, test.xor)
+		testBitFunSelf(t, "xor", (*Int).Xor, x, y, test.xor)
+	}
+}
+
+
+var notTests = []struct {
+	in  string
+	out string
+}{
+	{"0", "-1"},
+	{"1", "-2"},
+	{"7", "-8"},
+	{"0", "-1"},
+	{"-81910", "81909"},
+	{
+		"298472983472983471903246121093472394872319615612417471234712061",
+		"-298472983472983471903246121093472394872319615612417471234712062",
+	},
+}
+
+func TestNot(t *testing.T) {
+	in := new(Int)
+	out := new(Int)
+	expected := new(Int)
+	for i, test := range notTests {
+		in.SetString(test.in, 10)
+		expected.SetString(test.out, 10)
+		out = out.Not(in)
+		if out.Cmp(expected) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, expected)
+		}
+		out = out.Not(out)
+		if out.Cmp(in) != 0 {
+			t.Errorf("#%d: got %s want %s", i, out, in)
+		}
+	}
+}
+
+
+var modInverseTests = []struct {
+	element string
+	prime   string
+}{
+	{"1", "7"},
+	{"1", "13"},
+	{"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
+}
+
+func TestModInverse(t *testing.T) {
+	var element, prime Int
+	one := NewInt(1)
+	for i, test := range modInverseTests {
+		(&element).SetString(test.element, 10)
+		(&prime).SetString(test.prime, 10)
+		inverse := new(Int).ModInverse(&element, &prime)
+		inverse.Mul(inverse, &element)
+		inverse.Mod(inverse, &prime)
+		if inverse.Cmp(one) != 0 {
+			t.Errorf("#%d: failed (e·e^(-1)=%s)", i, inverse)
+		}
+	}
+}
diff --git a/libgo/go/big/nat.go b/libgo/go/big/nat.go
new file mode 100644
index 000000000..a308f69e8
--- /dev/null
+++ b/libgo/go/big/nat.go
@@ -0,0 +1,1067 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file contains operations on unsigned multi-precision integers.
+// These are the building blocks for the operations on signed integers
+// and rationals.
+
+// This package implements multi-precision arithmetic (big numbers).
+// The following numeric types are supported:
+//
+//	- Int	signed integers
+//	- Rat	rational numbers
+//
+// All methods on Int take the result as the receiver; if it is one
+// of the operands it may be overwritten (and its memory reused).
+// To enable chaining of operations, the result is also returned.
+//
+package big
+
+import "rand"
+
+// An unsigned integer x of the form
+//
+//   x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]
+//
+// with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n,
+// with the digits x[i] as the slice elements.
+//
+// A number is normalized if the slice contains no leading 0 digits.
+// During arithmetic operations, denormalized values may occur but are
+// always normalized before returning the final result. The normalized
+// representation of 0 is the empty or nil slice (length = 0).
+
+type nat []Word
+
+var (
+	natOne = nat{1}
+	natTwo = nat{2}
+	natTen = nat{10}
+)
+
+
+func (z nat) clear() {
+	for i := range z {
+		z[i] = 0
+	}
+}
+
+
+func (z nat) norm() nat {
+	i := len(z)
+	for i > 0 && z[i-1] == 0 {
+		i--
+	}
+	return z[0:i]
+}
+
+
+func (z nat) make(n int) nat {
+	if n <= cap(z) {
+		return z[0:n] // reuse z
+	}
+	// Choosing a good value for e has significant performance impact
+	// because it increases the chance that a value can be reused.
+	const e = 4 // extra capacity
+	return make(nat, n, n+e)
+}
+
+
+func (z nat) setWord(x Word) nat {
+	if x == 0 {
+		return z.make(0)
+	}
+	z = z.make(1)
+	z[0] = x
+	return z
+}
+
+
+func (z nat) setUint64(x uint64) nat {
+	// single-digit values
+	if w := Word(x); uint64(w) == x {
+		return z.setWord(w)
+	}
+
+	// compute number of words n required to represent x
+	n := 0
+	for t := x; t > 0; t >>= _W {
+		n++
+	}
+
+	// split x into n words
+	z = z.make(n)
+	for i := range z {
+		z[i] = Word(x & _M)
+		x >>= _W
+	}
+
+	return z
+}
+
+
+func (z nat) set(x nat) nat {
+	z = z.make(len(x))
+	copy(z, x)
+	return z
+}
+
+
+func (z nat) add(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+
+	switch {
+	case m < n:
+		return z.add(y, x)
+	case m == 0:
+		// n == 0 because m >= n; result is 0
+		return z.make(0)
+	case n == 0:
+		// result is x
+		return z.set(x)
+	}
+	// m > 0
+
+	z = z.make(m + 1)
+	c := addVV(z[0:n], x, y)
+	if m > n {
+		c = addVW(z[n:m], x[n:], c)
+	}
+	z[m] = c
+
+	return z.norm()
+}
+
+
+func (z nat) sub(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+
+	switch {
+	case m < n:
+		panic("underflow")
+	case m == 0:
+		// n == 0 because m >= n; result is 0
+		return z.make(0)
+	case n == 0:
+		// result is x
+		return z.set(x)
+	}
+	// m > 0
+
+	z = z.make(m)
+	c := subVV(z[0:n], x, y)
+	if m > n {
+		c = subVW(z[n:], x[n:], c)
+	}
+	if c != 0 {
+		panic("underflow")
+	}
+
+	return z.norm()
+}
+
+
+func (x nat) cmp(y nat) (r int) {
+	m := len(x)
+	n := len(y)
+	if m != n || m == 0 {
+		switch {
+		case m < n:
+			r = -1
+		case m > n:
+			r = 1
+		}
+		return
+	}
+
+	i := m - 1
+	for i > 0 && x[i] == y[i] {
+		i--
+	}
+
+	switch {
+	case x[i] < y[i]:
+		r = -1
+	case x[i] > y[i]:
+		r = 1
+	}
+	return
+}
+
+
+func (z nat) mulAddWW(x nat, y, r Word) nat {
+	m := len(x)
+	if m == 0 || y == 0 {
+		return z.setWord(r) // result is r
+	}
+	// m > 0
+
+	z = z.make(m + 1)
+	z[m] = mulAddVWW(z[0:m], x, y, r)
+
+	return z.norm()
+}
+
+
+// basicMul multiplies x and y and leaves the result in z.
+// The (non-normalized) result is placed in z[0 : len(x) + len(y)].
+func basicMul(z, x, y nat) {
+	z[0 : len(x)+len(y)].clear() // initialize z
+	for i, d := range y {
+		if d != 0 {
+			z[len(x)+i] = addMulVVW(z[i:i+len(x)], x, d)
+		}
+	}
+}
+
+
+// Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks.
+// Factored out for readability - do not use outside karatsuba.
+func karatsubaAdd(z, x nat, n int) {
+	if c := addVV(z[0:n], z, x); c != 0 {
+		addVW(z[n:n+n>>1], z[n:], c)
+	}
+}
+
+
+// Like karatsubaAdd, but does subtract.
+func karatsubaSub(z, x nat, n int) {
+	if c := subVV(z[0:n], z, x); c != 0 {
+		subVW(z[n:n+n>>1], z[n:], c)
+	}
+}
+
+
+// Operands that are shorter than karatsubaThreshold are multiplied using
+// "grade school" multiplication; for longer operands the Karatsuba algorithm
+// is used.
+var karatsubaThreshold int = 32 // computed by calibrate.go
+
+// karatsuba multiplies x and y and leaves the result in z.
+// Both x and y must have the same length n and n must be a
+// power of 2. The result vector z must have len(z) >= 6*n.
+// The (non-normalized) result is placed in z[0 : 2*n].
+func karatsuba(z, x, y nat) {
+	n := len(y)
+
+	// Switch to basic multiplication if numbers are odd or small.
+	// (n is always even if karatsubaThreshold is even, but be
+	// conservative)
+	if n&1 != 0 || n < karatsubaThreshold || n < 2 {
+		basicMul(z, x, y)
+		return
+	}
+	// n&1 == 0 && n >= karatsubaThreshold && n >= 2
+
+	// Karatsuba multiplication is based on the observation that
+	// for two numbers x and y with:
+	//
+	//   x = x1*b + x0
+	//   y = y1*b + y0
+	//
+	// the product x*y can be obtained with 3 products z2, z1, z0
+	// instead of 4:
+	//
+	//   x*y = x1*y1*b*b + (x1*y0 + x0*y1)*b + x0*y0
+	//       =    z2*b*b +              z1*b +    z0
+	//
+	// with:
+	//
+	//   xd = x1 - x0
+	//   yd = y0 - y1
+	//
+	//   z1 =      xd*yd                    + z1 + z0
+	//      = (x1-x0)*(y0 - y1)             + z1 + z0
+	//      = x1*y0 - x1*y1 - x0*y0 + x0*y1 + z1 + z0
+	//      = x1*y0 -    z1 -    z0 + x0*y1 + z1 + z0
+	//      = x1*y0                 + x0*y1
+
+	// split x, y into "digits"
+	n2 := n >> 1              // n2 >= 1
+	x1, x0 := x[n2:], x[0:n2] // x = x1*b + y0
+	y1, y0 := y[n2:], y[0:n2] // y = y1*b + y0
+
+	// z is used for the result and temporary storage:
+	//
+	//   6*n     5*n     4*n     3*n     2*n     1*n     0*n
+	// z = [z2 copy|z0 copy| xd*yd | yd:xd | x1*y1 | x0*y0 ]
+	//
+	// For each recursive call of karatsuba, an unused slice of
+	// z is passed in that has (at least) half the length of the
+	// caller's z.
+
+	// compute z0 and z2 with the result "in place" in z
+	karatsuba(z, x0, y0)     // z0 = x0*y0
+	karatsuba(z[n:], x1, y1) // z2 = x1*y1
+
+	// compute xd (or the negative value if underflow occurs)
+	s := 1 // sign of product xd*yd
+	xd := z[2*n : 2*n+n2]
+	if subVV(xd, x1, x0) != 0 { // x1-x0
+		s = -s
+		subVV(xd, x0, x1) // x0-x1
+	}
+
+	// compute yd (or the negative value if underflow occurs)
+	yd := z[2*n+n2 : 3*n]
+	if subVV(yd, y0, y1) != 0 { // y0-y1
+		s = -s
+		subVV(yd, y1, y0) // y1-y0
+	}
+
+	// p = (x1-x0)*(y0-y1) == x1*y0 - x1*y1 - x0*y0 + x0*y1 for s > 0
+	// p = (x0-x1)*(y0-y1) == x0*y0 - x0*y1 - x1*y0 + x1*y1 for s < 0
+	p := z[n*3:]
+	karatsuba(p, xd, yd)
+
+	// save original z2:z0
+	// (ok to use upper half of z since we're done recursing)
+	r := z[n*4:]
+	copy(r, z)
+
+	// add up all partial products
+	//
+	//   2*n     n     0
+	// z = [ z2  | z0  ]
+	//   +    [ z0  ]
+	//   +    [ z2  ]
+	//   +    [  p  ]
+	//
+	karatsubaAdd(z[n2:], r, n)
+	karatsubaAdd(z[n2:], r[n:], n)
+	if s > 0 {
+		karatsubaAdd(z[n2:], p, n)
+	} else {
+		karatsubaSub(z[n2:], p, n)
+	}
+}
+
+
+// alias returns true if x and y share the same base array.
+func alias(x, y nat) bool {
+	return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
+}
+
+
+// addAt implements z += x*(1<<(_W*i)); z must be long enough.
+// (we don't use nat.add because we need z to stay the same
+// slice, and we don't need to normalize z after each addition)
+func addAt(z, x nat, i int) {
+	if n := len(x); n > 0 {
+		if c := addVV(z[i:i+n], z[i:], x); c != 0 {
+			j := i + n
+			if j < len(z) {
+				addVW(z[j:], z[j:], c)
+			}
+		}
+	}
+}
+
+
+func max(x, y int) int {
+	if x > y {
+		return x
+	}
+	return y
+}
+
+
+// karatsubaLen computes an approximation to the maximum k <= n such that
+// k = p<<i for a number p <= karatsubaThreshold and an i >= 0. Thus, the
+// result is the largest number that can be divided repeatedly by 2 before
+// becoming about the value of karatsubaThreshold.
+func karatsubaLen(n int) int {
+	i := uint(0)
+	for n > karatsubaThreshold {
+		n >>= 1
+		i++
+	}
+	return n << i
+}
+
+
+func (z nat) mul(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+
+	switch {
+	case m < n:
+		return z.mul(y, x)
+	case m == 0 || n == 0:
+		return z.make(0)
+	case n == 1:
+		return z.mulAddWW(x, y[0], 0)
+	}
+	// m >= n > 1
+
+	// determine if z can be reused
+	if alias(z, x) || alias(z, y) {
+		z = nil // z is an alias for x or y - cannot reuse
+	}
+
+	// use basic multiplication if the numbers are small
+	if n < karatsubaThreshold || n < 2 {
+		z = z.make(m + n)
+		basicMul(z, x, y)
+		return z.norm()
+	}
+	// m >= n && n >= karatsubaThreshold && n >= 2
+
+	// determine Karatsuba length k such that
+	//
+	//   x = x1*b + x0
+	//   y = y1*b + y0  (and k <= len(y), which implies k <= len(x))
+	//   b = 1<<(_W*k)  ("base" of digits xi, yi)
+	//
+	k := karatsubaLen(n)
+	// k <= n
+
+	// multiply x0 and y0 via Karatsuba
+	x0 := x[0:k]              // x0 is not normalized
+	y0 := y[0:k]              // y0 is not normalized
+	z = z.make(max(6*k, m+n)) // enough space for karatsuba of x0*y0 and full result of x*y
+	karatsuba(z, x0, y0)
+	z = z[0 : m+n] // z has final length but may be incomplete, upper portion is garbage
+
+	// If x1 and/or y1 are not 0, add missing terms to z explicitly:
+	//
+	//     m+n       2*k       0
+	//   z = [   ...   | x0*y0 ]
+	//     +   [ x1*y1 ]
+	//     +   [ x1*y0 ]
+	//     +   [ x0*y1 ]
+	//
+	if k < n || m != n {
+		x1 := x[k:] // x1 is normalized because x is
+		y1 := y[k:] // y1 is normalized because y is
+		var t nat
+		t = t.mul(x1, y1)
+		copy(z[2*k:], t)
+		z[2*k+len(t):].clear() // upper portion of z is garbage
+		t = t.mul(x1, y0.norm())
+		addAt(z, t, k)
+		t = t.mul(x0.norm(), y1)
+		addAt(z, t, k)
+	}
+
+	return z.norm()
+}
+
+
+// mulRange computes the product of all the unsigned integers in the
+// range [a, b] inclusively. If a > b (empty range), the result is 1.
+func (z nat) mulRange(a, b uint64) nat {
+	switch {
+	case a == 0:
+		// cut long ranges short (optimization)
+		return z.setUint64(0)
+	case a > b:
+		return z.setUint64(1)
+	case a == b:
+		return z.setUint64(a)
+	case a+1 == b:
+		return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b))
+	}
+	m := (a + b) / 2
+	return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
+}
+
+
+// q = (x-r)/y, with 0 <= r < y
+func (z nat) divW(x nat, y Word) (q nat, r Word) {
+	m := len(x)
+	switch {
+	case y == 0:
+		panic("division by zero")
+	case y == 1:
+		q = z.set(x) // result is x
+		return
+	case m == 0:
+		q = z.make(0) // result is 0
+		return
+	}
+	// m > 0
+	z = z.make(m)
+	r = divWVW(z, 0, x, y)
+	q = z.norm()
+	return
+}
+
+
+func (z nat) div(z2, u, v nat) (q, r nat) {
+	if len(v) == 0 {
+		panic("division by zero")
+	}
+
+	if u.cmp(v) < 0 {
+		q = z.make(0)
+		r = z2.set(u)
+		return
+	}
+
+	if len(v) == 1 {
+		var rprime Word
+		q, rprime = z.divW(u, v[0])
+		if rprime > 0 {
+			r = z2.make(1)
+			r[0] = rprime
+		} else {
+			r = z2.make(0)
+		}
+		return
+	}
+
+	q, r = z.divLarge(z2, u, v)
+	return
+}
+
+
+// q = (uIn-r)/v, with 0 <= r < y
+// Uses z as storage for q, and u as storage for r if possible.
+// See Knuth, Volume 2, section 4.3.1, Algorithm D.
+// Preconditions:
+//    len(v) >= 2
+//    len(uIn) >= len(v)
+func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
+	n := len(v)
+	m := len(uIn) - n
+
+	// determine if z can be reused
+	// TODO(gri) should find a better solution - this if statement
+	//           is very costly (see e.g. time pidigits -s -n 10000)
+	if alias(z, uIn) || alias(z, v) {
+		z = nil // z is an alias for uIn or v - cannot reuse
+	}
+	q = z.make(m + 1)
+
+	qhatv := make(nat, n+1)
+	if alias(u, uIn) || alias(u, v) {
+		u = nil // u is an alias for uIn or v - cannot reuse
+	}
+	u = u.make(len(uIn) + 1)
+	u.clear()
+
+	// D1.
+	shift := Word(leadingZeros(v[n-1]))
+	shlVW(v, v, shift)
+	u[len(uIn)] = shlVW(u[0:len(uIn)], uIn, shift)
+
+	// D2.
+	for j := m; j >= 0; j-- {
+		// D3.
+		qhat := Word(_M)
+		if u[j+n] != v[n-1] {
+			var rhat Word
+			qhat, rhat = divWW(u[j+n], u[j+n-1], v[n-1])
+
+			// x1 | x2 = q̂v_{n-2}
+			x1, x2 := mulWW(qhat, v[n-2])
+			// test if q̂v_{n-2} > br̂ + u_{j+n-2}
+			for greaterThan(x1, x2, rhat, u[j+n-2]) {
+				qhat--
+				prevRhat := rhat
+				rhat += v[n-1]
+				// v[n-1] >= 0, so this tests for overflow.
+				if rhat < prevRhat {
+					break
+				}
+				x1, x2 = mulWW(qhat, v[n-2])
+			}
+		}
+
+		// D4.
+		qhatv[n] = mulAddVWW(qhatv[0:n], v, qhat, 0)
+
+		c := subVV(u[j:j+len(qhatv)], u[j:], qhatv)
+		if c != 0 {
+			c := addVV(u[j:j+n], u[j:], v)
+			u[j+n] += c
+			qhat--
+		}
+
+		q[j] = qhat
+	}
+
+	q = q.norm()
+	shrVW(u, u, shift)
+	shrVW(v, v, shift)
+	r = u.norm()
+
+	return q, r
+}
+
+
+// Length of x in bits. x must be normalized.
+func (x nat) bitLen() int {
+	if i := len(x) - 1; i >= 0 {
+		return i*_W + bitLen(x[i])
+	}
+	return 0
+}
+
+
+func hexValue(ch byte) int {
+	var d byte
+	switch {
+	case '0' <= ch && ch <= '9':
+		d = ch - '0'
+	case 'a' <= ch && ch <= 'f':
+		d = ch - 'a' + 10
+	case 'A' <= ch && ch <= 'F':
+		d = ch - 'A' + 10
+	default:
+		return -1
+	}
+	return int(d)
+}
+
+
+// scan returns the natural number corresponding to the
+// longest possible prefix of s representing a natural number in a
+// given conversion base, the actual conversion base used, and the
+// prefix length. The syntax of natural numbers follows the syntax
+// of unsigned integer literals in Go.
+//
+// If the base argument is 0, the string prefix determines the actual
+// conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the
+// ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects
+// base 2. Otherwise the selected base is 10.
+//
+func (z nat) scan(s string, base int) (nat, int, int) {
+	// determine base if necessary
+	i, n := 0, len(s)
+	if base == 0 {
+		base = 10
+		if n > 0 && s[0] == '0' {
+			base, i = 8, 1
+			if n > 1 {
+				switch s[1] {
+				case 'x', 'X':
+					base, i = 16, 2
+				case 'b', 'B':
+					base, i = 2, 2
+				}
+			}
+		}
+	}
+
+	// reject illegal bases or strings consisting only of prefix
+	if base < 2 || 16 < base || (base != 8 && i >= n) {
+		return z, 0, 0
+	}
+
+	// convert string
+	z = z.make(0)
+	for ; i < n; i++ {
+		d := hexValue(s[i])
+		if 0 <= d && d < base {
+			z = z.mulAddWW(z, Word(base), Word(d))
+		} else {
+			break
+		}
+	}
+
+	return z.norm(), base, i
+}
+
+
+// string converts x to a string for a given base, with 2 <= base <= 16.
+// TODO(gri) in the style of the other routines, perhaps this should take
+//           a []byte buffer and return it
+func (x nat) string(base int) string {
+	if base < 2 || 16 < base {
+		panic("illegal base")
+	}
+
+	if len(x) == 0 {
+		return "0"
+	}
+
+	// allocate buffer for conversion
+	i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
+	s := make([]byte, i)
+
+	// don't destroy x
+	q := nat(nil).set(x)
+
+	// convert
+	for len(q) > 0 {
+		i--
+		var r Word
+		q, r = q.divW(q, Word(base))
+		s[i] = "0123456789abcdef"[r]
+	}
+
+	return string(s[i:])
+}
+
+
+const deBruijn32 = 0x077CB531
+
+var deBruijn32Lookup = []byte{
+	0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+	31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
+}
+
+const deBruijn64 = 0x03f79d71b4ca8b09
+
+var deBruijn64Lookup = []byte{
+	0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
+	62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
+	63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
+	54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
+}
+
+// trailingZeroBits returns the number of consecutive zero bits on the right
+// side of the given Word.
+// See Knuth, volume 4, section 7.3.1
+func trailingZeroBits(x Word) int {
+	// x & -x leaves only the right-most bit set in the word. Let k be the
+	// index of that bit. Since only a single bit is set, the value is two
+	// to the power of k. Multipling by a power of two is equivalent to
+	// left shifting, in this case by k bits.  The de Bruijn constant is
+	// such that all six bit, consecutive substrings are distinct.
+	// Therefore, if we have a left shifted version of this constant we can
+	// find by how many bits it was shifted by looking at which six bit
+	// substring ended up at the top of the word.
+	switch _W {
+	case 32:
+		return int(deBruijn32Lookup[((x&-x)*deBruijn32)>>27])
+	case 64:
+		return int(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58])
+	default:
+		panic("Unknown word size")
+	}
+
+	return 0
+}
+
+
+// z = x << s
+func (z nat) shl(x nat, s uint) nat {
+	m := len(x)
+	if m == 0 {
+		return z.make(0)
+	}
+	// m > 0
+
+	n := m + int(s/_W)
+	z = z.make(n + 1)
+	z[n] = shlVW(z[n-m:n], x, Word(s%_W))
+	z[0 : n-m].clear()
+
+	return z.norm()
+}
+
+
+// z = x >> s
+func (z nat) shr(x nat, s uint) nat {
+	m := len(x)
+	n := m - int(s/_W)
+	if n <= 0 {
+		return z.make(0)
+	}
+	// n > 0
+
+	z = z.make(n)
+	shrVW(z, x[m-n:], Word(s%_W))
+
+	return z.norm()
+}
+
+
+func (z nat) and(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+	if m > n {
+		m = n
+	}
+	// m <= n
+
+	z = z.make(m)
+	for i := 0; i < m; i++ {
+		z[i] = x[i] & y[i]
+	}
+
+	return z.norm()
+}
+
+
+func (z nat) andNot(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+	if n > m {
+		n = m
+	}
+	// m >= n
+
+	z = z.make(m)
+	for i := 0; i < n; i++ {
+		z[i] = x[i] &^ y[i]
+	}
+	copy(z[n:m], x[n:m])
+
+	return z.norm()
+}
+
+
+func (z nat) or(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+	s := x
+	if m < n {
+		n, m = m, n
+		s = y
+	}
+	// m >= n
+
+	z = z.make(m)
+	for i := 0; i < n; i++ {
+		z[i] = x[i] | y[i]
+	}
+	copy(z[n:m], s[n:m])
+
+	return z.norm()
+}
+
+
+func (z nat) xor(x, y nat) nat {
+	m := len(x)
+	n := len(y)
+	s := x
+	if m < n {
+		n, m = m, n
+		s = y
+	}
+	// m >= n
+
+	z = z.make(m)
+	for i := 0; i < n; i++ {
+		z[i] = x[i] ^ y[i]
+	}
+	copy(z[n:m], s[n:m])
+
+	return z.norm()
+}
+
+
+// greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
+func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 || x1 == y1 && x2 > y2 }
+
+
+// modW returns x % d.
+func (x nat) modW(d Word) (r Word) {
+	// TODO(agl): we don't actually need to store the q value.
+	var q nat
+	q = q.make(len(x))
+	return divWVW(q, 0, x, d)
+}
+
+
+// powersOfTwoDecompose finds q and k such that q * 1<<k = n and q is odd.
+func (n nat) powersOfTwoDecompose() (q nat, k Word) {
+	if len(n) == 0 {
+		return n, 0
+	}
+
+	zeroWords := 0
+	for n[zeroWords] == 0 {
+		zeroWords++
+	}
+	// One of the words must be non-zero by invariant, therefore
+	// zeroWords < len(n).
+	x := trailingZeroBits(n[zeroWords])
+
+	q = q.make(len(n) - zeroWords)
+	shrVW(q, n[zeroWords:], Word(x))
+	q = q.norm()
+
+	k = Word(_W*zeroWords + x)
+	return
+}
+
+
+// random creates a random integer in [0..limit), using the space in z if
+// possible. n is the bit length of limit.
+func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
+	bitLengthOfMSW := uint(n % _W)
+	if bitLengthOfMSW == 0 {
+		bitLengthOfMSW = _W
+	}
+	mask := Word((1 << bitLengthOfMSW) - 1)
+	z = z.make(len(limit))
+
+	for {
+		for i := range z {
+			switch _W {
+			case 32:
+				z[i] = Word(rand.Uint32())
+			case 64:
+				z[i] = Word(rand.Uint32()) | Word(rand.Uint32())<<32
+			}
+		}
+
+		z[len(limit)-1] &= mask
+
+		if z.cmp(limit) < 0 {
+			break
+		}
+	}
+
+	return z.norm()
+}
+
+
+// If m != nil, expNN calculates x**y mod m. Otherwise it calculates x**y. It
+// reuses the storage of z if possible.
+func (z nat) expNN(x, y, m nat) nat {
+	if alias(z, x) || alias(z, y) {
+		// We cannot allow in place modification of x or y.
+		z = nil
+	}
+
+	if len(y) == 0 {
+		z = z.make(1)
+		z[0] = 1
+		return z
+	}
+
+	if m != nil {
+		// We likely end up being as long as the modulus.
+		z = z.make(len(m))
+	}
+	z = z.set(x)
+	v := y[len(y)-1]
+	// It's invalid for the most significant word to be zero, therefore we
+	// will find a one bit.
+	shift := leadingZeros(v) + 1
+	v <<= shift
+	var q nat
+
+	const mask = 1 << (_W - 1)
+
+	// We walk through the bits of the exponent one by one. Each time we
+	// see a bit, we square, thus doubling the power. If the bit is a one,
+	// we also multiply by x, thus adding one to the power.
+
+	w := _W - int(shift)
+	for j := 0; j < w; j++ {
+		z = z.mul(z, z)
+
+		if v&mask != 0 {
+			z = z.mul(z, x)
+		}
+
+		if m != nil {
+			q, z = q.div(z, z, m)
+		}
+
+		v <<= 1
+	}
+
+	for i := len(y) - 2; i >= 0; i-- {
+		v = y[i]
+
+		for j := 0; j < _W; j++ {
+			z = z.mul(z, z)
+
+			if v&mask != 0 {
+				z = z.mul(z, x)
+			}
+
+			if m != nil {
+				q, z = q.div(z, z, m)
+			}
+
+			v <<= 1
+		}
+	}
+
+	return z
+}
+
+
+// probablyPrime performs reps Miller-Rabin tests to check whether n is prime.
+// If it returns true, n is prime with probability 1 - 1/4^reps.
+// If it returns false, n is not prime.
+func (n nat) probablyPrime(reps int) bool {
+	if len(n) == 0 {
+		return false
+	}
+
+	if len(n) == 1 {
+		if n[0] < 2 {
+			return false
+		}
+
+		if n[0]%2 == 0 {
+			return n[0] == 2
+		}
+
+		// We have to exclude these cases because we reject all
+		// multiples of these numbers below.
+		switch n[0] {
+		case 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53:
+			return true
+		}
+	}
+
+	const primesProduct32 = 0xC0CFD797         // Π {p ∈ primes, 2 < p <= 29}
+	const primesProduct64 = 0xE221F97C30E94E1D // Π {p ∈ primes, 2 < p <= 53}
+
+	var r Word
+	switch _W {
+	case 32:
+		r = n.modW(primesProduct32)
+	case 64:
+		r = n.modW(primesProduct64 & _M)
+	default:
+		panic("Unknown word size")
+	}
+
+	if r%3 == 0 || r%5 == 0 || r%7 == 0 || r%11 == 0 ||
+		r%13 == 0 || r%17 == 0 || r%19 == 0 || r%23 == 0 || r%29 == 0 {
+		return false
+	}
+
+	if _W == 64 && (r%31 == 0 || r%37 == 0 || r%41 == 0 ||
+		r%43 == 0 || r%47 == 0 || r%53 == 0) {
+		return false
+	}
+
+	nm1 := nat(nil).sub(n, natOne)
+	// 1<<k * q = nm1;
+	q, k := nm1.powersOfTwoDecompose()
+
+	nm3 := nat(nil).sub(nm1, natTwo)
+	rand := rand.New(rand.NewSource(int64(n[0])))
+
+	var x, y, quotient nat
+	nm3Len := nm3.bitLen()
+
+NextRandom:
+	for i := 0; i < reps; i++ {
+		x = x.random(rand, nm3, nm3Len)
+		x = x.add(x, natTwo)
+		y = y.expNN(x, q, n)
+		if y.cmp(natOne) == 0 || y.cmp(nm1) == 0 {
+			continue
+		}
+		for j := Word(1); j < k; j++ {
+			y = y.mul(y, y)
+			quotient, y = quotient.div(y, y, n)
+			if y.cmp(nm1) == 0 {
+				continue NextRandom
+			}
+			if y.cmp(natOne) == 0 {
+				return false
+			}
+		}
+		return false
+	}
+
+	return true
+}
diff --git a/libgo/go/big/nat_test.go b/libgo/go/big/nat_test.go
new file mode 100644
index 000000000..0bcb94554
--- /dev/null
+++ b/libgo/go/big/nat_test.go
@@ -0,0 +1,358 @@
+// Copyright 2009 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package big
+
+import "testing"
+
+var cmpTests = []struct {
+	x, y nat
+	r    int
+}{
+	{nil, nil, 0},
+	{nil, nat{}, 0},
+	{nat{}, nil, 0},
+	{nat{}, nat{}, 0},
+	{nat{0}, nat{0}, 0},
+	{nat{0}, nat{1}, -1},
+	{nat{1}, nat{0}, 1},
+	{nat{1}, nat{1}, 0},
+	{nat{0, _M}, nat{1}, 1},
+	{nat{1}, nat{0, _M}, -1},
+	{nat{1, _M}, nat{0, _M}, 1},
+	{nat{0, _M}, nat{1, _M}, -1},
+	{nat{16, 571956, 8794, 68}, nat{837, 9146, 1, 754489}, -1},
+	{nat{34986, 41, 105, 1957}, nat{56, 7458, 104, 1957}, 1},
+}
+
+
+func TestCmp(t *testing.T) {
+	for i, a := range cmpTests {
+		r := a.x.cmp(a.y)
+		if r != a.r {
+			t.Errorf("#%d got r = %v; want %v", i, r, a.r)
+		}
+	}
+}
+
+
+type funNN func(z, x, y nat) nat
+type argNN struct {
+	z, x, y nat
+}
+
+
+var sumNN = []argNN{
+	{},
+	{nat{1}, nil, nat{1}},
+	{nat{1111111110}, nat{123456789}, nat{987654321}},
+	{nat{0, 0, 0, 1}, nil, nat{0, 0, 0, 1}},
+	{nat{0, 0, 0, 1111111110}, nat{0, 0, 0, 123456789}, nat{0, 0, 0, 987654321}},
+	{nat{0, 0, 0, 1}, nat{0, 0, _M}, nat{0, 0, 1}},
+}
+
+
+var prodNN = []argNN{
+	{},
+	{nil, nil, nil},
+	{nil, nat{991}, nil},
+	{nat{991}, nat{991}, nat{1}},
+	{nat{991 * 991}, nat{991}, nat{991}},
+	{nat{0, 0, 991 * 991}, nat{0, 991}, nat{0, 991}},
+	{nat{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat{1, 2, 3, 4}, nat{991}},
+	{nat{4, 11, 20, 30, 20, 11, 4}, nat{1, 2, 3, 4}, nat{4, 3, 2, 1}},
+}
+
+
+func TestSet(t *testing.T) {
+	for _, a := range sumNN {
+		z := nat(nil).set(a.z)
+		if z.cmp(a.z) != 0 {
+			t.Errorf("got z = %v; want %v", z, a.z)
+		}
+	}
+}
+
+
+func testFunNN(t *testing.T, msg string, f funNN, a argNN) {
+	z := f(nil, a.x, a.y)
+	if z.cmp(a.z) != 0 {
+		t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, z, a.z)
+	}
+}
+
+
+func TestFunNN(t *testing.T) {
+	for _, a := range sumNN {
+		arg := a
+		testFunNN(t, "add", nat.add, arg)
+
+		arg = argNN{a.z, a.y, a.x}
+		testFunNN(t, "add symmetric", nat.add, arg)
+
+		arg = argNN{a.x, a.z, a.y}
+		testFunNN(t, "sub", nat.sub, arg)
+
+		arg = argNN{a.y, a.z, a.x}
+		testFunNN(t, "sub symmetric", nat.sub, arg)
+	}
+
+	for _, a := range prodNN {
+		arg := a
+		testFunNN(t, "mul", nat.mul, arg)
+
+		arg = argNN{a.z, a.y, a.x}
+		testFunNN(t, "mul symmetric", nat.mul, arg)
+	}
+}
+
+
+var mulRangesN = []struct {
+	a, b uint64
+	prod string
+}{
+	{0, 0, "0"},
+	{1, 1, "1"},
+	{1, 2, "2"},
+	{1, 3, "6"},
+	{10, 10, "10"},
+	{0, 100, "0"},
+	{0, 1e9, "0"},
+	{1, 0, "1"},                    // empty range
+	{100, 1, "1"},                  // empty range
+	{1, 10, "3628800"},             // 10!
+	{1, 20, "2432902008176640000"}, // 20!
+	{1, 100,
+		"933262154439441526816992388562667004907159682643816214685929" +
+			"638952175999932299156089414639761565182862536979208272237582" +
+			"51185210916864000000000000000000000000", // 100!
+	},
+}
+
+
+func TestMulRangeN(t *testing.T) {
+	for i, r := range mulRangesN {
+		prod := nat(nil).mulRange(r.a, r.b).string(10)
+		if prod != r.prod {
+			t.Errorf("#%d: got %s; want %s", i, prod, r.prod)
+		}
+	}
+}
+
+
+var mulArg, mulTmp nat
+
+func init() {
+	const n = 1000
+	mulArg = make(nat, n)
+	for i := 0; i < n; i++ {
+		mulArg[i] = _M
+	}
+}
+
+
+func benchmarkMulLoad() {
+	for j := 1; j <= 10; j++ {
+		x := mulArg[0 : j*100]
+		mulTmp.mul(x, x)
+	}
+}
+
+
+func BenchmarkMul(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		benchmarkMulLoad()
+	}
+}
+
+
+var tab = []struct {
+	x nat
+	b int
+	s string
+}{
+	{nil, 10, "0"},
+	{nat{1}, 10, "1"},
+	{nat{10}, 10, "10"},
+	{nat{1234567890}, 10, "1234567890"},
+}
+
+
+func TestString(t *testing.T) {
+	for _, a := range tab {
+		s := a.x.string(a.b)
+		if s != a.s {
+			t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
+		}
+
+		x, b, n := nat(nil).scan(a.s, a.b)
+		if x.cmp(a.x) != 0 {
+			t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
+		}
+		if b != a.b {
+			t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b)
+		}
+		if n != len(a.s) {
+			t.Errorf("scan%+v\n\tgot n = %d; want %d", a, n, len(a.s))
+		}
+	}
+}
+
+
+func TestLeadingZeros(t *testing.T) {
+	var x Word = _B >> 1
+	for i := 0; i <= _W; i++ {
+		if int(leadingZeros(x)) != i {
+			t.Errorf("failed at %x: got %d want %d", x, leadingZeros(x), i)
+		}
+		x >>= 1
+	}
+}
+
+
+type shiftTest struct {
+	in    nat
+	shift uint
+	out   nat
+}
+
+
+var leftShiftTests = []shiftTest{
+	{nil, 0, nil},
+	{nil, 1, nil},
+	{natOne, 0, natOne},
+	{natOne, 1, natTwo},
+	{nat{1 << (_W - 1)}, 1, nat{0}},
+	{nat{1 << (_W - 1), 0}, 1, nat{0, 1}},
+}
+
+
+func TestShiftLeft(t *testing.T) {
+	for i, test := range leftShiftTests {
+		var z nat
+		z = z.shl(test.in, test.shift)
+		for j, d := range test.out {
+			if j >= len(z) || z[j] != d {
+				t.Errorf("#%d: got: %v want: %v", i, z, test.out)
+				break
+			}
+		}
+	}
+}
+
+
+var rightShiftTests = []shiftTest{
+	{nil, 0, nil},
+	{nil, 1, nil},
+	{natOne, 0, natOne},
+	{natOne, 1, nil},
+	{natTwo, 1, natOne},
+	{nat{0, 1}, 1, nat{1 << (_W - 1)}},
+	{nat{2, 1, 1}, 1, nat{1<<(_W-1) + 1, 1 << (_W - 1)}},
+}
+
+
+func TestShiftRight(t *testing.T) {
+	for i, test := range rightShiftTests {
+		var z nat
+		z = z.shr(test.in, test.shift)
+		for j, d := range test.out {
+			if j >= len(z) || z[j] != d {
+				t.Errorf("#%d: got: %v want: %v", i, z, test.out)
+				break
+			}
+		}
+	}
+}
+
+
+type modWTest struct {
+	in       string
+	dividend string
+	out      string
+}
+
+
+var modWTests32 = []modWTest{
+	{"23492635982634928349238759823742", "252341", "220170"},
+}
+
+
+var modWTests64 = []modWTest{
+	{"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
+}
+
+
+func runModWTests(t *testing.T, tests []modWTest) {
+	for i, test := range tests {
+		in, _ := new(Int).SetString(test.in, 10)
+		d, _ := new(Int).SetString(test.dividend, 10)
+		out, _ := new(Int).SetString(test.out, 10)
+
+		r := in.abs.modW(d.abs[0])
+		if r != out.abs[0] {
+			t.Errorf("#%d failed: got %s want %s", i, r, out)
+		}
+	}
+}
+
+
+func TestModW(t *testing.T) {
+	if _W >= 32 {
+		runModWTests(t, modWTests32)
+	}
+	if _W >= 64 {
+		runModWTests(t, modWTests64)
+	}
+}
+
+
+func TestTrailingZeroBits(t *testing.T) {
+	var x Word
+	x--
+	for i := 0; i < _W; i++ {
+		if trailingZeroBits(x) != i {
+			t.Errorf("Failed at step %d: x: %x got: %d", i, x, trailingZeroBits(x))
+		}
+		x <<= 1
+	}
+}
+
+
+var expNNTests = []struct {
+	x, y, m string
+	out     string
+}{
+	{"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
+	{"0x8000000000000000", "2", "6719", "4944"},
+	{"0x8000000000000000", "3", "6719", "5447"},
+	{"0x8000000000000000", "1000", "6719", "1603"},
+	{"0x8000000000000000", "1000000", "6719", "3199"},
+	{
+		"2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
+		"298472983472983471903246121093472394872319615612417471234712061",
+		"29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
+		"23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
+	},
+}
+
+
+func TestExpNN(t *testing.T) {
+	for i, test := range expNNTests {
+		x, _, _ := nat(nil).scan(test.x, 0)
+		y, _, _ := nat(nil).scan(test.y, 0)
+		out, _, _ := nat(nil).scan(test.out, 0)
+
+		var m nat
+
+		if len(test.m) > 0 {
+			m, _, _ = nat(nil).scan(test.m, 0)
+		}
+
+		z := nat(nil).expNN(x, y, m)
+		if z.cmp(out) != 0 {
+			t.Errorf("#%d got %v want %v", i, z, out)
+		}
+	}
+}
diff --git a/libgo/go/big/rat.go b/libgo/go/big/rat.go
new file mode 100644
index 000000000..e70673a1c
--- /dev/null
+++ b/libgo/go/big/rat.go
@@ -0,0 +1,326 @@
+// Copyright 2010 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file implements multi-precision rational numbers.
+
+package big
+
+import "strings"
+
+// A Rat represents a quotient a/b of arbitrary precision. The zero value for
+// a Rat, 0/0, is not a legal Rat.
+type Rat struct {
+	a Int
+	b nat
+}
+
+
+// NewRat creates a new Rat with numerator a and denominator b.
+func NewRat(a, b int64) *Rat {
+	return new(Rat).SetFrac64(a, b)
+}
+
+
+// SetFrac sets z to a/b and returns z.
+func (z *Rat) SetFrac(a, b *Int) *Rat {
+	z.a.Set(a)
+	z.a.neg = a.neg != b.neg
+	z.b = z.b.set(b.abs)
+	return z.norm()
+}
+
+
+// SetFrac64 sets z to a/b and returns z.
+func (z *Rat) SetFrac64(a, b int64) *Rat {
+	z.a.SetInt64(a)
+	if b < 0 {
+		b = -b
+		z.a.neg = !z.a.neg
+	}
+	z.b = z.b.setUint64(uint64(b))
+	return z.norm()
+}
+
+
+// SetInt sets z to x (by making a copy of x) and returns z.
+func (z *Rat) SetInt(x *Int) *Rat {
+	z.a.Set(x)
+	z.b = z.b.setWord(1)
+	return z
+}
+
+
+// SetInt64 sets z to x and returns z.
+func (z *Rat) SetInt64(x int64) *Rat {
+	z.a.SetInt64(x)
+	z.b = z.b.setWord(1)
+	return z
+}
+
+
+// Sign returns:
+//
+//	-1 if x <  0
+//	 0 if x == 0
+//	+1 if x >  0
+//
+func (x *Rat) Sign() int {
+	return x.a.Sign()
+}
+
+
+// IsInt returns true if the denominator of x is 1.
+func (x *Rat) IsInt() bool {
+	return len(x.b) == 1 && x.b[0] == 1
+}
+
+
+// Num returns the numerator of z; it may be <= 0.
+// The result is a reference to z's numerator; it
+// may change if a new value is assigned to z.
+func (z *Rat) Num() *Int {
+	return &z.a
+}
+
+
+// Demom returns the denominator of z; it is always > 0.
+// The result is a reference to z's denominator; it
+// may change if a new value is assigned to z.
+func (z *Rat) Denom() *Int {
+	return &Int{false, z.b}
+}
+
+
+func gcd(x, y nat) nat {
+	// Euclidean algorithm.
+	var a, b nat
+	a = a.set(x)
+	b = b.set(y)
+	for len(b) != 0 {
+		var q, r nat
+		_, r = q.div(r, a, b)
+		a = b
+		b = r
+	}
+	return a
+}
+
+
+func (z *Rat) norm() *Rat {
+	f := gcd(z.a.abs, z.b)
+	if len(z.a.abs) == 0 {
+		// z == 0
+		z.a.neg = false // normalize sign
+		z.b = z.b.setWord(1)
+		return z
+	}
+	if f.cmp(natOne) != 0 {
+		z.a.abs, _ = z.a.abs.div(nil, z.a.abs, f)
+		z.b, _ = z.b.div(nil, z.b, f)
+	}
+	return z
+}
+
+
+func mulNat(x *Int, y nat) *Int {
+	var z Int
+	z.abs = z.abs.mul(x.abs, y)
+	z.neg = len(z.abs) > 0 && x.neg
+	return &z
+}
+
+
+// Cmp compares x and y and returns:
+//
+//   -1 if x <  y
+//    0 if x == y
+//   +1 if x >  y
+//
+func (x *Rat) Cmp(y *Rat) (r int) {
+	return mulNat(&x.a, y.b).Cmp(mulNat(&y.a, x.b))
+}
+
+
+// Abs sets z to |x| (the absolute value of x) and returns z.
+func (z *Rat) Abs(x *Rat) *Rat {
+	z.a.Abs(&x.a)
+	z.b = z.b.set(x.b)
+	return z
+}
+
+
+// Add sets z to the sum x+y and returns z.
+func (z *Rat) Add(x, y *Rat) *Rat {
+	a1 := mulNat(&x.a, y.b)
+	a2 := mulNat(&y.a, x.b)
+	z.a.Add(a1, a2)
+	z.b = z.b.mul(x.b, y.b)
+	return z.norm()
+}
+
+
+// Sub sets z to the difference x-y and returns z.
+func (z *Rat) Sub(x, y *Rat) *Rat {
+	a1 := mulNat(&x.a, y.b)
+	a2 := mulNat(&y.a, x.b)
+	z.a.Sub(a1, a2)
+	z.b = z.b.mul(x.b, y.b)
+	return z.norm()
+}
+
+
+// Mul sets z to the product x*y and returns z.
+func (z *Rat) Mul(x, y *Rat) *Rat {
+	z.a.Mul(&x.a, &y.a)
+	z.b = z.b.mul(x.b, y.b)
+	return z.norm()
+}
+
+
+// Quo sets z to the quotient x/y and returns z.
+// If y == 0, a division-by-zero run-time panic occurs.
+func (z *Rat) Quo(x, y *Rat) *Rat {
+	if len(y.a.abs) == 0 {
+		panic("division by zero")
+	}
+	a := mulNat(&x.a, y.b)
+	b := mulNat(&y.a, x.b)
+	z.a.abs = a.abs
+	z.b = b.abs
+	z.a.neg = a.neg != b.neg
+	return z.norm()
+}
+
+
+// Neg sets z to -x (by making a copy of x if necessary) and returns z.
+func (z *Rat) Neg(x *Rat) *Rat {
+	z.a.Neg(&x.a)
+	z.b = z.b.set(x.b)
+	return z
+}
+
+
+// Set sets z to x (by making a copy of x if necessary) and returns z.
+func (z *Rat) Set(x *Rat) *Rat {
+	z.a.Set(&x.a)
+	z.b = z.b.set(x.b)
+	return z
+}
+
+
+// SetString sets z to the value of s and returns z and a boolean indicating
+// success. s can be given as a fraction "a/b" or as a floating-point number
+// optionally followed by an exponent. If the operation failed, the value of z
+// is undefined.
+func (z *Rat) SetString(s string) (*Rat, bool) {
+	if len(s) == 0 {
+		return z, false
+	}
+
+	// check for a quotient
+	sep := strings.Index(s, "/")
+	if sep >= 0 {
+		if _, ok := z.a.SetString(s[0:sep], 10); !ok {
+			return z, false
+		}
+		s = s[sep+1:]
+		var n int
+		if z.b, _, n = z.b.scan(s, 10); n != len(s) {
+			return z, false
+		}
+		return z.norm(), true
+	}
+
+	// check for a decimal point
+	sep = strings.Index(s, ".")
+	// check for an exponent
+	e := strings.IndexAny(s, "eE")
+	var exp Int
+	if e >= 0 {
+		if e < sep {
+			// The E must come after the decimal point.
+			return z, false
+		}
+		if _, ok := exp.SetString(s[e+1:], 10); !ok {
+			return z, false
+		}
+		s = s[0:e]
+	}
+	if sep >= 0 {
+		s = s[0:sep] + s[sep+1:]
+		exp.Sub(&exp, NewInt(int64(len(s)-sep)))
+	}
+
+	if _, ok := z.a.SetString(s, 10); !ok {
+		return z, false
+	}
+	powTen := nat{}.expNN(natTen, exp.abs, nil)
+	if exp.neg {
+		z.b = powTen
+		z.norm()
+	} else {
+		z.a.abs = z.a.abs.mul(z.a.abs, powTen)
+		z.b = z.b.setWord(1)
+	}
+
+	return z, true
+}
+
+
+// String returns a string representation of z in the form "a/b" (even if b == 1).
+func (z *Rat) String() string {
+	return z.a.String() + "/" + z.b.string(10)
+}
+
+
+// RatString returns a string representation of z in the form "a/b" if b != 1,
+// and in the form "a" if b == 1.
+func (z *Rat) RatString() string {
+	if z.IsInt() {
+		return z.a.String()
+	}
+	return z.String()
+}
+
+
+// FloatString returns a string representation of z in decimal form with prec
+// digits of precision after the decimal point and the last digit rounded.
+func (z *Rat) FloatString(prec int) string {
+	if z.IsInt() {
+		return z.a.String()
+	}
+
+	q, r := nat{}.div(nat{}, z.a.abs, z.b)
+
+	p := natOne
+	if prec > 0 {
+		p = nat{}.expNN(natTen, nat{}.setUint64(uint64(prec)), nil)
+	}
+
+	r = r.mul(r, p)
+	r, r2 := r.div(nat{}, r, z.b)
+
+	// see if we need to round up
+	r2 = r2.add(r2, r2)
+	if z.b.cmp(r2) <= 0 {
+		r = r.add(r, natOne)
+		if r.cmp(p) >= 0 {
+			q = nat{}.add(q, natOne)
+			r = nat{}.sub(r, p)
+		}
+	}
+
+	s := q.string(10)
+	if z.a.neg {
+		s = "-" + s
+	}
+
+	if prec > 0 {
+		rs := r.string(10)
+		leadingZeros := prec - len(rs)
+		s += "." + strings.Repeat("0", leadingZeros) + rs
+	}
+
+	return s
+}
diff --git a/libgo/go/big/rat_test.go b/libgo/go/big/rat_test.go
new file mode 100644
index 000000000..8f42949b0
--- /dev/null
+++ b/libgo/go/big/rat_test.go
@@ -0,0 +1,282 @@
+// Copyright 2010 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package big
+
+import "testing"
+
+
+var setStringTests = []struct {
+	in, out string
+	ok      bool
+}{
+	{"0", "0", true},
+	{"-0", "0", true},
+	{"1", "1", true},
+	{"-1", "-1", true},
+	{"1.", "1", true},
+	{"1e0", "1", true},
+	{"1.e1", "10", true},
+	{in: "1e", ok: false},
+	{in: "1.e", ok: false},
+	{in: "1e+14e-5", ok: false},
+	{in: "1e4.5", ok: false},
+	{in: "r", ok: false},
+	{in: "a/b", ok: false},
+	{in: "a.b", ok: false},
+	{"-0.1", "-1/10", true},
+	{"-.1", "-1/10", true},
+	{"2/4", "1/2", true},
+	{".25", "1/4", true},
+	{"-1/5", "-1/5", true},
+	{"8129567.7690E14", "812956776900000000000", true},
+	{"78189e+4", "781890000", true},
+	{"553019.8935e+8", "55301989350000", true},
+	{"98765432109876543210987654321e-10", "98765432109876543210987654321/10000000000", true},
+	{"9877861857500000E-7", "3951144743/4", true},
+	{"2169378.417e-3", "2169378417/1000000", true},
+	{"884243222337379604041632732738665534", "884243222337379604041632732738665534", true},
+	{"53/70893980658822810696", "53/70893980658822810696", true},
+	{"106/141787961317645621392", "53/70893980658822810696", true},
+	{"204211327800791583.81095", "4084226556015831676219/20000", true},
+}
+
+func TestRatSetString(t *testing.T) {
+	for i, test := range setStringTests {
+		x, ok := new(Rat).SetString(test.in)
+
+		if ok != test.ok || ok && x.RatString() != test.out {
+			t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
+		}
+	}
+}
+
+
+var floatStringTests = []struct {
+	in   string
+	prec int
+	out  string
+}{
+	{"0", 0, "0"},
+	{"0", 4, "0"},
+	{"1", 0, "1"},
+	{"1", 2, "1"},
+	{"-1", 0, "-1"},
+	{".25", 2, "0.25"},
+	{".25", 1, "0.3"},
+	{"-1/3", 3, "-0.333"},
+	{"-2/3", 4, "-0.6667"},
+	{"0.96", 1, "1.0"},
+	{"0.999", 2, "1.00"},
+	{"0.9", 0, "1"},
+	{".25", -1, "0"},
+	{".55", -1, "1"},
+}
+
+func TestFloatString(t *testing.T) {
+	for i, test := range floatStringTests {
+		x, _ := new(Rat).SetString(test.in)
+
+		if x.FloatString(test.prec) != test.out {
+			t.Errorf("#%d got %s want %s", i, x.FloatString(test.prec), test.out)
+		}
+	}
+}
+
+
+func TestRatSign(t *testing.T) {
+	zero := NewRat(0, 1)
+	for _, a := range setStringTests {
+		var x Rat
+		x.SetString(a.in)
+		s := x.Sign()
+		e := x.Cmp(zero)
+		if s != e {
+			t.Errorf("got %d; want %d for z = %v", s, e, &x)
+		}
+	}
+}
+
+
+var ratCmpTests = []struct {
+	rat1, rat2 string
+	out        int
+}{
+	{"0", "0/1", 0},
+	{"1/1", "1", 0},
+	{"-1", "-2/2", 0},
+	{"1", "0", 1},
+	{"0/1", "1/1", -1},
+	{"-5/1434770811533343057144", "-5/1434770811533343057145", -1},
+	{"49832350382626108453/8964749413", "49832350382626108454/8964749413", -1},
+	{"-37414950961700930/7204075375675961", "37414950961700930/7204075375675961", -1},
+	{"37414950961700930/7204075375675961", "74829901923401860/14408150751351922", 0},
+}
+
+func TestRatCmp(t *testing.T) {
+	for i, test := range ratCmpTests {
+		x, _ := new(Rat).SetString(test.rat1)
+		y, _ := new(Rat).SetString(test.rat2)
+
+		out := x.Cmp(y)
+		if out != test.out {
+			t.Errorf("#%d got out = %v; want %v", i, out, test.out)
+		}
+	}
+}
+
+
+func TestIsInt(t *testing.T) {
+	one := NewInt(1)
+	for _, a := range setStringTests {
+		var x Rat
+		x.SetString(a.in)
+		i := x.IsInt()
+		e := x.Denom().Cmp(one) == 0
+		if i != e {
+			t.Errorf("got %v; want %v for z = %v", i, e, &x)
+		}
+	}
+}
+
+
+func TestRatAbs(t *testing.T) {
+	zero := NewRat(0, 1)
+	for _, a := range setStringTests {
+		var z Rat
+		z.SetString(a.in)
+		var e Rat
+		e.Set(&z)
+		if e.Cmp(zero) < 0 {
+			e.Sub(zero, &e)
+		}
+		z.Abs(&z)
+		if z.Cmp(&e) != 0 {
+			t.Errorf("got z = %v; want %v", &z, &e)
+		}
+	}
+}
+
+
+type ratBinFun func(z, x, y *Rat) *Rat
+type ratBinArg struct {
+	x, y, z string
+}
+
+func testRatBin(t *testing.T, i int, name string, f ratBinFun, a ratBinArg) {
+	x, _ := NewRat(0, 1).SetString(a.x)
+	y, _ := NewRat(0, 1).SetString(a.y)
+	z, _ := NewRat(0, 1).SetString(a.z)
+	out := f(NewRat(0, 1), x, y)
+
+	if out.Cmp(z) != 0 {
+		t.Errorf("%s #%d got %s want %s", name, i, out, z)
+	}
+}
+
+
+var ratBinTests = []struct {
+	x, y      string
+	sum, prod string
+}{
+	{"0", "0", "0", "0"},
+	{"0", "1", "1", "0"},
+	{"-1", "0", "-1", "0"},
+	{"-1", "1", "0", "-1"},
+	{"1", "1", "2", "1"},
+	{"1/2", "1/2", "1", "1/4"},
+	{"1/4", "1/3", "7/12", "1/12"},
+	{"2/5", "-14/3", "-64/15", "-28/15"},
+	{"4707/49292519774798173060", "-3367/70976135186689855734", "84058377121001851123459/1749296273614329067191168098769082663020", "-1760941/388732505247628681598037355282018369560"},
+	{"-61204110018146728334/3", "-31052192278051565633/2", "-215564796870448153567/6", "950260896245257153059642991192710872711/3"},
+	{"-854857841473707320655/4237645934602118692642972629634714039", "-18/31750379913563777419", "-27/133467566250814981", "15387441146526731771790/134546868362786310073779084329032722548987800600710485341"},
+	{"618575745270541348005638912139/19198433543745179392300736", "-19948846211000086/637313996471", "27674141753240653/30123979153216", "-6169936206128396568797607742807090270137721977/6117715203873571641674006593837351328"},
+	{"-3/26206484091896184128", "5/2848423294177090248", "15310893822118706237/9330894968229805033368778458685147968", "-5/24882386581946146755650075889827061248"},
+	{"26946729/330400702820", "41563965/225583428284", "1238218672302860271/4658307703098666660055", "224002580204097/14906584649915733312176"},
+	{"-8259900599013409474/7", "-84829337473700364773/56707961321161574960", "-468402123685491748914621885145127724451/396955729248131024720", "350340947706464153265156004876107029701/198477864624065512360"},
+	{"575775209696864/1320203974639986246357", "29/712593081308", "410331716733912717985762465/940768218243776489278275419794956", "808/45524274987585732633"},
+	{"1786597389946320496771/2066653520653241", "6269770/1992362624741777", "3559549865190272133656109052308126637/4117523232840525481453983149257", "8967230/3296219033"},
+	{"-36459180403360509753/32150500941194292113930", "9381566963714/9633539", "301622077145533298008420642898530153/309723104686531919656937098270", "-3784609207827/3426986245"},
+}
+
+func TestRatBin(t *testing.T) {
+	for i, test := range ratBinTests {
+		arg := ratBinArg{test.x, test.y, test.sum}
+		testRatBin(t, i, "Add", (*Rat).Add, arg)
+
+		arg = ratBinArg{test.y, test.x, test.sum}
+		testRatBin(t, i, "Add symmetric", (*Rat).Add, arg)
+
+		arg = ratBinArg{test.sum, test.x, test.y}
+		testRatBin(t, i, "Sub", (*Rat).Sub, arg)
+
+		arg = ratBinArg{test.sum, test.y, test.x}
+		testRatBin(t, i, "Sub symmetric", (*Rat).Sub, arg)
+
+		arg = ratBinArg{test.x, test.y, test.prod}
+		testRatBin(t, i, "Mul", (*Rat).Mul, arg)
+
+		arg = ratBinArg{test.y, test.x, test.prod}
+		testRatBin(t, i, "Mul symmetric", (*Rat).Mul, arg)
+
+		if test.x != "0" {
+			arg = ratBinArg{test.prod, test.x, test.y}
+			testRatBin(t, i, "Quo", (*Rat).Quo, arg)
+		}
+
+		if test.y != "0" {
+			arg = ratBinArg{test.prod, test.y, test.x}
+			testRatBin(t, i, "Quo symmetric", (*Rat).Quo, arg)
+		}
+	}
+}
+
+
+func TestIssue820(t *testing.T) {
+	x := NewRat(3, 1)
+	y := NewRat(2, 1)
+	z := y.Quo(x, y)
+	q := NewRat(3, 2)
+	if z.Cmp(q) != 0 {
+		t.Errorf("got %s want %s", z, q)
+	}
+
+	y = NewRat(3, 1)
+	x = NewRat(2, 1)
+	z = y.Quo(x, y)
+	q = NewRat(2, 3)
+	if z.Cmp(q) != 0 {
+		t.Errorf("got %s want %s", z, q)
+	}
+
+	x = NewRat(3, 1)
+	z = x.Quo(x, x)
+	q = NewRat(3, 3)
+	if z.Cmp(q) != 0 {
+		t.Errorf("got %s want %s", z, q)
+	}
+}
+
+
+var setFrac64Tests = []struct {
+	a, b int64
+	out  string
+}{
+	{0, 1, "0"},
+	{0, -1, "0"},
+	{1, 1, "1"},
+	{-1, 1, "-1"},
+	{1, -1, "-1"},
+	{-1, -1, "1"},
+	{-9223372036854775808, -9223372036854775808, "1"},
+}
+
+func TestRatSetFrac64Rat(t *testing.T) {
+	for i, test := range setFrac64Tests {
+		x := new(Rat).SetFrac64(test.a, test.b)
+		if x.RatString() != test.out {
+			t.Errorf("#%d got %s want %s", i, x.RatString(), test.out)
+		}
+	}
+}