ftoa.go

Documentation: strconv

     1  // Copyright 2009 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  // Binary to decimal floating point conversion.
     6  // Algorithm:
     7  //   1) store mantissa in multiprecision decimal
     8  //   2) shift decimal by exponent
     9  //   3) read digits out & format
    10  
    11  package strconv
    12  
    13  import "math"
    14  
    15  // TODO: move elsewhere?
    16  type floatInfo struct {
    17  	mantbits uint
    18  	expbits  uint
    19  	bias     int
    20  }
    21  
    22  var float32info = floatInfo{23, 8, -127}
    23  var float64info = floatInfo{52, 11, -1023}
    24  
    25  // FormatFloat converts the floating-point number f to a string,
    26  // according to the format fmt and precision prec. It rounds the
    27  // result assuming that the original was obtained from a floating-point
    28  // value of bitSize bits (32 for float32, 64 for float64).
    29  //
    30  // The format fmt is one of
    31  // 'b' (-ddddp±ddd, a binary exponent),
    32  // 'e' (-d.dddde±dd, a decimal exponent),
    33  // 'E' (-d.ddddE±dd, a decimal exponent),
    34  // 'f' (-ddd.dddd, no exponent),
    35  // 'g' ('e' for large exponents, 'f' otherwise), or
    36  // 'G' ('E' for large exponents, 'f' otherwise).
    37  //
    38  // The precision prec controls the number of digits
    39  // (excluding the exponent) printed by the 'e', 'E', 'f', 'g', and 'G' formats.
    40  // For 'e', 'E', and 'f' it is the number of digits after the decimal point.
    41  // For 'g' and 'G' it is the total number of digits.
    42  // The special precision -1 uses the smallest number of digits
    43  // necessary such that ParseFloat will return f exactly.
    44  func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
    45  	return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))
    46  }
    47  
    48  // AppendFloat appends the string form of the floating-point number f,
    49  // as generated by FormatFloat, to dst and returns the extended buffer.
    50  func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
    51  	return genericFtoa(dst, f, fmt, prec, bitSize)
    52  }
    53  
    54  func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
    55  	var bits uint64
    56  	var flt *floatInfo
    57  	switch bitSize {
    58  	case 32:
    59  		bits = uint64(math.Float32bits(float32(val)))
    60  		flt = &float32info
    61  	case 64:
    62  		bits = math.Float64bits(val)
    63  		flt = &float64info
    64  	default:
    65  		panic("strconv: illegal AppendFloat/FormatFloat bitSize")
    66  	}
    67  
    68  	neg := bits>>(flt.expbits+flt.mantbits) != 0
    69  	exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
    70  	mant := bits & (uint64(1)<<flt.mantbits - 1)
    71  
    72  	switch exp {
    73  	case 1<<flt.expbits - 1:
    74  		// Inf, NaN
    75  		var s string
    76  		switch {
    77  		case mant != 0:
    78  			s = "NaN"
    79  		case neg:
    80  			s = "-Inf"
    81  		default:
    82  			s = "+Inf"
    83  		}
    84  		return append(dst, s...)
    85  
    86  	case 0:
    87  		// denormalized
    88  		exp++
    89  
    90  	default:
    91  		// add implicit top bit
    92  		mant |= uint64(1) << flt.mantbits
    93  	}
    94  	exp += flt.bias
    95  
    96  	// Pick off easy binary format.
    97  	if fmt == 'b' {
    98  		return fmtB(dst, neg, mant, exp, flt)
    99  	}
   100  
   101  	if !optimize {
   102  		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   103  	}
   104  
   105  	var digs decimalSlice
   106  	ok := false
   107  	// Negative precision means "only as much as needed to be exact."
   108  	shortest := prec < 0
   109  	if shortest {
   110  		// Try Grisu3 algorithm.
   111  		f := new(extFloat)
   112  		lower, upper := f.AssignComputeBounds(mant, exp, neg, flt)
   113  		var buf [32]byte
   114  		digs.d = buf[:]
   115  		ok = f.ShortestDecimal(&digs, &lower, &upper)
   116  		if !ok {
   117  			return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   118  		}
   119  		// Precision for shortest representation mode.
   120  		switch fmt {
   121  		case 'e', 'E':
   122  			prec = max(digs.nd-1, 0)
   123  		case 'f':
   124  			prec = max(digs.nd-digs.dp, 0)
   125  		case 'g', 'G':
   126  			prec = digs.nd
   127  		}
   128  	} else if fmt != 'f' {
   129  		// Fixed number of digits.
   130  		digits := prec
   131  		switch fmt {
   132  		case 'e', 'E':
   133  			digits++
   134  		case 'g', 'G':
   135  			if prec == 0 {
   136  				prec = 1
   137  			}
   138  			digits = prec
   139  		}
   140  		if digits <= 15 {
   141  			// try fast algorithm when the number of digits is reasonable.
   142  			var buf [24]byte
   143  			digs.d = buf[:]
   144  			f := extFloat{mant, exp - int(flt.mantbits), neg}
   145  			ok = f.FixedDecimal(&digs, digits)
   146  		}
   147  	}
   148  	if !ok {
   149  		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   150  	}
   151  	return formatDigits(dst, shortest, neg, digs, prec, fmt)
   152  }
   153  
   154  // bigFtoa uses multiprecision computations to format a float.
   155  func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   156  	d := new(decimal)
   157  	d.Assign(mant)
   158  	d.Shift(exp - int(flt.mantbits))
   159  	var digs decimalSlice
   160  	shortest := prec < 0
   161  	if shortest {
   162  		roundShortest(d, mant, exp, flt)
   163  		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
   164  		// Precision for shortest representation mode.
   165  		switch fmt {
   166  		case 'e', 'E':
   167  			prec = digs.nd - 1
   168  		case 'f':
   169  			prec = max(digs.nd-digs.dp, 0)
   170  		case 'g', 'G':
   171  			prec = digs.nd
   172  		}
   173  	} else {
   174  		// Round appropriately.
   175  		switch fmt {
   176  		case 'e', 'E':
   177  			d.Round(prec + 1)
   178  		case 'f':
   179  			d.Round(d.dp + prec)
   180  		case 'g', 'G':
   181  			if prec == 0 {
   182  				prec = 1
   183  			}
   184  			d.Round(prec)
   185  		}
   186  		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
   187  	}
   188  	return formatDigits(dst, shortest, neg, digs, prec, fmt)
   189  }
   190  
   191  func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
   192  	switch fmt {
   193  	case 'e', 'E':
   194  		return fmtE(dst, neg, digs, prec, fmt)
   195  	case 'f':
   196  		return fmtF(dst, neg, digs, prec)
   197  	case 'g', 'G':
   198  		// trailing fractional zeros in 'e' form will be trimmed.
   199  		eprec := prec
   200  		if eprec > digs.nd && digs.nd >= digs.dp {
   201  			eprec = digs.nd
   202  		}
   203  		// %e is used if the exponent from the conversion
   204  		// is less than -4 or greater than or equal to the precision.
   205  		// if precision was the shortest possible, use precision 6 for this decision.
   206  		if shortest {
   207  			eprec = 6
   208  		}
   209  		exp := digs.dp - 1
   210  		if exp < -4 || exp >= eprec {
   211  			if prec > digs.nd {
   212  				prec = digs.nd
   213  			}
   214  			return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
   215  		}
   216  		if prec > digs.dp {
   217  			prec = digs.nd
   218  		}
   219  		return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
   220  	}
   221  
   222  	// unknown format
   223  	return append(dst, '%', fmt)
   224  }
   225  
   226  // roundShortest rounds d (= mant * 2^exp) to the shortest number of digits
   227  // that will let the original floating point value be precisely reconstructed.
   228  func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
   229  	// If mantissa is zero, the number is zero; stop now.
   230  	if mant == 0 {
   231  		d.nd = 0
   232  		return
   233  	}
   234  
   235  	// Compute upper and lower such that any decimal number
   236  	// between upper and lower (possibly inclusive)
   237  	// will round to the original floating point number.
   238  
   239  	// We may see at once that the number is already shortest.
   240  	//
   241  	// Suppose d is not denormal, so that 2^exp <= d < 10^dp.
   242  	// The closest shorter number is at least 10^(dp-nd) away.
   243  	// The lower/upper bounds computed below are at distance
   244  	// at most 2^(exp-mantbits).
   245  	//
   246  	// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
   247  	// or equivalently log2(10)*(dp-nd) > exp-mantbits.
   248  	// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
   249  	minexp := flt.bias + 1 // minimum possible exponent
   250  	if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
   251  		// The number is already shortest.
   252  		return
   253  	}
   254  
   255  	// d = mant << (exp - mantbits)
   256  	// Next highest floating point number is mant+1 << exp-mantbits.
   257  	// Our upper bound is halfway between, mant*2+1 << exp-mantbits-1.
   258  	upper := new(decimal)
   259  	upper.Assign(mant*2 + 1)
   260  	upper.Shift(exp - int(flt.mantbits) - 1)
   261  
   262  	// d = mant << (exp - mantbits)
   263  	// Next lowest floating point number is mant-1 << exp-mantbits,
   264  	// unless mant-1 drops the significant bit and exp is not the minimum exp,
   265  	// in which case the next lowest is mant*2-1 << exp-mantbits-1.
   266  	// Either way, call it mantlo << explo-mantbits.
   267  	// Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1.
   268  	var mantlo uint64
   269  	var explo int
   270  	if mant > 1<<flt.mantbits || exp == minexp {
   271  		mantlo = mant - 1
   272  		explo = exp
   273  	} else {
   274  		mantlo = mant*2 - 1
   275  		explo = exp - 1
   276  	}
   277  	lower := new(decimal)
   278  	lower.Assign(mantlo*2 + 1)
   279  	lower.Shift(explo - int(flt.mantbits) - 1)
   280  
   281  	// The upper and lower bounds are possible outputs only if
   282  	// the original mantissa is even, so that IEEE round-to-even
   283  	// would round to the original mantissa and not the neighbors.
   284  	inclusive := mant%2 == 0
   285  
   286  	// Now we can figure out the minimum number of digits required.
   287  	// Walk along until d has distinguished itself from upper and lower.
   288  	for i := 0; i < d.nd; i++ {
   289  		l := byte('0') // lower digit
   290  		if i < lower.nd {
   291  			l = lower.d[i]
   292  		}
   293  		m := d.d[i]    // middle digit
   294  		u := byte('0') // upper digit
   295  		if i < upper.nd {
   296  			u = upper.d[i]
   297  		}
   298  
   299  		// Okay to round down (truncate) if lower has a different digit
   300  		// or if lower is inclusive and is exactly the result of rounding
   301  		// down (i.e., and we have reached the final digit of lower).
   302  		okdown := l != m || inclusive && i+1 == lower.nd
   303  
   304  		// Okay to round up if upper has a different digit and either upper
   305  		// is inclusive or upper is bigger than the result of rounding up.
   306  		okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd)
   307  
   308  		// If it's okay to do either, then round to the nearest one.
   309  		// If it's okay to do only one, do it.
   310  		switch {
   311  		case okdown && okup:
   312  			d.Round(i + 1)
   313  			return
   314  		case okdown:
   315  			d.RoundDown(i + 1)
   316  			return
   317  		case okup:
   318  			d.RoundUp(i + 1)
   319  			return
   320  		}
   321  	}
   322  }
   323  
   324  type decimalSlice struct {
   325  	d      []byte
   326  	nd, dp int
   327  	neg    bool
   328  }
   329  
   330  // %e: -d.ddddde±dd
   331  func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
   332  	// sign
   333  	if neg {
   334  		dst = append(dst, '-')
   335  	}
   336  
   337  	// first digit
   338  	ch := byte('0')
   339  	if d.nd != 0 {
   340  		ch = d.d[0]
   341  	}
   342  	dst = append(dst, ch)
   343  
   344  	// .moredigits
   345  	if prec > 0 {
   346  		dst = append(dst, '.')
   347  		i := 1
   348  		m := min(d.nd, prec+1)
   349  		if i < m {
   350  			dst = append(dst, d.d[i:m]...)
   351  			i = m
   352  		}
   353  		for ; i <= prec; i++ {
   354  			dst = append(dst, '0')
   355  		}
   356  	}
   357  
   358  	// e±
   359  	dst = append(dst, fmt)
   360  	exp := d.dp - 1
   361  	if d.nd == 0 { // special case: 0 has exponent 0
   362  		exp = 0
   363  	}
   364  	if exp < 0 {
   365  		ch = '-'
   366  		exp = -exp
   367  	} else {
   368  		ch = '+'
   369  	}
   370  	dst = append(dst, ch)
   371  
   372  	// dd or ddd
   373  	switch {
   374  	case exp < 10:
   375  		dst = append(dst, '0', byte(exp)+'0')
   376  	case exp < 100:
   377  		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
   378  	default:
   379  		dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
   380  	}
   381  
   382  	return dst
   383  }
   384  
   385  // %f: -ddddddd.ddddd
   386  func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
   387  	// sign
   388  	if neg {
   389  		dst = append(dst, '-')
   390  	}
   391  
   392  	// integer, padded with zeros as needed.
   393  	if d.dp > 0 {
   394  		m := min(d.nd, d.dp)
   395  		dst = append(dst, d.d[:m]...)
   396  		for ; m < d.dp; m++ {
   397  			dst = append(dst, '0')
   398  		}
   399  	} else {
   400  		dst = append(dst, '0')
   401  	}
   402  
   403  	// fraction
   404  	if prec > 0 {
   405  		dst = append(dst, '.')
   406  		for i := 0; i < prec; i++ {
   407  			ch := byte('0')
   408  			if j := d.dp + i; 0 <= j && j < d.nd {
   409  				ch = d.d[j]
   410  			}
   411  			dst = append(dst, ch)
   412  		}
   413  	}
   414  
   415  	return dst
   416  }
   417  
   418  // %b: -ddddddddp±ddd
   419  func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   420  	// sign
   421  	if neg {
   422  		dst = append(dst, '-')
   423  	}
   424  
   425  	// mantissa
   426  	dst, _ = formatBits(dst, mant, 10, false, true)
   427  
   428  	// p
   429  	dst = append(dst, 'p')
   430  
   431  	// ±exponent
   432  	exp -= int(flt.mantbits)
   433  	if exp >= 0 {
   434  		dst = append(dst, '+')
   435  	}
   436  	dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)
   437  
   438  	return dst
   439  }
   440  
   441  func min(a, b int) int {
   442  	if a < b {
   443  		return a
   444  	}
   445  	return b
   446  }
   447  
   448  func max(a, b int) int {
   449  	if a > b {
   450  		return a
   451  	}
   452  	return b
   453  }
   454
View as plain text