ftoa.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file implements Float-to-string conversion functions.
     6  // It is closely following the corresponding implementation
     7  // in strconv/ftoa.go, but modified and simplified for Float.
     8  
     9  package big
    10  
    11  import (
    12  	"bytes"
    13  	"fmt"
    14  	"strconv"
    15  )
    16  
    17  // Text converts the floating-point number x to a string according
    18  // to the given format and precision prec. The format is one of:
    19  //
    20  //	'e'	-d.dddde±dd, decimal exponent, at least two (possibly 0) exponent digits
    21  //	'E'	-d.ddddE±dd, decimal exponent, at least two (possibly 0) exponent digits
    22  //	'f'	-ddddd.dddd, no exponent
    23  //	'g'	like 'e' for large exponents, like 'f' otherwise
    24  //	'G'	like 'E' for large exponents, like 'f' otherwise
    25  //	'x'	-0xd.dddddp±dd, hexadecimal mantissa, decimal power of two exponent
    26  //	'p'	-0x.dddp±dd, hexadecimal mantissa, decimal power of two exponent (non-standard)
    27  //	'b'	-ddddddp±dd, decimal mantissa, decimal power of two exponent (non-standard)
    28  //
    29  // For the power-of-two exponent formats, the mantissa is printed in normalized form:
    30  //
    31  //	'x'	hexadecimal mantissa in [1, 2), or 0
    32  //	'p'	hexadecimal mantissa in [½, 1), or 0
    33  //	'b'	decimal integer mantissa using x.Prec() bits, or 0
    34  //
    35  // Note that the 'x' form is the one used by most other languages and libraries.
    36  //
    37  // If format is a different character, Text returns a "%" followed by the
    38  // unrecognized format character.
    39  //
    40  // The precision prec controls the number of digits (excluding the exponent)
    41  // printed by the 'e', 'E', 'f', 'g', 'G', and 'x' formats.
    42  // For 'e', 'E', 'f', and 'x', it is the number of digits after the decimal point.
    43  // For 'g' and 'G' it is the total number of digits. A negative precision selects
    44  // the smallest number of decimal digits necessary to identify the value x uniquely
    45  // using x.Prec() mantissa bits.
    46  // The prec value is ignored for the 'b' and 'p' formats.
    47  func (x *Float) Text(format byte, prec int) string {
    48  	cap := 10 // TODO(gri) determine a good/better value here
    49  	if prec > 0 {
    50  		cap += prec
    51  	}
    52  	return string(x.Append(make([]byte, 0, cap), format, prec))
    53  }
    54  
    55  // String formats x like x.Text('g', 10).
    56  // (String must be called explicitly, Float.Format does not support %s verb.)
    57  func (x *Float) String() string {
    58  	return x.Text('g', 10)
    59  }
    60  
    61  // Append appends to buf the string form of the floating-point number x,
    62  // as generated by x.Text, and returns the extended buffer.
    63  func (x *Float) Append(buf []byte, fmt byte, prec int) []byte {
    64  	// sign
    65  	if x.neg {
    66  		buf = append(buf, '-')
    67  	}
    68  
    69  	// Inf
    70  	if x.form == inf {
    71  		if !x.neg {
    72  			buf = append(buf, '+')
    73  		}
    74  		return append(buf, "Inf"...)
    75  	}
    76  
    77  	// pick off easy formats
    78  	switch fmt {
    79  	case 'b':
    80  		return x.fmtB(buf)
    81  	case 'p':
    82  		return x.fmtP(buf)
    83  	case 'x':
    84  		return x.fmtX(buf, prec)
    85  	}
    86  
    87  	// Algorithm:
    88  	//   1) convert Float to multiprecision decimal
    89  	//   2) round to desired precision
    90  	//   3) read digits out and format
    91  
    92  	// 1) convert Float to multiprecision decimal
    93  	var d decimal // == 0.0
    94  	if x.form == finite {
    95  		// x != 0
    96  		d.init(x.mant, int(x.exp)-x.mant.bitLen())
    97  	}
    98  
    99  	// 2) round to desired precision
   100  	shortest := false
   101  	if prec < 0 {
   102  		shortest = true
   103  		roundShortest(&d, x)
   104  		// Precision for shortest representation mode.
   105  		switch fmt {
   106  		case 'e', 'E':
   107  			prec = len(d.mant) - 1
   108  		case 'f':
   109  			prec = max(len(d.mant)-d.exp, 0)
   110  		case 'g', 'G':
   111  			prec = len(d.mant)
   112  		}
   113  	} else {
   114  		// round appropriately
   115  		switch fmt {
   116  		case 'e', 'E':
   117  			// one digit before and number of digits after decimal point
   118  			d.round(1 + prec)
   119  		case 'f':
   120  			// number of digits before and after decimal point
   121  			d.round(d.exp + prec)
   122  		case 'g', 'G':
   123  			if prec == 0 {
   124  				prec = 1
   125  			}
   126  			d.round(prec)
   127  		}
   128  	}
   129  
   130  	// 3) read digits out and format
   131  	switch fmt {
   132  	case 'e', 'E':
   133  		return fmtE(buf, fmt, prec, d)
   134  	case 'f':
   135  		return fmtF(buf, prec, d)
   136  	case 'g', 'G':
   137  		// trim trailing fractional zeros in %e format
   138  		eprec := prec
   139  		if eprec > len(d.mant) && len(d.mant) >= d.exp {
   140  			eprec = len(d.mant)
   141  		}
   142  		// %e is used if the exponent from the conversion
   143  		// is less than -4 or greater than or equal to the precision.
   144  		// If precision was the shortest possible, use eprec = 6 for
   145  		// this decision.
   146  		if shortest {
   147  			eprec = 6
   148  		}
   149  		exp := d.exp - 1
   150  		if exp < -4 || exp >= eprec {
   151  			if prec > len(d.mant) {
   152  				prec = len(d.mant)
   153  			}
   154  			return fmtE(buf, fmt+'e'-'g', prec-1, d)
   155  		}
   156  		if prec > d.exp {
   157  			prec = len(d.mant)
   158  		}
   159  		return fmtF(buf, max(prec-d.exp, 0), d)
   160  	}
   161  
   162  	// unknown format
   163  	if x.neg {
   164  		buf = buf[:len(buf)-1] // sign was added prematurely - remove it again
   165  	}
   166  	return append(buf, '%', fmt)
   167  }
   168  
   169  func roundShortest(d *decimal, x *Float) {
   170  	// if the mantissa is zero, the number is zero - stop now
   171  	if len(d.mant) == 0 {
   172  		return
   173  	}
   174  
   175  	// Approach: All numbers in the interval [x - 1/2ulp, x + 1/2ulp]
   176  	// (possibly exclusive) round to x for the given precision of x.
   177  	// Compute the lower and upper bound in decimal form and find the
   178  	// shortest decimal number d such that lower <= d <= upper.
   179  
   180  	// TODO(gri) strconv/ftoa.do describes a shortcut in some cases.
   181  	// See if we can use it (in adjusted form) here as well.
   182  
   183  	// 1) Compute normalized mantissa mant and exponent exp for x such
   184  	// that the lsb of mant corresponds to 1/2 ulp for the precision of
   185  	// x (i.e., for mant we want x.prec + 1 bits).
   186  	mant := nat(nil).set(x.mant)
   187  	exp := int(x.exp) - mant.bitLen()
   188  	s := mant.bitLen() - int(x.prec+1)
   189  	switch {
   190  	case s < 0:
   191  		mant = mant.shl(mant, uint(-s))
   192  	case s > 0:
   193  		mant = mant.shr(mant, uint(+s))
   194  	}
   195  	exp += s
   196  	// x = mant * 2**exp with lsb(mant) == 1/2 ulp of x.prec
   197  
   198  	// 2) Compute lower bound by subtracting 1/2 ulp.
   199  	var lower decimal
   200  	var tmp nat
   201  	lower.init(tmp.sub(mant, natOne), exp)
   202  
   203  	// 3) Compute upper bound by adding 1/2 ulp.
   204  	var upper decimal
   205  	upper.init(tmp.add(mant, natOne), exp)
   206  
   207  	// The upper and lower bounds are possible outputs only if
   208  	// the original mantissa is even, so that ToNearestEven rounding
   209  	// would round to the original mantissa and not the neighbors.
   210  	inclusive := mant[0]&2 == 0 // test bit 1 since original mantissa was shifted by 1
   211  
   212  	// Now we can figure out the minimum number of digits required.
   213  	// Walk along until d has distinguished itself from upper and lower.
   214  	for i, m := range d.mant {
   215  		l := lower.at(i)
   216  		u := upper.at(i)
   217  
   218  		// Okay to round down (truncate) if lower has a different digit
   219  		// or if lower is inclusive and is exactly the result of rounding
   220  		// down (i.e., and we have reached the final digit of lower).
   221  		okdown := l != m || inclusive && i+1 == len(lower.mant)
   222  
   223  		// Okay to round up if upper has a different digit and either upper
   224  		// is inclusive or upper is bigger than the result of rounding up.
   225  		okup := m != u && (inclusive || m+1 < u || i+1 < len(upper.mant))
   226  
   227  		// If it's okay to do either, then round to the nearest one.
   228  		// If it's okay to do only one, do it.
   229  		switch {
   230  		case okdown && okup:
   231  			d.round(i + 1)
   232  			return
   233  		case okdown:
   234  			d.roundDown(i + 1)
   235  			return
   236  		case okup:
   237  			d.roundUp(i + 1)
   238  			return
   239  		}
   240  	}
   241  }
   242  
   243  // %e: d.ddddde±dd
   244  func fmtE(buf []byte, fmt byte, prec int, d decimal) []byte {
   245  	// first digit
   246  	ch := byte('0')
   247  	if len(d.mant) > 0 {
   248  		ch = d.mant[0]
   249  	}
   250  	buf = append(buf, ch)
   251  
   252  	// .moredigits
   253  	if prec > 0 {
   254  		buf = append(buf, '.')
   255  		i := 1
   256  		m := min(len(d.mant), prec+1)
   257  		if i < m {
   258  			buf = append(buf, d.mant[i:m]...)
   259  			i = m
   260  		}
   261  		for ; i <= prec; i++ {
   262  			buf = append(buf, '0')
   263  		}
   264  	}
   265  
   266  	// e±
   267  	buf = append(buf, fmt)
   268  	var exp int64
   269  	if len(d.mant) > 0 {
   270  		exp = int64(d.exp) - 1 // -1 because first digit was printed before '.'
   271  	}
   272  	if exp < 0 {
   273  		ch = '-'
   274  		exp = -exp
   275  	} else {
   276  		ch = '+'
   277  	}
   278  	buf = append(buf, ch)
   279  
   280  	// dd...d
   281  	if exp < 10 {
   282  		buf = append(buf, '0') // at least 2 exponent digits
   283  	}
   284  	return strconv.AppendInt(buf, exp, 10)
   285  }
   286  
   287  // %f: ddddddd.ddddd
   288  func fmtF(buf []byte, prec int, d decimal) []byte {
   289  	// integer, padded with zeros as needed
   290  	if d.exp > 0 {
   291  		m := min(len(d.mant), d.exp)
   292  		buf = append(buf, d.mant[:m]...)
   293  		for ; m < d.exp; m++ {
   294  			buf = append(buf, '0')
   295  		}
   296  	} else {
   297  		buf = append(buf, '0')
   298  	}
   299  
   300  	// fraction
   301  	if prec > 0 {
   302  		buf = append(buf, '.')
   303  		for i := 0; i < prec; i++ {
   304  			buf = append(buf, d.at(d.exp+i))
   305  		}
   306  	}
   307  
   308  	return buf
   309  }
   310  
   311  // fmtB appends the string of x in the format mantissa "p" exponent
   312  // with a decimal mantissa and a binary exponent, or 0" if x is zero,
   313  // and returns the extended buffer.
   314  // The mantissa is normalized such that is uses x.Prec() bits in binary
   315  // representation.
   316  // The sign of x is ignored, and x must not be an Inf.
   317  // (The caller handles Inf before invoking fmtB.)
   318  func (x *Float) fmtB(buf []byte) []byte {
   319  	if x.form == zero {
   320  		return append(buf, '0')
   321  	}
   322  
   323  	if debugFloat && x.form != finite {
   324  		panic("non-finite float")
   325  	}
   326  	// x != 0
   327  
   328  	// adjust mantissa to use exactly x.prec bits
   329  	m := x.mant
   330  	switch w := uint32(len(x.mant)) * _W; {
   331  	case w < x.prec:
   332  		m = nat(nil).shl(m, uint(x.prec-w))
   333  	case w > x.prec:
   334  		m = nat(nil).shr(m, uint(w-x.prec))
   335  	}
   336  
   337  	buf = append(buf, m.utoa(10)...)
   338  	buf = append(buf, 'p')
   339  	e := int64(x.exp) - int64(x.prec)
   340  	if e >= 0 {
   341  		buf = append(buf, '+')
   342  	}
   343  	return strconv.AppendInt(buf, e, 10)
   344  }
   345  
   346  // fmtX appends the string of x in the format "0x1." mantissa "p" exponent
   347  // with a hexadecimal mantissa and a binary exponent, or "0x0p0" if x is zero,
   348  // and returns the extended buffer.
   349  // A non-zero mantissa is normalized such that 1.0 <= mantissa < 2.0.
   350  // The sign of x is ignored, and x must not be an Inf.
   351  // (The caller handles Inf before invoking fmtX.)
   352  func (x *Float) fmtX(buf []byte, prec int) []byte {
   353  	if x.form == zero {
   354  		buf = append(buf, "0x0"...)
   355  		if prec > 0 {
   356  			buf = append(buf, '.')
   357  			for i := 0; i < prec; i++ {
   358  				buf = append(buf, '0')
   359  			}
   360  		}
   361  		buf = append(buf, "p+00"...)
   362  		return buf
   363  	}
   364  
   365  	if debugFloat && x.form != finite {
   366  		panic("non-finite float")
   367  	}
   368  
   369  	// round mantissa to n bits
   370  	var n uint
   371  	if prec < 0 {
   372  		n = 1 + (x.MinPrec()-1+3)/4*4 // round MinPrec up to 1 mod 4
   373  	} else {
   374  		n = 1 + 4*uint(prec)
   375  	}
   376  	// n%4 == 1
   377  	x = new(Float).SetPrec(n).SetMode(x.mode).Set(x)
   378  
   379  	// adjust mantissa to use exactly n bits
   380  	m := x.mant
   381  	switch w := uint(len(x.mant)) * _W; {
   382  	case w < n:
   383  		m = nat(nil).shl(m, n-w)
   384  	case w > n:
   385  		m = nat(nil).shr(m, w-n)
   386  	}
   387  	exp64 := int64(x.exp) - 1 // avoid wrap-around
   388  
   389  	hm := m.utoa(16)
   390  	if debugFloat && hm[0] != '1' {
   391  		panic("incorrect mantissa: " + string(hm))
   392  	}
   393  	buf = append(buf, "0x1"...)
   394  	if len(hm) > 1 {
   395  		buf = append(buf, '.')
   396  		buf = append(buf, hm[1:]...)
   397  	}
   398  
   399  	buf = append(buf, 'p')
   400  	if exp64 >= 0 {
   401  		buf = append(buf, '+')
   402  	} else {
   403  		exp64 = -exp64
   404  		buf = append(buf, '-')
   405  	}
   406  	// Force at least two exponent digits, to match fmt.
   407  	if exp64 < 10 {
   408  		buf = append(buf, '0')
   409  	}
   410  	return strconv.AppendInt(buf, exp64, 10)
   411  }
   412  
   413  // fmtP appends the string of x in the format "0x." mantissa "p" exponent
   414  // with a hexadecimal mantissa and a binary exponent, or "0" if x is zero,
   415  // and returns the extended buffer.
   416  // The mantissa is normalized such that 0.5 <= 0.mantissa < 1.0.
   417  // The sign of x is ignored, and x must not be an Inf.
   418  // (The caller handles Inf before invoking fmtP.)
   419  func (x *Float) fmtP(buf []byte) []byte {
   420  	if x.form == zero {
   421  		return append(buf, '0')
   422  	}
   423  
   424  	if debugFloat && x.form != finite {
   425  		panic("non-finite float")
   426  	}
   427  	// x != 0
   428  
   429  	// remove trailing 0 words early
   430  	// (no need to convert to hex 0's and trim later)
   431  	m := x.mant
   432  	i := 0
   433  	for i < len(m) && m[i] == 0 {
   434  		i++
   435  	}
   436  	m = m[i:]
   437  
   438  	buf = append(buf, "0x."...)
   439  	buf = append(buf, bytes.TrimRight(m.utoa(16), "0")...)
   440  	buf = append(buf, 'p')
   441  	if x.exp >= 0 {
   442  		buf = append(buf, '+')
   443  	}
   444  	return strconv.AppendInt(buf, int64(x.exp), 10)
   445  }
   446  
   447  func min(x, y int) int {
   448  	if x < y {
   449  		return x
   450  	}
   451  	return y
   452  }
   453  
   454  var _ fmt.Formatter = &floatZero // *Float must implement fmt.Formatter
   455  
   456  // Format implements fmt.Formatter. It accepts all the regular
   457  // formats for floating-point numbers ('b', 'e', 'E', 'f', 'F',
   458  // 'g', 'G', 'x') as well as 'p' and 'v'. See (*Float).Text for the
   459  // interpretation of 'p'. The 'v' format is handled like 'g'.
   460  // Format also supports specification of the minimum precision
   461  // in digits, the output field width, as well as the format flags
   462  // '+' and ' ' for sign control, '0' for space or zero padding,
   463  // and '-' for left or right justification. See the fmt package
   464  // for details.
   465  func (x *Float) Format(s fmt.State, format rune) {
   466  	prec, hasPrec := s.Precision()
   467  	if !hasPrec {
   468  		prec = 6 // default precision for 'e', 'f'
   469  	}
   470  
   471  	switch format {
   472  	case 'e', 'E', 'f', 'b', 'p', 'x':
   473  		// nothing to do
   474  	case 'F':
   475  		// (*Float).Text doesn't support 'F'; handle like 'f'
   476  		format = 'f'
   477  	case 'v':
   478  		// handle like 'g'
   479  		format = 'g'
   480  		fallthrough
   481  	case 'g', 'G':
   482  		if !hasPrec {
   483  			prec = -1 // default precision for 'g', 'G'
   484  		}
   485  	default:
   486  		fmt.Fprintf(s, "%%!%c(*big.Float=%s)", format, x.String())
   487  		return
   488  	}
   489  	var buf []byte
   490  	buf = x.Append(buf, byte(format), prec)
   491  	if len(buf) == 0 {
   492  		buf = []byte("?") // should never happen, but don't crash
   493  	}
   494  	// len(buf) > 0
   495  
   496  	var sign string
   497  	switch {
   498  	case buf[0] == '-':
   499  		sign = "-"
   500  		buf = buf[1:]
   501  	case buf[0] == '+':
   502  		// +Inf
   503  		sign = "+"
   504  		if s.Flag(' ') {
   505  			sign = " "
   506  		}
   507  		buf = buf[1:]
   508  	case s.Flag('+'):
   509  		sign = "+"
   510  	case s.Flag(' '):
   511  		sign = " "
   512  	}
   513  
   514  	var padding int
   515  	if width, hasWidth := s.Width(); hasWidth && width > len(sign)+len(buf) {
   516  		padding = width - len(sign) - len(buf)
   517  	}
   518  
   519  	switch {
   520  	case s.Flag('0') && !x.IsInf():
   521  		// 0-padding on left
   522  		writeMultiple(s, sign, 1)
   523  		writeMultiple(s, "0", padding)
   524  		s.Write(buf)
   525  	case s.Flag('-'):
   526  		// padding on right
   527  		writeMultiple(s, sign, 1)
   528  		s.Write(buf)
   529  		writeMultiple(s, " ", padding)
   530  	default:
   531  		// padding on left
   532  		writeMultiple(s, " ", padding)
   533  		writeMultiple(s, sign, 1)
   534  		s.Write(buf)
   535  	}
   536  }
   537
View as plain text