src/internal/strconv/ftoafixed.go - go.git - Git at Google

 // Copyright 2025 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.

 package strconv

 import "math/bits"

 var uint64pow10 = [...]uint64{
 	1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
 	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
 }

 // fixedFtoa formats a number of decimal digits of mant*(2^exp) into d,
 // where mant > 0 and 1 ≤ digits ≤ 18.
 // If fmt == 'f', digits is a conservative overestimate, and the final
 // number of digits is prec past the decimal point.
 func fixedFtoa(d *decimalSlice, mant uint64, exp, digits, prec int, fmt byte) {
 	// The strategy here is to multiply (mant * 2^exp) by a power of 10
 	// to make the resulting integer be the number of digits we want.
 	//
 	// Adams proved in the Ryu paper that 128-bit precision in the
 	// power-of-10 constant is sufficient to produce correctly
 	// rounded output for all float64s, up to 18 digits.
 	// https://dl.acm.org/doi/10.1145/3192366.3192369
 	//
 	// TODO(rsc): The paper is not focused on, nor terribly clear about,
 	// this fact in this context, and the proof seems too complicated.
 	// Post a shorter, more direct proof and link to it here.

 	if digits > 18 {
 		panic("fixedFtoa called with digits > 18")
 	}

 	// Shift mantissa to have 64 bits,
 	// so that the 192-bit product below will
 	// have at least 63 bits in its top word.
 	b := 64 - bits.Len64(mant)
 	mant <<= b
 	exp -= b

 	// We have f = mant * 2^exp ≥ 2^(63+exp)
 	// and we want to multiply it by some 10^p
 	// to make it have the number of digits plus one rounding bit:
 	//
 	//	2 * 10^(digits-1) ≤ f * 10^p < ~2 * 10^digits
 	//
 	// The lower bound is required, but the upper bound is approximate:
 	// we must not have too few digits, but we can round away extra ones.
 	//
 	//	f * 10^p ≥ 2 * 10^(digits-1)
 	//	10^p ≥ 2 * 10^(digits-1) / f                         [dividing by f]
 	//	p ≥ (log₁₀ 2) + (digits-1) - log₁₀ f                 [taking log₁₀]
 	//	p ≥ (log₁₀ 2) + (digits-1) - log₁₀ (mant * 2^exp)    [expanding f]
 	//	p ≥ (log₁₀ 2) + (digits-1) - (log₁₀ 2) * (64 + exp)  [mant < 2⁶⁴]
 	//	p ≥ (digits - 1) - (log₁₀ 2) * (63 + exp)            [refactoring]
 	//
 	// Once we have p, we can compute the scaled value:
 	//
 	//	dm * 2^de = mant * 2^exp * 10^p
 	//	          = mant * 2^exp * pow/2^128 * 2^exp2.
 	//	          = (mant * pow/2^128) * 2^(exp+exp2).
 	p := (digits - 1) - mulLog10_2(63+exp)
 	pow, exp2, ok := pow10(p)
 	if !ok {
 		// This never happens due to the range of float32/float64 exponent
 		panic("fixedFtoa: pow10 out of range")
 	}
 	if -22 <= p && p < 0 {
 		// Special case: Let q=-p. q is in [1,22]. We are dividing by 10^q
 		// and the mantissa may be a multiple of 5^q (5^22 < 2^53),
 		// in which case the division must be computed exactly and
 		// recorded as exact for correct rounding. Our normal computation is:
 		//
 		//	dm = floor(mant * floor(10^p * 2^s))
 		//
 		// for some scaling shift s. To make this an exact division,
 		// it suffices to change the inner floor to a ceil:
 		//
 		//	dm = floor(mant * ceil(10^p * 2^s))
 		//
 		// In the range of values we are using, the floor and ceil
 		// cancel each other out and the high 64 bits of the product
 		// come out exactly right.
 		// (This is the same trick compilers use for division by constants.
 		// See Hacker's Delight, 2nd ed., Chapter 10.)
 		pow.Lo++
 	}
 	dm, lo1, lo0 := umul192(mant, pow)
 	de := exp + exp2

 	// Check whether any bits have been truncated from dm.
 	// If so, set dt != 0. If not, leave dt == 0 (meaning dm is exact).
 	var dt uint
 	switch {
 	default:
 		// Most powers of 10 use a truncated constant,
 		// meaning the result is also truncated.
 		dt = 1
 	case 0 <= p && p <= 55:
 		// Small positive powers of 10 (up to 10⁵⁵) can be represented
 		// precisely in a 128-bit mantissa (5⁵⁵ ≤ 2¹²⁸), so the only truncation
 		// comes from discarding the low bits of the 192-bit product.
 		//
 		// TODO(rsc): The new proof mentioned above should also
 		// prove that we can't have lo1 == 0 and lo0 != 0.
 		// After proving that, drop computation and use of lo0 here.
 		dt = bool2uint(lo1|lo0 != 0)
 	case -22 <= p && p < 0 && divisiblePow5(mant, -p):
 		// If the original mantissa was a multiple of 5^p,
 		// the result is exact. (See comment above for pow.Lo++.)
 		dt = 0
 	}

 	// The value we want to format is dm * 2^de, where de < 0.
 	// Multply by 2^de by shifting, but leave one extra bit for rounding.
 	// After the shift, the "integer part" of dm is dm>>1,
 	// the "rounding bit" (the first fractional bit) is dm&1,
 	// and the "truncated bit" (have any bits been discarded?) is dt.
 	shift := -de - 1
 	dt |= bool2uint(dm&(1<<shift-1) != 0)
 	dm >>= shift

 	// Set decimal point in eventual formatted digits,
 	// so we can update it as we adjust the digits.
 	d.dp = digits - p

 	// Trim excess digit if any, updating truncation and decimal point.
 	// The << 1 is leaving room for the rounding bit.
 	max := uint64pow10[digits] << 1
 	if dm >= max {
 		var r uint
 		dm, r = dm/10, uint(dm%10)
 		dt |= bool2uint(r != 0)
 		d.dp++
 	}

 	// If this is %.*f we may have overestimated the digits needed.
 	// Now that we know where the decimal point is,
 	// trim to the actual number of digits, which is d.dp+prec.
 	if fmt == 'f' && digits != d.dp+prec {
 		for digits > d.dp+prec {
 			var r uint
 			dm, r = dm/10, uint(dm%10)
 			dt |= bool2uint(r != 0)
 			digits--
 		}

 		// Dropping those digits can create a new leftmost
 		// non-zero digit, like if we are formatting %.1f and
 		// convert 0.09 -> 0.1. Detect and adjust for that.
 		if digits <= 0 {
 			digits = 1
 			d.dp++
 		}

 		max = uint64pow10[digits] << 1
 	}

 	// Round and shift away rounding bit.
 	// We want to round up when
 	// (a) the fractional part is > 0.5 (dm&1 != 0 and dt == 1)
 	// (b) or the fractional part is ≥ 0.5 and the integer part is odd
 	//     (dm&1 != 0 and dm&2 != 0).
 	// The bitwise expression encodes that logic.
 	dm += uint64(uint(dm) & (dt | uint(dm)>>1) & 1)
 	dm >>= 1
 	if dm == max>>1 {
 		// 999... rolled over to 1000...
 		dm = uint64pow10[digits-1]
 		d.dp++
 	}

 	// Format digits into d.
 	if dm != 0 {
 		if formatBase10(d.d[:digits], dm) != 0 {
 			panic("formatBase10")
 		}
 		d.nd = digits
 		for d.d[d.nd-1] == '0' {
 			d.nd--
 		}
 	}
 }
	// Copyright 2025 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.

	package strconv

	import "math/bits"

	var uint64pow10 = [...]uint64{
	1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
	}

	// fixedFtoa formats a number of decimal digits of mant*(2^exp) into d,
	// where mant > 0 and 1 ≤ digits ≤ 18.
	// If fmt == 'f', digits is a conservative overestimate, and the final
	// number of digits is prec past the decimal point.
	func fixedFtoa(d *decimalSlice, mant uint64, exp, digits, prec int, fmt byte) {
	// The strategy here is to multiply (mant * 2^exp) by a power of 10
	// to make the resulting integer be the number of digits we want.
	//
	// Adams proved in the Ryu paper that 128-bit precision in the
	// power-of-10 constant is sufficient to produce correctly
	// rounded output for all float64s, up to 18 digits.
	// https://dl.acm.org/doi/10.1145/3192366.3192369
	//
	// TODO(rsc): The paper is not focused on, nor terribly clear about,
	// this fact in this context, and the proof seems too complicated.
	// Post a shorter, more direct proof and link to it here.

	if digits > 18 {
	panic("fixedFtoa called with digits > 18")
	}

	// Shift mantissa to have 64 bits,
	// so that the 192-bit product below will
	// have at least 63 bits in its top word.
	b := 64 - bits.Len64(mant)
	mant <<= b
	exp -= b

	// We have f = mant * 2^exp ≥ 2^(63+exp)
	// and we want to multiply it by some 10^p
	// to make it have the number of digits plus one rounding bit:
	//
	// 2 * 10^(digits-1) ≤ f * 10^p < ~2 * 10^digits
	//
	// The lower bound is required, but the upper bound is approximate:
	// we must not have too few digits, but we can round away extra ones.
	//
	// f * 10^p ≥ 2 * 10^(digits-1)
	// 10^p ≥ 2 * 10^(digits-1) / f [dividing by f]
	// p ≥ (log₁₀ 2) + (digits-1) - log₁₀ f [taking log₁₀]
	// p ≥ (log₁₀ 2) + (digits-1) - log₁₀ (mant * 2^exp) [expanding f]
	// p ≥ (log₁₀ 2) + (digits-1) - (log₁₀ 2) * (64 + exp) [mant < 2⁶⁴]
	// p ≥ (digits - 1) - (log₁₀ 2) * (63 + exp) [refactoring]
	//
	// Once we have p, we can compute the scaled value:
	//
	// dm * 2^de = mant * 2^exp * 10^p
	// = mant * 2^exp * pow/2^128 * 2^exp2.
	// = (mant * pow/2^128) * 2^(exp+exp2).
	p := (digits - 1) - mulLog10_2(63+exp)
	pow, exp2, ok := pow10(p)
	if !ok {
	// This never happens due to the range of float32/float64 exponent
	panic("fixedFtoa: pow10 out of range")
	}
	if -22 <= p && p < 0 {
	// Special case: Let q=-p. q is in [1,22]. We are dividing by 10^q
	// and the mantissa may be a multiple of 5^q (5^22 < 2^53),
	// in which case the division must be computed exactly and
	// recorded as exact for correct rounding. Our normal computation is:
	//
	// dm = floor(mant * floor(10^p * 2^s))
	//
	// for some scaling shift s. To make this an exact division,
	// it suffices to change the inner floor to a ceil:
	//
	// dm = floor(mant * ceil(10^p * 2^s))
	//
	// In the range of values we are using, the floor and ceil
	// cancel each other out and the high 64 bits of the product
	// come out exactly right.
	// (This is the same trick compilers use for division by constants.
	// See Hacker's Delight, 2nd ed., Chapter 10.)
	pow.Lo++
	}
	dm, lo1, lo0 := umul192(mant, pow)
	de := exp + exp2

	// Check whether any bits have been truncated from dm.
	// If so, set dt != 0. If not, leave dt == 0 (meaning dm is exact).
	var dt uint
	switch {
	default:
	// Most powers of 10 use a truncated constant,
	// meaning the result is also truncated.
	dt = 1
	case 0 <= p && p <= 55:
	// Small positive powers of 10 (up to 10⁵⁵) can be represented
	// precisely in a 128-bit mantissa (5⁵⁵ ≤ 2¹²⁸), so the only truncation
	// comes from discarding the low bits of the 192-bit product.
	//
	// TODO(rsc): The new proof mentioned above should also
	// prove that we can't have lo1 == 0 and lo0 != 0.
	// After proving that, drop computation and use of lo0 here.
	dt = bool2uint(lo1\|lo0 != 0)
	case -22 <= p && p < 0 && divisiblePow5(mant, -p):
	// If the original mantissa was a multiple of 5^p,
	// the result is exact. (See comment above for pow.Lo++.)
	dt = 0
	}

	// The value we want to format is dm * 2^de, where de < 0.
	// Multply by 2^de by shifting, but leave one extra bit for rounding.
	// After the shift, the "integer part" of dm is dm>>1,
	// the "rounding bit" (the first fractional bit) is dm&1,
	// and the "truncated bit" (have any bits been discarded?) is dt.
	shift := -de - 1
	dt \|= bool2uint(dm&(1<<shift-1) != 0)
	dm >>= shift

	// Set decimal point in eventual formatted digits,
	// so we can update it as we adjust the digits.
	d.dp = digits - p

	// Trim excess digit if any, updating truncation and decimal point.
	// The << 1 is leaving room for the rounding bit.
	max := uint64pow10[digits] << 1
	if dm >= max {
	var r uint
	dm, r = dm/10, uint(dm%10)
	dt \|= bool2uint(r != 0)
	d.dp++
	}

	// If this is %.*f we may have overestimated the digits needed.
	// Now that we know where the decimal point is,
	// trim to the actual number of digits, which is d.dp+prec.
	if fmt == 'f' && digits != d.dp+prec {
	for digits > d.dp+prec {
	var r uint
	dm, r = dm/10, uint(dm%10)
	dt \|= bool2uint(r != 0)
	digits--
	}

	// Dropping those digits can create a new leftmost
	// non-zero digit, like if we are formatting %.1f and
	// convert 0.09 -> 0.1. Detect and adjust for that.
	if digits <= 0 {
	digits = 1
	d.dp++
	}

	max = uint64pow10[digits] << 1
	}

	// Round and shift away rounding bit.
	// We want to round up when
	// (a) the fractional part is > 0.5 (dm&1 != 0 and dt == 1)
	// (b) or the fractional part is ≥ 0.5 and the integer part is odd
	// (dm&1 != 0 and dm&2 != 0).
	// The bitwise expression encodes that logic.
	dm += uint64(uint(dm) & (dt \| uint(dm)>>1) & 1)
	dm >>= 1
	if dm == max>>1 {
	// 999... rolled over to 1000...
	dm = uint64pow10[digits-1]
	d.dp++
	}

	// Format digits into d.
	if dm != 0 {
	if formatBase10(d.d[:digits], dm) != 0 {
	panic("formatBase10")
	}
	d.nd = digits
	for d.d[d.nd-1] == '0' {
	d.nd--
	}
	}
	}