From e937eeeccdbf07df30ad4ea8ebd3cc20742b3200 Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Fri, 25 Sep 2015 10:09:04 -0700 Subject: [PATCH] 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 --- src/math/big/decimal.go | 2 +- src/math/big/ftoa.go | 6 +++--- src/math/big/intconv.go | 13 +++---------- src/math/big/nat_test.go | 10 +++++----- src/math/big/natconv.go | 17 +++++++++++++++-- src/math/big/natconv_test.go | 22 +++++++++++----------- src/math/big/ratconv.go | 36 ++++++++++++++++++++++++------------ 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 "" } - 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, ""...) } - 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) } -- 2.50.0