From 721d5893d7fbc6b1791ee067e95dab3ae8d7d13e Mon Sep 17 00:00:00 2001
From: Robert Griesemer <gri@golang.org>
Date: Tue, 3 Feb 2015 17:37:01 -0800
Subject: [PATCH] math/big: first version of Float %e, %f, %g, %G formatting
 working

Change-Id: I10efa3bc8bc7f41100feabe17837f805a42d7eb6
Reviewed-on: https://go-review.googlesource.com/3842
Reviewed-by: Alan Donovan <adonovan@google.com>
---
 src/math/big/floatconv.go      |   9 +-
 src/math/big/floatconv_test.go | 165 ++++++++++++++++++++++++++----
 src/math/big/ftoa.go           | 181 +++++++++++++++++++++++++++++++++
 3 files changed, 329 insertions(+), 26 deletions(-)
 create mode 100644 src/math/big/ftoa.go

diff --git a/src/math/big/floatconv.go b/src/math/big/floatconv.go
index 06c1f14471..7628e77d9a 100644
--- a/src/math/big/floatconv.go
+++ b/src/math/big/floatconv.go
@@ -162,8 +162,8 @@ func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b i
 // Format converts the floating-point number x to a string according
 // to the given format and precision prec. The format is one of:
 //
-//	'e'	-d.dddde±dd, decimal exponent
-//	'E'	-d.ddddE±dd, decimal exponent
+//	'e'	-d.dddde±dd, decimal exponent, at least two (possibly 0) exponent digits
+//	'E'	-d.ddddE±dd, decimal exponent, at least two (possibly 0) exponent digits
 //	'f'	-ddddd.dddd, no exponent
 //	'g'	like 'e' for large exponents, like 'f' otherwise
 //	'G'	like 'E' for large exponents, like 'f' otherwise
@@ -182,7 +182,7 @@ func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b i
 // number of digits necessary such that ParseFloat will return f exactly.
 // The prec value is ignored for the 'b' or 'p' format.
 //
