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),
		36  // 'G' ('E' for large exponents, 'f' otherwise),
		37  // 'x' (-0xd.ddddp±ddd, a hexadecimal fraction and binary exponent), or
		38  // 'X' (-0Xd.ddddP±ddd, a hexadecimal fraction and binary exponent).
		39  //
		40  // The precision prec controls the number of digits (excluding the exponent)
		41  // printed by the 'e', 'E', 'f', 'g', 'G', 'x', and 'X' formats.
		42  // For 'e', 'E', 'f', 'x', and 'X', it is the number of digits after the decimal point.
		43  // For 'g' and 'G' it is the maximum number of significant digits (trailing
		44  // zeros are removed).
		45  // The special precision -1 uses the smallest number of digits
		46  // necessary such that ParseFloat will return f exactly.
		47  func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
		48  	return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))
		49  }
		50  
		51  // AppendFloat appends the string form of the floating-point number f,
		52  // as generated by FormatFloat, to dst and returns the extended buffer.
		53  func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
		54  	return genericFtoa(dst, f, fmt, prec, bitSize)
		55  }
		56  
		57  func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
		58  	var bits uint64
		59  	var flt *floatInfo
		60  	switch bitSize {
		61  	case 32:
		62  		bits = uint64(math.Float32bits(float32(val)))
		63  		flt = &float32info
		64  	case 64:
		65  		bits = math.Float64bits(val)
		66  		flt = &float64info
		67  	default:
		68  		panic("strconv: illegal AppendFloat/FormatFloat bitSize")
		69  	}
		70  
		71  	neg := bits>>(flt.expbits+flt.mantbits) != 0
		72  	exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
		73  	mant := bits & (uint64(1)<<flt.mantbits - 1)
		74  
		75  	switch exp {
		76  	case 1<<flt.expbits - 1:
		77  		// Inf, NaN
		78  		var s string
		79  		switch {
		80  		case mant != 0:
		81  			s = "NaN"
		82  		case neg:
		83  			s = "-Inf"
		84  		default:
		85  			s = "+Inf"
		86  		}
		87  		return append(dst, s...)
		88  
		89  	case 0:
		90  		// denormalized
		91  		exp++
		92  
		93  	default:
		94  		// add implicit top bit
		95  		mant |= uint64(1) << flt.mantbits
		96  	}
		97  	exp += flt.bias
		98  
		99  	// Pick off easy binary, hex formats.
	 100  	if fmt == 'b' {
	 101  		return fmtB(dst, neg, mant, exp, flt)
	 102  	}
	 103  	if fmt == 'x' || fmt == 'X' {
	 104  		return fmtX(dst, prec, fmt, neg, mant, exp, flt)
	 105  	}
	 106  
	 107  	if !optimize {
	 108  		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	 109  	}
	 110  
	 111  	var digs decimalSlice
	 112  	ok := false
	 113  	// Negative precision means "only as much as needed to be exact."
	 114  	shortest := prec < 0
	 115  	if shortest {
	 116  		// Use Ryu algorithm.
	 117  		var buf [32]byte
	 118  		digs.d = buf[:]
	 119  		ryuFtoaShortest(&digs, mant, exp-int(flt.mantbits), flt)
	 120  		ok = true
	 121  		// Precision for shortest representation mode.
	 122  		switch fmt {
	 123  		case 'e', 'E':
	 124  			prec = max(digs.nd-1, 0)
	 125  		case 'f':
	 126  			prec = max(digs.nd-digs.dp, 0)
	 127  		case 'g', 'G':
	 128  			prec = digs.nd
	 129  		}
	 130  	} else if fmt != 'f' {
	 131  		// Fixed number of digits.
	 132  		digits := prec
	 133  		switch fmt {
	 134  		case 'e', 'E':
	 135  			digits++
	 136  		case 'g', 'G':
	 137  			if prec == 0 {
	 138  				prec = 1
	 139  			}
	 140  			digits = prec
	 141  		}
	 142  		var buf [24]byte
	 143  		if bitSize == 32 && digits <= 9 {
	 144  			digs.d = buf[:]
	 145  			ryuFtoaFixed32(&digs, uint32(mant), exp-int(flt.mantbits), digits)
	 146  			ok = true
	 147  		} else if digits <= 18 {
	 148  			digs.d = buf[:]
	 149  			ryuFtoaFixed64(&digs, mant, exp-int(flt.mantbits), digits)
	 150  			ok = true
	 151  		}
	 152  	}
	 153  	if !ok {
	 154  		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
	 155  	}
	 156  	return formatDigits(dst, shortest, neg, digs, prec, fmt)
	 157  }
	 158  
	 159  // bigFtoa uses multiprecision computations to format a float.
	 160  func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	 161  	d := new(decimal)
	 162  	d.Assign(mant)
	 163  	d.Shift(exp - int(flt.mantbits))
	 164  	var digs decimalSlice
	 165  	shortest := prec < 0
	 166  	if shortest {
	 167  		roundShortest(d, mant, exp, flt)
	 168  		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
	 169  		// Precision for shortest representation mode.
	 170  		switch fmt {
	 171  		case 'e', 'E':
	 172  			prec = digs.nd - 1
	 173  		case 'f':
	 174  			prec = max(digs.nd-digs.dp, 0)
	 175  		case 'g', 'G':
	 176  			prec = digs.nd
	 177  		}
	 178  	} else {
	 179  		// Round appropriately.
	 180  		switch fmt {
	 181  		case 'e', 'E':
	 182  			d.Round(prec + 1)
	 183  		case 'f':
	 184  			d.Round(d.dp + prec)
	 185  		case 'g', 'G':
	 186  			if prec == 0 {
	 187  				prec = 1
	 188  			}
	 189  			d.Round(prec)
	 190  		}
	 191  		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
	 192  	}
	 193  	return formatDigits(dst, shortest, neg, digs, prec, fmt)
	 194  }
	 195  
	 196  func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
	 197  	switch fmt {
	 198  	case 'e', 'E':
	 199  		return fmtE(dst, neg, digs, prec, fmt)
	 200  	case 'f':
	 201  		return fmtF(dst, neg, digs, prec)
	 202  	case 'g', 'G':
	 203  		// trailing fractional zeros in 'e' form will be trimmed.
	 204  		eprec := prec
	 205  		if eprec > digs.nd && digs.nd >= digs.dp {
	 206  			eprec = digs.nd
	 207  		}
	 208  		// %e is used if the exponent from the conversion
	 209  		// is less than -4 or greater than or equal to the precision.
	 210  		// if precision was the shortest possible, use precision 6 for this decision.
	 211  		if shortest {
	 212  			eprec = 6
	 213  		}
	 214  		exp := digs.dp - 1
	 215  		if exp < -4 || exp >= eprec {
	 216  			if prec > digs.nd {
	 217  				prec = digs.nd
	 218  			}
	 219  			return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
	 220  		}
	 221  		if prec > digs.dp {
	 222  			prec = digs.nd
	 223  		}
	 224  		return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
	 225  	}
	 226  
	 227  	// unknown format
	 228  	return append(dst, '%', fmt)
	 229  }
	 230  
	 231  // roundShortest rounds d (= mant * 2^exp) to the shortest number of digits
	 232  // that will let the original floating point value be precisely reconstructed.
	 233  func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
	 234  	// If mantissa is zero, the number is zero; stop now.
	 235  	if mant == 0 {
	 236  		d.nd = 0
	 237  		return
	 238  	}
	 239  
	 240  	// Compute upper and lower such that any decimal number
	 241  	// between upper and lower (possibly inclusive)
	 242  	// will round to the original floating point number.
	 243  
	 244  	// We may see at once that the number is already shortest.
	 245  	//
	 246  	// Suppose d is not denormal, so that 2^exp <= d < 10^dp.
	 247  	// The closest shorter number is at least 10^(dp-nd) away.
	 248  	// The lower/upper bounds computed below are at distance
	 249  	// at most 2^(exp-mantbits).
	 250  	//
	 251  	// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
	 252  	// or equivalently log2(10)*(dp-nd) > exp-mantbits.
	 253  	// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
	 254  	minexp := flt.bias + 1 // minimum possible exponent
	 255  	if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
	 256  		// The number is already shortest.
	 257  		return
	 258  	}
	 259  
	 260  	// d = mant << (exp - mantbits)
	 261  	// Next highest floating point number is mant+1 << exp-mantbits.
	 262  	// Our upper bound is halfway between, mant*2+1 << exp-mantbits-1.
	 263  	upper := new(decimal)
	 264  	upper.Assign(mant*2 + 1)
	 265  	upper.Shift(exp - int(flt.mantbits) - 1)
	 266  
	 267  	// d = mant << (exp - mantbits)
	 268  	// Next lowest floating point number is mant-1 << exp-mantbits,
	 269  	// unless mant-1 drops the significant bit and exp is not the minimum exp,
	 270  	// in which case the next lowest is mant*2-1 << exp-mantbits-1.
	 271  	// Either way, call it mantlo << explo-mantbits.
	 272  	// Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1.
	 273  	var mantlo uint64
	 274  	var explo int
	 275  	if mant > 1<<flt.mantbits || exp == minexp {
	 276  		mantlo = mant - 1
	 277  		explo = exp
	 278  	} else {
	 279  		mantlo = mant*2 - 1
	 280  		explo = exp - 1
	 281  	}
	 282  	lower := new(decimal)
	 283  	lower.Assign(mantlo*2 + 1)
	 284  	lower.Shift(explo - int(flt.mantbits) - 1)
	 285  
	 286  	// The upper and lower bounds are possible outputs only if
	 287  	// the original mantissa is even, so that IEEE round-to-even
	 288  	// would round to the original mantissa and not the neighbors.
	 289  	inclusive := mant%2 == 0
	 290  
	 291  	// As we walk the digits we want to know whether rounding up would fall
	 292  	// within the upper bound. This is tracked by upperdelta:
	 293  	//
	 294  	// If upperdelta == 0, the digits of d and upper are the same so far.
	 295  	//
	 296  	// If upperdelta == 1, we saw a difference of 1 between d and upper on a
	 297  	// previous digit and subsequently only 9s for d and 0s for upper.
	 298  	// (Thus rounding up may fall outside the bound, if it is exclusive.)
	 299  	//
	 300  	// If upperdelta == 2, then the difference is greater than 1
	 301  	// and we know that rounding up falls within the bound.
	 302  	var upperdelta uint8
	 303  
	 304  	// Now we can figure out the minimum number of digits required.
	 305  	// Walk along until d has distinguished itself from upper and lower.
	 306  	for ui := 0; ; ui++ {
	 307  		// lower, d, and upper may have the decimal points at different
	 308  		// places. In this case upper is the longest, so we iterate from
	 309  		// ui==0 and start li and mi at (possibly) -1.
	 310  		mi := ui - upper.dp + d.dp
	 311  		if mi >= d.nd {
	 312  			break
	 313  		}
	 314  		li := ui - upper.dp + lower.dp
	 315  		l := byte('0') // lower digit
	 316  		if li >= 0 && li < lower.nd {
	 317  			l = lower.d[li]
	 318  		}
	 319  		m := byte('0') // middle digit
	 320  		if mi >= 0 {
	 321  			m = d.d[mi]
	 322  		}
	 323  		u := byte('0') // upper digit
	 324  		if ui < upper.nd {
	 325  			u = upper.d[ui]
	 326  		}
	 327  
	 328  		// Okay to round down (truncate) if lower has a different digit
	 329  		// or if lower is inclusive and is exactly the result of rounding
	 330  		// down (i.e., and we have reached the final digit of lower).
	 331  		okdown := l != m || inclusive && li+1 == lower.nd
	 332  
	 333  		switch {
	 334  		case upperdelta == 0 && m+1 < u:
	 335  			// Example:
	 336  			// m = 12345xxx
	 337  			// u = 12347xxx
	 338  			upperdelta = 2
	 339  		case upperdelta == 0 && m != u:
	 340  			// Example:
	 341  			// m = 12345xxx
	 342  			// u = 12346xxx
	 343  			upperdelta = 1
	 344  		case upperdelta == 1 && (m != '9' || u != '0'):
	 345  			// Example:
	 346  			// m = 1234598x
	 347  			// u = 1234600x
	 348  			upperdelta = 2
	 349  		}
	 350  		// Okay to round up if upper has a different digit and either upper
	 351  		// is inclusive or upper is bigger than the result of rounding up.
	 352  		okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd)
	 353  
	 354  		// If it's okay to do either, then round to the nearest one.
	 355  		// If it's okay to do only one, do it.
	 356  		switch {
	 357  		case okdown && okup:
	 358  			d.Round(mi + 1)
	 359  			return
	 360  		case okdown:
	 361  			d.RoundDown(mi + 1)
	 362  			return
	 363  		case okup:
	 364  			d.RoundUp(mi + 1)
	 365  			return
	 366  		}
	 367  	}
	 368  }
	 369  
	 370  type decimalSlice struct {
	 371  	d			[]byte
	 372  	nd, dp int
	 373  	neg		bool
	 374  }
	 375  
	 376  // %e: -d.ddddde±dd
	 377  func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
	 378  	// sign
	 379  	if neg {
	 380  		dst = append(dst, '-')
	 381  	}
	 382  
	 383  	// first digit
	 384  	ch := byte('0')
	 385  	if d.nd != 0 {
	 386  		ch = d.d[0]
	 387  	}
	 388  	dst = append(dst, ch)
	 389  
	 390  	// .moredigits
	 391  	if prec > 0 {
	 392  		dst = append(dst, '.')
	 393  		i := 1
	 394  		m := min(d.nd, prec+1)
	 395  		if i < m {
	 396  			dst = append(dst, d.d[i:m]...)
	 397  			i = m
	 398  		}
	 399  		for ; i <= prec; i++ {
	 400  			dst = append(dst, '0')
	 401  		}
	 402  	}
	 403  
	 404  	// e±
	 405  	dst = append(dst, fmt)
	 406  	exp := d.dp - 1
	 407  	if d.nd == 0 { // special case: 0 has exponent 0
	 408  		exp = 0
	 409  	}
	 410  	if exp < 0 {
	 411  		ch = '-'
	 412  		exp = -exp
	 413  	} else {
	 414  		ch = '+'
	 415  	}
	 416  	dst = append(dst, ch)
	 417  
	 418  	// dd or ddd
	 419  	switch {
	 420  	case exp < 10:
	 421  		dst = append(dst, '0', byte(exp)+'0')
	 422  	case exp < 100:
	 423  		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
	 424  	default:
	 425  		dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
	 426  	}
	 427  
	 428  	return dst
	 429  }
	 430  
	 431  // %f: -ddddddd.ddddd
	 432  func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
	 433  	// sign
	 434  	if neg {
	 435  		dst = append(dst, '-')
	 436  	}
	 437  
	 438  	// integer, padded with zeros as needed.
	 439  	if d.dp > 0 {
	 440  		m := min(d.nd, d.dp)
	 441  		dst = append(dst, d.d[:m]...)
	 442  		for ; m < d.dp; m++ {
	 443  			dst = append(dst, '0')
	 444  		}
	 445  	} else {
	 446  		dst = append(dst, '0')
	 447  	}
	 448  
	 449  	// fraction
	 450  	if prec > 0 {
	 451  		dst = append(dst, '.')
	 452  		for i := 0; i < prec; i++ {
	 453  			ch := byte('0')
	 454  			if j := d.dp + i; 0 <= j && j < d.nd {
	 455  				ch = d.d[j]
	 456  			}
	 457  			dst = append(dst, ch)
	 458  		}
	 459  	}
	 460  
	 461  	return dst
	 462  }
	 463  
	 464  // %b: -ddddddddp±ddd
	 465  func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	 466  	// sign
	 467  	if neg {
	 468  		dst = append(dst, '-')
	 469  	}
	 470  
	 471  	// mantissa
	 472  	dst, _ = formatBits(dst, mant, 10, false, true)
	 473  
	 474  	// p
	 475  	dst = append(dst, 'p')
	 476  
	 477  	// ±exponent
	 478  	exp -= int(flt.mantbits)
	 479  	if exp >= 0 {
	 480  		dst = append(dst, '+')
	 481  	}
	 482  	dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)
	 483  
	 484  	return dst
	 485  }
	 486  
	 487  // %x: -0x1.yyyyyyyyp±ddd or -0x0p+0. (y is hex digit, d is decimal digit)
	 488  func fmtX(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
	 489  	if mant == 0 {
	 490  		exp = 0
	 491  	}
	 492  
	 493  	// Shift digits so leading 1 (if any) is at bit 1<<60.
	 494  	mant <<= 60 - flt.mantbits
	 495  	for mant != 0 && mant&(1<<60) == 0 {
	 496  		mant <<= 1
	 497  		exp--
	 498  	}
	 499  
	 500  	// Round if requested.
	 501  	if prec >= 0 && prec < 15 {
	 502  		shift := uint(prec * 4)
	 503  		extra := (mant << shift) & (1<<60 - 1)
	 504  		mant >>= 60 - shift
	 505  		if extra|(mant&1) > 1<<59 {
	 506  			mant++
	 507  		}
	 508  		mant <<= 60 - shift
	 509  		if mant&(1<<61) != 0 {
	 510  			// Wrapped around.
	 511  			mant >>= 1
	 512  			exp++
	 513  		}
	 514  	}
	 515  
	 516  	hex := lowerhex
	 517  	if fmt == 'X' {
	 518  		hex = upperhex
	 519  	}
	 520  
	 521  	// sign, 0x, leading digit
	 522  	if neg {
	 523  		dst = append(dst, '-')
	 524  	}
	 525  	dst = append(dst, '0', fmt, '0'+byte((mant>>60)&1))
	 526  
	 527  	// .fraction
	 528  	mant <<= 4 // remove leading 0 or 1
	 529  	if prec < 0 && mant != 0 {
	 530  		dst = append(dst, '.')
	 531  		for mant != 0 {
	 532  			dst = append(dst, hex[(mant>>60)&15])
	 533  			mant <<= 4
	 534  		}
	 535  	} else if prec > 0 {
	 536  		dst = append(dst, '.')
	 537  		for i := 0; i < prec; i++ {
	 538  			dst = append(dst, hex[(mant>>60)&15])
	 539  			mant <<= 4
	 540  		}
	 541  	}
	 542  
	 543  	// p±
	 544  	ch := byte('P')
	 545  	if fmt == lower(fmt) {
	 546  		ch = 'p'
	 547  	}
	 548  	dst = append(dst, ch)
	 549  	if exp < 0 {
	 550  		ch = '-'
	 551  		exp = -exp
	 552  	} else {
	 553  		ch = '+'
	 554  	}
	 555  	dst = append(dst, ch)
	 556  
	 557  	// dd or ddd or dddd
	 558  	switch {
	 559  	case exp < 100:
	 560  		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
	 561  	case exp < 1000:
	 562  		dst = append(dst, byte(exp/100)+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
	 563  	default:
	 564  		dst = append(dst, byte(exp/1000)+'0', byte(exp/100)%10+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
	 565  	}
	 566  
	 567  	return dst
	 568  }
	 569  
	 570  func min(a, b int) int {
	 571  	if a < b {
	 572  		return a
	 573  	}
	 574  	return b
	 575  }
	 576  
	 577  func max(a, b int) int {
	 578  	if a > b {
	 579  		return a
	 580  	}
	 581  	return b
	 582  }
	 583
View as plain text