src/pkg/strconv/ftoa.go - The Go Programming Language

Golang

Source file src/pkg/strconv/ftoa.go

     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 int, 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		// Negative precision means "only as much as needed to be exact."
   102		shortest := prec < 0
   103	
   104		d := new(decimal)
   105		if shortest {
   106			ok := false
   107			if optimize && bitSize == 64 {
   108				// Try Grisu3 algorithm.
   109				f := new(extFloat)
   110				lower, upper := f.AssignComputeBounds(val)
   111				ok = f.ShortestDecimal(d, &lower, &upper)
   112			}
   113			if !ok {
   114				// Create exact decimal representation.
   115				// The shift is exp - flt.mantbits because mant is a 1-bit integer
   116				// followed by a flt.mantbits fraction, and we are treating it as
   117				// a 1+flt.mantbits-bit integer.
   118				d.Assign(mant)
   119				d.Shift(exp - int(flt.mantbits))
   120				roundShortest(d, mant, exp, flt)
   121			}
   122			// Precision for shortest representation mode.
   123			if prec < 0 {
   124				switch fmt {
   125				case 'e', 'E':
   126					prec = d.nd - 1
   127				case 'f':
   128					prec = max(d.nd-d.dp, 0)
   129				case 'g', 'G':
   130					prec = d.nd
   131				}
   132			}
   133		} else {
   134			// Create exact decimal representation.
   135			d.Assign(mant)
   136			d.Shift(exp - int(flt.mantbits))
   137			// Round appropriately.
   138			switch fmt {
   139			case 'e', 'E':
   140				d.Round(prec + 1)
   141			case 'f':
   142				d.Round(d.dp + prec)
   143			case 'g', 'G':
   144				if prec == 0 {
   145					prec = 1
   146				}
   147				d.Round(prec)
   148			}
   149		}
   150	
   151		switch fmt {
   152		case 'e', 'E':
   153			return fmtE(dst, neg, d, prec, fmt)
   154		case 'f':
   155			return fmtF(dst, neg, d, prec)
   156		case 'g', 'G':
   157			// trailing fractional zeros in 'e' form will be trimmed.
   158			eprec := prec
   159			if eprec > d.nd && d.nd >= d.dp {
   160				eprec = d.nd
   161			}
   162			// %e is used if the exponent from the conversion
   163			// is less than -4 or greater than or equal to the precision.
   164			// if precision was the shortest possible, use precision 6 for this decision.
   165			if shortest {
   166				eprec = 6
   167			}
   168			exp := d.dp - 1
   169			if exp < -4 || exp >= eprec {
   170				if prec > d.nd {
   171					prec = d.nd
   172				}
   173				return fmtE(dst, neg, d, prec-1, fmt+'e'-'g')
   174			}
   175			if prec > d.dp {
   176				prec = d.nd
   177			}
   178			return fmtF(dst, neg, d, max(prec-d.dp, 0))
   179		}
   180	
   181		// unknown format
   182		return append(dst, '%', fmt)
   183	}
   184	
   185	// Round d (= mant * 2^exp) to the shortest number of digits
   186	// that will let the original floating point value be precisely
   187	// reconstructed.  Size is original floating point size (64 or 32).
   188	func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
   189		// If mantissa is zero, the number is zero; stop now.
   190		if mant == 0 {
   191			d.nd = 0
   192			return
   193		}
   194	
   195		// Compute upper and lower such that any decimal number
   196		// between upper and lower (possibly inclusive)
   197		// will round to the original floating point number.
   198	
   199		// We may see at once that the number is already shortest.
   200		//
   201		// Suppose d is not denormal, so that 2^exp <= d < 10^dp.
   202		// The closest shorter number is at least 10^(dp-nd) away.
   203		// The lower/upper bounds computed below are at distance
   204		// at most 2^(exp-mantbits).
   205		//
   206		// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
   207		// or equivalently log2(10)*(dp-nd) > exp-mantbits.
   208		// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
   209		minexp := flt.bias + 1 // minimum possible exponent
   210		if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
   211			// The number is already shortest.
   212			return
   213		}
   214	
   215		// d = mant << (exp - mantbits)
   216		// Next highest floating point number is mant+1 << exp-mantbits.
   217		// Our upper bound is halfway inbetween, mant*2+1 << exp-mantbits-1.
   218		upper := new(decimal)
   219		upper.Assign(mant*2 + 1)
   220		upper.Shift(exp - int(flt.mantbits) - 1)
   221	
   222		// d = mant << (exp - mantbits)
   223		// Next lowest floating point number is mant-1 << exp-mantbits,
   224		// unless mant-1 drops the significant bit and exp is not the minimum exp,
   225		// in which case the next lowest is mant*2-1 << exp-mantbits-1.
   226		// Either way, call it mantlo << explo-mantbits.
   227		// Our lower bound is halfway inbetween, mantlo*2+1 << explo-mantbits-1.
   228		var mantlo uint64
   229		var explo int
   230		if mant > 1<<flt.mantbits || exp == minexp {
   231			mantlo = mant - 1
   232			explo = exp
   233		} else {
   234			mantlo = mant*2 - 1
   235			explo = exp - 1
   236		}
   237		lower := new(decimal)
   238		lower.Assign(mantlo*2 + 1)
   239		lower.Shift(explo - int(flt.mantbits) - 1)
   240	
   241		// The upper and lower bounds are possible outputs only if
   242		// the original mantissa is even, so that IEEE round-to-even
   243		// would round to the original mantissa and not the neighbors.
   244		inclusive := mant%2 == 0
   245	
   246		// Now we can figure out the minimum number of digits required.
   247		// Walk along until d has distinguished itself from upper and lower.
   248		for i := 0; i < d.nd; i++ {
   249			var l, m, u byte // lower, middle, upper digits
   250			if i < lower.nd {
   251				l = lower.d[i]
   252			} else {
   253				l = '0'
   254			}
   255			m = d.d[i]
   256			if i < upper.nd {
   257				u = upper.d[i]
   258			} else {
   259				u = '0'
   260			}
   261	
   262			// Okay to round down (truncate) if lower has a different digit
   263			// or if lower is inclusive and is exactly the result of rounding down.
   264			okdown := l != m || (inclusive && l == m && i+1 == lower.nd)
   265	
   266			// Okay to round up if upper has a different digit and
   267			// either upper is inclusive or upper is bigger than the result of rounding up.
   268			okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd)
   269	
   270			// If it's okay to do either, then round to the nearest one.
   271			// If it's okay to do only one, do it.
   272			switch {
   273			case okdown && okup:
   274				d.Round(i + 1)
   275				return
   276			case okdown:
   277				d.RoundDown(i + 1)
   278				return
   279			case okup:
   280				d.RoundUp(i + 1)
   281				return
   282			}
   283		}
   284	}
   285	
   286	// %e: -d.ddddde±dd
   287	func fmtE(dst []byte, neg bool, d *decimal, prec int, fmt byte) []byte {
   288		// sign
   289		if neg {
   290			dst = append(dst, '-')
   291		}
   292	
   293		// first digit
   294		ch := byte('0')
   295		if d.nd != 0 {
   296			ch = d.d[0]
   297		}
   298		dst = append(dst, ch)
   299	
   300		// .moredigits
   301		if prec > 0 {
   302			dst = append(dst, '.')
   303			for i := 1; i <= prec; i++ {
   304				ch = '0'
   305				if i < d.nd {
   306					ch = d.d[i]
   307				}
   308				dst = append(dst, ch)
   309			}
   310		}
   311	
   312		// e±
   313		dst = append(dst, fmt)
   314		exp := d.dp - 1
   315		if d.nd == 0 { // special case: 0 has exponent 0
   316			exp = 0
   317		}
   318		if exp < 0 {
   319			ch = '-'
   320			exp = -exp
   321		} else {
   322			ch = '+'
   323		}
   324		dst = append(dst, ch)
   325	
   326		// dddd
   327		var buf [3]byte
   328		i := len(buf)
   329		for exp >= 10 {
   330			i--
   331			buf[i] = byte(exp%10 + '0')
   332			exp /= 10
   333		}
   334		// exp < 10
   335		i--
   336		buf[i] = byte(exp + '0')
   337	
   338		// leading zeroes
   339		if i > len(buf)-2 {
   340			i--
   341			buf[i] = '0'
   342		}
   343	
   344		return append(dst, buf[i:]...)
   345	}
   346	
   347	// %f: -ddddddd.ddddd
   348	func fmtF(dst []byte, neg bool, d *decimal, prec int) []byte {
   349		// sign
   350		if neg {
   351			dst = append(dst, '-')
   352		}
   353	
   354		// integer, padded with zeros as needed.
   355		if d.dp > 0 {
   356			var i int
   357			for i = 0; i < d.dp && i < d.nd; i++ {
   358				dst = append(dst, d.d[i])
   359			}
   360			for ; i < d.dp; i++ {
   361				dst = append(dst, '0')
   362			}
   363		} else {
   364			dst = append(dst, '0')
   365		}
   366	
   367		// fraction
   368		if prec > 0 {
   369			dst = append(dst, '.')
   370			for i := 0; i < prec; i++ {
   371				ch := byte('0')
   372				if j := d.dp + i; 0 <= j && j < d.nd {
   373					ch = d.d[j]
   374				}
   375				dst = append(dst, ch)
   376			}
   377		}
   378	
   379		return dst
   380	}
   381	
   382	// %b: -ddddddddp+ddd
   383	func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   384		var buf [50]byte
   385		w := len(buf)
   386		exp -= int(flt.mantbits)
   387		esign := byte('+')
   388		if exp < 0 {
   389			esign = '-'
   390			exp = -exp
   391		}
   392		n := 0
   393		for exp > 0 || n < 1 {
   394			n++
   395			w--
   396			buf[w] = byte(exp%10 + '0')
   397			exp /= 10
   398		}
   399		w--
   400		buf[w] = esign
   401		w--
   402		buf[w] = 'p'
   403		n = 0
   404		for mant > 0 || n < 1 {
   405			n++
   406			w--
   407			buf[w] = byte(mant%10 + '0')
   408			mant /= 10
   409		}
   410		if neg {
   411			w--
   412			buf[w] = '-'
   413		}
   414		return append(dst, buf[w:]...)
   415	}
   416	
   417	func max(a, b int) int {
   418		if a > b {
   419			return a
   420		}
   421		return b
   422	}