-// BUG(gri) Currently, Format only accepts the 'b' and 'p' format.
+// BUG(gri) Currently, Format does not accept negative precisions.
 func (x *Float) Format(format byte, prec int) string {
 	const extra = 10 // TODO(gri) determine a good/better value here
 	return string(x.Append(make([]byte, 0, prec+extra), format, prec))
@@ -191,13 +191,14 @@ func (x *Float) Format(format byte, prec int) string {
 // Append appends the string form of the floating-point number x,
 // as generated by x.Format, to buf and returns the extended buffer.
 func (x *Float) Append(buf []byte, format byte, prec int) []byte {
+	// pick off simple cases
 	switch format {
 	case 'b':
 		return x.bstring(buf)
 	case 'p':
 		return x.pstring(buf)
 	}
-	return append(buf, fmt.Sprintf(`%%!c`, format)...)
+	return x.bigFtoa(buf, format, prec)
 }
 
 // BUG(gri): Currently, String uses the 'p' (rather than 'g') format.
diff --git a/src/math/big/floatconv_test.go b/src/math/big/floatconv_test.go
index 0e8bfb39ab..27ac6c877b 100644
--- a/src/math/big/floatconv_test.go
+++ b/src/math/big/floatconv_test.go
@@ -5,6 +5,7 @@
 package big
 
 import (
+	"math"
 	"strconv"
 	"testing"
 )
@@ -71,37 +72,157 @@ func TestFloatSetFloat64String(t *testing.T) {
 	}
 }
 
-func TestFloatFormat(t *testing.T) {
+const (
+	below1e23 = 99999999999999974834176
+	above1e23 = 100000000000000008388608
+)
+
+func TestFloat64Format(t *testing.T) {
 	for _, test := range []struct {
-		x      string
+		x      float64
 		format byte
 		prec   int
 		want   string
 	}{
-		{"0", 'b', 0, "0"},
-		{"-0", 'b', 0, "-0"},
-		{"1.0", 'b', 0, "4503599627370496p-52"},
-		{"-1.0", 'b', 0, "-4503599627370496p-52"},
-		{"4503599627370496", 'b', 0, "4503599627370496p+0"},
-
-		{"0", 'p', 0, "0"},
-		{"-0", 'p', 0, "-0"},
-		{"1024.0", 'p', 0, "0x.8p11"},
-		{"-1024.0", 'p', 0, "-0x.8p11"},
-	} {
-		f64, err := strconv.ParseFloat(test.x, 64)
-		if err != nil {
-			t.Error(err)
-			continue
-		}
+		{0, 'f', 0, "0"},
+		{math.Copysign(0, -1), 'f', 0, "-0"},
+		{1, 'f', 0, "1"},
+		{-1, 'f', 0, "-1"},
+
+		{1.459, 'e', 0, "1e+00"},
+		{2.459, 'e', 1, "2.5e+00"},
+		{3.459, 'e', 2, "3.46e+00"},
+		{4.459, 'e', 3, "4.459e+00"},
+		{5.459, 'e', 4, "5.4590e+00"},
+
+		{1.459, 'f', 0, "1"},
+		{2.459, 'f', 1, "2.5"},
+		{3.459, 'f', 2, "3.46"},
+		{4.459, 'f', 3, "4.459"},
+		{5.459, 'f', 4, "5.4590"},
+
+		{0, 'b', 0, "0"},
+		{math.Copysign(0, -1), 'b', 0, "-0"},
+		{1.0, 'b', 0, "4503599627370496p-52"},
+		{-1.0, 'b', 0, "-4503599627370496p-52"},
+		{4503599627370496, 'b', 0, "4503599627370496p+0"},
+
+		{0, 'p', 0, "0"},
+		{math.Copysign(0, -1), 'p', 0, "-0"},
+		{1024.0, 'p', 0, "0x.8p11"},
+		{-1024.0, 'p', 0, "-0x.8p11"},
+
+		// all test cases below from strconv/ftoa_test.go
+		{1, 'e', 5, "1.00000e+00"},
+		{1, 'f', 5, "1.00000"},
+		{1, 'g', 5, "1"},
+		// {1, 'g', -1, "1"},
+		// {20, 'g', -1, "20"},
+		// {1234567.8, 'g', -1, "1.2345678e+06"},
+		// {200000, 'g', -1, "200000"},
+		// {2000000, 'g', -1, "2e+06"},
+
+		// g conversion and zero suppression
+		{400, 'g', 2, "4e+02"},
+		{40, 'g', 2, "40"},
+		{4, 'g', 2, "4"},
+		{.4, 'g', 2, "0.4"},
+		{.04, 'g', 2, "0.04"},
+		{.004, 'g', 2, "0.004"},
+		{.0004, 'g', 2, "0.0004"},
+		{.00004, 'g', 2, "4e-05"},
+		{.000004, 'g', 2, "4e-06"},
+
+		{0, 'e', 5, "0.00000e+00"},
+		{0, 'f', 5, "0.00000"},
+		{0, 'g', 5, "0"},
+		// {0, 'g', -1, "0"},
+
+		{-1, 'e', 5, "-1.00000e+00"},
+		{-1, 'f', 5, "-1.00000"},
+		{-1, 'g', 5, "-1"},
+		// {-1, 'g', -1, "-1"},
+
+		{12, 'e', 5, "1.20000e+01"},
+		{12, 'f', 5, "12.00000"},
+		{12, 'g', 5, "12"},
+		// {12, 'g', -1, "12"},
+
+		{123456700, 'e', 5, "1.23457e+08"},
+		{123456700, 'f', 5, "123456700.00000"},
+		{123456700, 'g', 5, "1.2346e+08"},
+		// {123456700, 'g', -1, "1.234567e+08"},
 
-		f := new(Float).SetFloat64(f64)
+		{1.2345e6, 'e', 5, "1.23450e+06"},
+		{1.2345e6, 'f', 5, "1234500.00000"},
+		{1.2345e6, 'g', 5, "1.2345e+06"},
+
+		{1e23, 'e', 17, "9.99999999999999916e+22"},
+		{1e23, 'f', 17, "99999999999999991611392.00000000000000000"},
+		{1e23, 'g', 17, "9.9999999999999992e+22"},
+
+		// {1e23, 'e', -1, "1e+23"},
+		// {1e23, 'f', -1, "100000000000000000000000"},
+		// {1e23, 'g', -1, "1e+23"},
+
+		{below1e23, 'e', 17, "9.99999999999999748e+22"},
+		{below1e23, 'f', 17, "99999999999999974834176.00000000000000000"},
+		// {below1e23, 'g', 17, "9.9999999999999975e+22"},
+
+		// {below1e23, 'e', -1, "9.999999999999997e+22"},
+		// {below1e23, 'f', -1, "99999999999999970000000"},
+		// {below1e23, 'g', -1, "9.999999999999997e+22"},
+
+		{above1e23, 'e', 17, "1.00000000000000008e+23"},
+		{above1e23, 'f', 17, "100000000000000008388608.00000000000000000"},
+		// {above1e23, 'g', 17, "1.0000000000000001e+23"},
+
+		// {above1e23, 'e', -1, "1.0000000000000001e+23"},
+		// {above1e23, 'f', -1, "100000000000000010000000"},
+		// {above1e23, 'g', -1, "1.0000000000000001e+23"},
+
+		// {fdiv(5e-304, 1e20), 'g', -1, "5e-324"},
+		// {fdiv(-5e-304, 1e20), 'g', -1, "-5e-324"},
+
+		// {32, 'g', -1, "32"},
+		// {32, 'g', 0, "3e+01"},
+
+		// {100, 'x', -1, "%x"},
+
+		// {math.NaN(), 'g', -1, "NaN"},
+		// {-math.NaN(), 'g', -1, "NaN"},
+		// {math.Inf(0), 'g', -1, "+Inf"},
+		// {math.Inf(-1), 'g', -1, "-Inf"},
+		// {-math.Inf(0), 'g', -1, "-Inf"},
+
+		{-1, 'b', -1, "-4503599627370496p-52"},
+
+		// fixed bugs
+		{0.9, 'f', 1, "0.9"},
+		{0.09, 'f', 1, "0.1"},
+		{0.0999, 'f', 1, "0.1"},
+		{0.05, 'f', 1, "0.1"},
+		{0.05, 'f', 0, "0"},
+		{0.5, 'f', 1, "0.5"},
+		{0.5, 'f', 0, "0"},
+		{1.5, 'f', 0, "2"},
+
+		// http://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/
+		// {2.2250738585072012e-308, 'g', -1, "2.2250738585072014e-308"},
+		// http://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/
+		// {2.2250738585072011e-308, 'g', -1, "2.225073858507201e-308"},
+
+		// Issue 2625.
+		{383260575764816448, 'f', 0, "383260575764816448"},
+		// {383260575764816448, 'g', -1, "3.8326057576481645e+17"},
+	} {
+		f := new(Float).SetFloat64(test.x)
 		got := f.Format(test.format, test.prec)
 		if got != test.want {
 			t.Errorf("%v: got %s; want %s", test, got, test.want)
 		}
 
-		if test.format == 'b' && f64 == 0 {
+		if test.format == 'b' && test.x == 0 {
 			continue // 'b' format in strconv.Float requires knowledge of bias for 0.0
 		}
 		if test.format == 'p' {
@@ -109,9 +230,9 @@ func TestFloatFormat(t *testing.T) {
 		}
 
 		// verify that Float format matches strconv format
-		want := strconv.FormatFloat(f64, test.format, test.prec, 64)
+		want := strconv.FormatFloat(test.x, test.format, test.prec, 64)
 		if got != want {
-			t.Errorf("%v: got %s; want %s", test, got, want)
+			t.Errorf("%v: got %s; want %s (strconv)", test, got, want)
 		}
 	}
 }
diff --git a/src/math/big/ftoa.go b/src/math/big/ftoa.go
new file mode 100644
index 0000000000..5eb0dbdd53
--- /dev/null
+++ b/src/math/big/ftoa.go
@@ -0,0 +1,181 @@
+// Copyright 2015 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 the 'e', 'f', 'g' floating-point formats.
+// It is closely following the corresponding implementation in
+// strconv/ftoa.go, but modified and simplified for big.Float.
+
+// Algorithm:
+//   1) convert Float to multiprecision decimal
+//   2) round to desired precision
+//   3) read digits out and format
+
+package big
+
+import "strconv"
+
+// TODO(gri) Consider moving sign into decimal - could make the signatures below cleaner.
+
+// bigFtoa formats a float for the %e, %E, %f, %g, and %G formats.
+func (f *Float) bigFtoa(buf []byte, fmt byte, prec int) []byte {
+	// TODO(gri) handle Inf.
+
+	// 1) convert Float to multiprecision decimal
+	var d decimal
+	d.init(f.mant, int(f.exp)-f.mant.bitLen())
+
+	// 2) round to desired precision
+	shortest := false
+	if prec < 0 {
+		shortest = true
+		panic("unimplemented")
+		// TODO(gri) complete this
+		// roundShortest(&d, f.mant, int(f.exp))
+		// Precision for shortest representation mode.
+		switch fmt {
+		case 'e', 'E':
+			prec = len(d.mant) - 1
+		case 'f':
+			prec = max(len(d.mant)-d.exp, 0)
+		case 'g', 'G':
+			prec = len(d.mant)
+		}
+	} else {
+		// round appropriately
+		switch fmt {
+		case 'e', 'E':
+			// one digit before and number of digits after decimal point
+			d.round(1 + prec)
+		case 'f':
+			// number of digits before and after decimal point
+			d.round(d.exp + prec)
+		case 'g', 'G':
+			if prec == 0 {
+				prec = 1
+			}
+			d.round(prec)
+		}
+	}
+
+	// 3) read digits out and format
+	switch fmt {
+	case 'e', 'E':
+		return fmtE(buf, fmt, prec, f.neg, d)
+	case 'f':
+		return fmtF(buf, prec, f.neg, d)
+	case 'g', 'G':
+		// trim trailing fractional zeros in %e format
+		eprec := prec
+		if eprec > len(d.mant) && len(d.mant) >= d.exp {
+			eprec = len(d.mant)
+		}
+		// %e is used if the exponent from the conversion
+		// is less than -4 or greater than or equal to the precision.
+		// If precision was the shortest possible, use eprec = 6 for
+		// this decision.
+		if shortest {
+			eprec = 6
+		}
+		exp := d.exp - 1
+		if exp < -4 || exp >= eprec {
+			if prec > len(d.mant) {
+				prec = len(d.mant)
+			}
+			return fmtE(buf, fmt+'e'-'g', prec-1, f.neg, d)
+		}
+		if prec > d.exp {
+			prec = len(d.mant)
+		}
+		return fmtF(buf, max(prec-d.exp, 0), f.neg, d)
+	}
+
+	// unknown format
+	return append(buf, '%', fmt)
+}
+
+// %e: -d.ddddde±dd
+func fmtE(buf []byte, fmt byte, prec int, neg bool, d decimal) []byte {
+	// sign
+	if neg {
+		buf = append(buf, '-')
+	}
+
+	// first digit
+	ch := byte('0')
+	if len(d.mant) > 0 {
+		ch = d.mant[0]
+	}
+	buf = append(buf, ch)
+
+	// .moredigits
+	if prec > 0 {
+		buf = append(buf, '.')
+		// TODO(gri) clean up logic below
+		i := 1
+		m := len(d.mant) + prec + 1 - max(len(d.mant), prec+1)
+		if i < m {
+			buf = append(buf, d.mant[i:m]...)
+			i = m
+		}
+		for ; i <= prec; i++ {
+			buf = append(buf, '0')
+		}
+	}
+
+	// e±
+	buf = append(buf, fmt)
+	var exp int64
+	if len(d.mant) > 0 {
+		exp = int64(d.exp) - 1 // -1 because first digit was printed before '.'
+	}
+	if exp < 0 {
+		ch = '-'
+		exp = -exp
+	} else {
+		ch = '+'
+	}
+	buf = append(buf, ch)
+
+	// dd...d
+	if exp < 10 {
+		buf = append(buf, '0') // at least 2 exponent digits
+	}
+	return strconv.AppendInt(buf, exp, 10)
+}
+
+// %f: -ddddddd.ddddd
+func fmtF(buf []byte, prec int, neg bool, d decimal) []byte {
+	// sign
+	if neg {
+		buf = append(buf, '-')
+	}
+
+	// integer, padded with zeros as needed.
+	if d.exp > 0 {
+		// TODO(gri) fuse loops below and/or cleanup
+		var i int
+		for i = 0; i < int(d.exp) && i < len(d.mant); i++ {
+			buf = append(buf, d.mant[i])
+		}
+		for ; i < d.exp; i++ {
+			buf = append(buf, '0')
+		}
+	} else {
+		buf = append(buf, '0')
+	}
+
+	// fraction
+	if prec > 0 {
+		buf = append(buf, '.')
+		for i := 0; i < prec; i++ {
+			ch := byte('0')
+			if j := d.exp + i; 0 <= j && j < len(d.mant) {
+				ch = d.mant[j]
+			}
+			buf = append(buf, ch)
+		}
+	}
+
+	return buf
+}
-- 
2.50.0