math/big: removed more unnecessary string conversions

- renamed (nat) itoa to utoa (since that's what it is)
- added (nat) itoa that takes a sign parameter; this helps removing a few string copies
- used buffers instead of string+ in Rat conversions

Change-Id: I6b37a6b39557ae311cafdfe5c4a26e9246bde1a9
Reviewed-on: https://go-review.googlesource.com/14995
Reviewed-by: Alan Donovan <adonovan@google.com>

7 files changed, 62 insertions, 44 deletions

diff --git a/src/math/big/decimal.go b/src/math/big/decimal.go
index 28cddf9f6b..2c0c9daebc 100644
--- a/src/math/big/decimal.go
+++ b/src/math/big/decimal.go
@@ -80,7 +80,7 @@ func (x *decimal) init(m nat, shift int) {
 	}
 
 	// Convert mantissa into decimal representation.
-	s := m.itoa(10)
+	s := m.utoa(10)
 	n := len(s)
 	x.exp = n
 	// Trim trailing zeros; instead the exponent is tracking
diff --git a/src/math/big/ftoa.go b/src/math/big/ftoa.go
index 3727b7d651..0ed5f6fe9b 100644
--- a/src/math/big/ftoa.go
+++ b/src/math/big/ftoa.go
@@ -165,7 +165,7 @@ func roundShortest(d *decimal, x *Float) {
 	// Approach: All numbers in the interval [x - 1/2ulp, x + 1/2ulp]
 	// (possibly exclusive) round to x for the given precision of x.
 	// Compute the lower and upper bound in decimal form and find the
-	// the shortest decimal number d such that lower <= d <= upper.
+	// shortest decimal number d such that lower <= d <= upper.
 
 	// TODO(gri) strconv/ftoa.do describes a shortcut in some cases.
 	// See if we can use it (in adjusted form) here as well.
@@ -323,7 +323,7 @@ func (x *Float) fmtB(buf []byte) []byte {
 		m = nat(nil).shr(m, uint(w-x.prec))
 	}
 
-	buf = append(buf, m.itoa(10)...)
+	buf = append(buf, m.utoa(10)...)
 	buf = append(buf, 'p')
 	e := int64(x.exp) - int64(x.prec)
 	if e >= 0 {
@@ -357,7 +357,7 @@ func (x *Float) fmtP(buf []byte) []byte {
 	m = m[i:]
 
 	buf = append(buf, "0x."...)
-	buf = append(buf, bytes.TrimRight(m.itoa(16), "0")...)
+	buf = append(buf, bytes.TrimRight(m.utoa(16), "0")...)
 	buf = append(buf, 'p')
 	if x.exp >= 0 {
 		buf = append(buf, '+')
diff --git a/src/math/big/intconv.go b/src/math/big/intconv.go
index 524f775a39..56a75f87ae 100644
--- a/src/math/big/intconv.go
+++ b/src/math/big/intconv.go
@@ -26,11 +26,7 @@ func (x *Int) Text(base int) string {
 	if x == nil {
 		return "<nil>"
 	}
-	s := string(x.abs.itoa(base))
-	if x.neg {
-		s = "-" + s
-	}
-	return s
+	return string(x.abs.itoa(x.neg, base))
 }
 
 // Append appends the string representation of x, as generated by
@@ -39,10 +35,7 @@ func (x *Int) Append(buf []byte, base int) []byte {
 	if x == nil {
 		return append(buf, "<nil>"...)
 	}
-	if x.neg {
-		buf = append(buf, '-')
-	}
-	return append(buf, x.abs.itoa(base)...)
+	return append(buf, x.abs.itoa(x.neg, base)...)
 }
 
 func (x *Int) String() string {
@@ -117,7 +110,7 @@ func (x *Int) Format(s fmt.State, ch rune) {
 		}
 	}
 
-	digits := x.abs.itoa(base)
+	digits := x.abs.utoa(base)
 	if ch == 'X' {
 		// faster than bytes.ToUpper
 		for i, d := range digits {
diff --git a/src/math/big/nat_test.go b/src/math/big/nat_test.go
index 3def120fff..3eefffc61b 100644
--- a/src/math/big/nat_test.go
+++ b/src/math/big/nat_test.go
@@ -158,7 +158,7 @@ var mulRangesN = []struct {
 
 func TestMulRangeN(t *testing.T) {
 	for i, r := range mulRangesN {
-		prod := string(nat(nil).mulRange(r.a, r.b).itoa(10))
+		prod := string(nat(nil).mulRange(r.a, r.b).utoa(10))
 		if prod != r.prod {
 			t.Errorf("#%d: got %s; want %s", i, prod, r.prod)
 		}
@@ -326,7 +326,7 @@ func TestTrailingZeroBits(t *testing.T) {
 	for i := uint(0); i <= 3*_W; i++ {
 		n := y.trailingZeroBits()
 		if n != i {
-			t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.itoa(16), n, i)
+			t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.utoa(16), n, i)
 		}
 		y = y.shl(y, 1)
 	}
@@ -388,7 +388,7 @@ func TestMontgomery(t *testing.T) {
 		z := nat(nil).montgomery(x, y, m, k0, len(m))
 		z = z.norm()
 		if z.cmp(out) != 0 {
-			t.Errorf("#%d got %s want %s", i, z.itoa(10), out.itoa(10))
+			t.Errorf("#%d got %s want %s", i, z.utoa(10), out.utoa(10))
 		}
 	}
 }
@@ -429,7 +429,7 @@ func TestExpNN(t *testing.T) {
 
 		z := nat(nil).expNN(x, y, m)
 		if z.cmp(out) != 0 {
-			t.Errorf("#%d got %s want %s", i, z.itoa(10), out.itoa(10))
+			t.Errorf("#%d got %s want %s", i, z.utoa(10), out.utoa(10))
 		}
 	}
 }
@@ -486,7 +486,7 @@ var fiboNums = []string{
 func TestFibo(t *testing.T) {
 	for i, want := range fiboNums {
 		n := i * 10
-		got := string(fibo(n).itoa(10))
+		got := string(fibo(n).utoa(10))
 		if got != want {
 			t.Errorf("fibo(%d) failed: got %s want %s", n, got, want)
 		}
diff --git a/src/math/big/natconv.go b/src/math/big/natconv.go
index 96c0fad6e6..d2ce667fb6 100644
--- a/src/math/big/natconv.go
+++ b/src/math/big/natconv.go
@@ -234,9 +234,14 @@ func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count in
 	return
 }
 
-// itoa converts x to an ASCII representation in the given base;
+// utoa converts x to an ASCII representation in the given base;
 // base must be between 2 and MaxBase, inclusive.
-func (x nat) itoa(base int) []byte {
+func (x nat) utoa(base int) []byte {
+	return x.itoa(false, base)
+}
+
+// itoa is like utoa but it prepends a '-' if neg && x != 0.
+func (x nat) itoa(neg bool, base int) []byte {
 	if base < 2 || base > MaxBase {
 		panic("invalid base")
 	}
@@ -249,6 +254,9 @@ func (x nat) itoa(base int) []byte {
 
 	// allocate buffer for conversion
 	i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most
+	if neg {
+		i++
+	}
 	s := make([]byte, i)
 
 	// convert power of two and non power of two bases separately
@@ -315,6 +323,11 @@ func (x nat) itoa(base int) []byte {
 		}
 	}
 
+	if neg {
+		i--
+		s[i] = '-'
+	}
+
 	return s[i:]
 }
 
diff --git a/src/math/big/natconv_test.go b/src/math/big/natconv_test.go
index 687b70698a..028e5a858e 100644
--- a/src/math/big/natconv_test.go
+++ b/src/math/big/natconv_test.go
@@ -61,14 +61,14 @@ func TestString(t *testing.T) {
 		defer func() {
 			panicStr = recover().(string)
 		}()
-		natOne.itoa(1)
+		natOne.utoa(1)
 	}()
 	if panicStr != "invalid base" {
 		t.Errorf("expected panic for invalid base")
 	}
 
 	for _, a := range strTests {
-		s := string(a.x.itoa(a.b))
+		s := string(a.x.utoa(a.b))
 		if s != a.s {
 			t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
 		}
@@ -234,7 +234,7 @@ func TestScanPi(t *testing.T) {
 	if err != nil {
 		t.Errorf("scanning pi: %s", err)
 	}
-	if s := string(z.itoa(10)); s != pi {
+	if s := string(z.utoa(10)); s != pi {
 		t.Errorf("scanning pi: got %s", s)
 	}
 }
@@ -263,12 +263,12 @@ func BenchmarkScanPi(b *testing.B) {
 func BenchmarkStringPiParallel(b *testing.B) {
 	var x nat
 	x, _, _, _ = x.scan(strings.NewReader(pi), 0, false)
-	if string(x.itoa(10)) != pi {
+	if string(x.utoa(10)) != pi {
 		panic("benchmark incorrect: conversion failed")
 	}
 	b.RunParallel(func(pb *testing.PB) {
 		for pb.Next() {
-			x.itoa(10)
+			x.utoa(10)
 		}
 	})
 }
@@ -302,7 +302,7 @@ func ScanHelper(b *testing.B, base int, x, y Word) {
 	var z nat
 	z = z.expWW(x, y)
 
-	s := z.itoa(base)
+	s := z.utoa(base)
 	if t := itoa(z, base); !bytes.Equal(s, t) {
 		b.Fatalf("scanning: got %s; want %s", s, t)
 	}
@@ -341,11 +341,11 @@ func StringHelper(b *testing.B, base int, x, y Word) {
 	b.StopTimer()
 	var z nat
 	z = z.expWW(x, y)
-	z.itoa(base) // warm divisor cache
+	z.utoa(base) // warm divisor cache
 	b.StartTimer()
 
 	for i := 0; i < b.N; i++ {
-		_ = z.itoa(base)
+		_ = z.utoa(base)
 	}
 }
 
@@ -380,11 +380,11 @@ func LeafSizeHelper(b *testing.B, base, size int) {
 		b.StopTimer()
 		var z nat
 		z = z.expWW(Word(base), Word(d)) // build target number
-		_ = z.itoa(base)                 // warm divisor cache
+		_ = z.utoa(base)                 // warm divisor cache
 		b.StartTimer()
 
 		for i := 0; i < b.N; i++ {
-			_ = z.itoa(base)
+			_ = z.utoa(base)
 		}
 	}
 
@@ -409,7 +409,7 @@ func TestStringPowers(t *testing.T) {
 	for b := 2; b <= 16; b++ {
 		for p = 0; p <= 512; p++ {
 			x := nat(nil).expWW(Word(b), p)
-			xs := x.itoa(b)
+			xs := x.utoa(b)
 			xs2 := itoa(x, b)
 			if !bytes.Equal(xs, xs2) {
 				t.Errorf("failed at %d ** %d in base %d: %s != %s", b, p, b, xs, xs2)
diff --git a/src/math/big/ratconv.go b/src/math/big/ratconv.go
index 8cf6716c3a..4566ff4e39 100644
--- a/src/math/big/ratconv.go
+++ b/src/math/big/ratconv.go
@@ -188,11 +188,15 @@ func scanExponent(r io.ByteScanner, binExpOk bool) (exp int64, base int, err err
 
 // String returns a string representation of x in the form "a/b" (even if b == 1).
 func (x *Rat) String() string {
-	s := "/1"
+	var buf []byte
+	buf = x.a.Append(buf, 10)
+	buf = append(buf, '/')
 	if len(x.b.abs) != 0 {
-		s = "/" + string(x.b.abs.itoa(10))
+		buf = x.b.Append(buf, 10)
+	} else {
+		buf = append(buf, '1')
 	}
-	return x.a.String() + s
+	return string(buf)
 }
 
 // RatString returns a string representation of x in the form "a/b" if b != 1,
@@ -208,12 +212,17 @@ func (x *Rat) RatString() string {
 // digits of precision after the decimal point. The last digit is rounded to
 // nearest, with halves rounded away from zero.
 func (x *Rat) FloatString(prec int) string {
+	var buf []byte
+
 	if x.IsInt() {
-		s := x.a.String()
+		buf = x.a.Append(buf, 10)
 		if prec > 0 {
-			s += "." + strings.Repeat("0", prec)
+			buf = append(buf, '.')
+			for i := prec; i > 0; i-- {
+				buf = append(buf, '0')
+			}
 		}
-		return s
+		return string(buf)
 	}
 	// x.b.abs != 0
 
@@ -237,16 +246,19 @@ func (x *Rat) FloatString(prec int) string {
 		}
 	}
 
-	s := string(q.itoa(10))
 	if x.a.neg {
-		s = "-" + s
+		buf = append(buf, '-')
 	}
+	buf = append(buf, q.utoa(10)...) // itoa ignores sign if q == 0
 
 	if prec > 0 {
-		rs := string(r.itoa(10))
-		leadingZeros := prec - len(rs)
-		s += "." + strings.Repeat("0", leadingZeros) + rs
+		buf = append(buf, '.')
+		rs := r.utoa(10)
+		for i := prec - len(rs); i > 0; i-- {
+			buf = append(buf, '0')
+		}
+		buf = append(buf, rs...)
 	}
 
-	return s
+	return string(buf)
 }