From 079c00a475d11f71a69fe848dd67e8fe34ac88a8 Mon Sep 17 00:00:00 2001 From: Russ Cox Date: Mon, 17 Nov 2008 12:34:03 -0800 Subject: correctly rounded floating-point conversions in new package strconv. move atoi etc to strconv too. update fmt, etc to use strconv. R=r DELTA=2232 (1691 added, 424 deleted, 117 changed) OCL=19286 CL=19380 --- src/lib/strconv/decimal.go | 385 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 385 insertions(+) create mode 100644 src/lib/strconv/decimal.go (limited to 'src/lib/strconv/decimal.go') diff --git a/src/lib/strconv/decimal.go b/src/lib/strconv/decimal.go new file mode 100644 index 0000000000..ee6dd0e780 --- /dev/null +++ b/src/lib/strconv/decimal.go @@ -0,0 +1,385 @@ +// Copyright 2009 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. + +// Multiprecision decimal numbers. +// For floating-point formatting only; not general purpose. +// Only operations are assign and (binary) left/right shift. +// Can do binary floating point in multiprecision decimal precisely +// because 2 divides 10; cannot do decimal floating point +// in multiprecision binary precisely. + +package strconv + +package type Decimal struct { + // TODO(rsc): Can make d[] a bit smaller and add + // truncated bool; + d [2000] byte; // digits + nd int; // number of digits used + dp int; // decimal point +}; +func (a *Decimal) String() string; +func (a *Decimal) Assign(v uint64); +func (a *Decimal) Shift(k int) *Decimal; +func (a *Decimal) Round(nd int) *Decimal; +func (a *Decimal) RoundUp(nd int) *Decimal; +func (a *Decimal) RoundDown(nd int) *Decimal; +func (a *Decimal) RoundedInteger() uint64; + + +func Copy(dst *[]byte, src *[]byte) int; +func DigitZero(dst *[]byte) int; + +func (a *Decimal) String() string { + n := 10 + a.nd; + if a.dp > 0 { + n += a.dp; + } + if a.dp < 0 { + n += -a.dp; + } + + buf := new([]byte, n); + w := 0; + switch { + case a.dp <= 0: + // zeros fill space between decimal point and digits + buf[w] = '0'; + w++; + buf[w] = '.'; + w++; + w += DigitZero(buf[w:w+-a.dp]); + w += Copy(buf[w:w+a.nd], (&a.d)[0:a.nd]); + + case a.dp < a.nd: + // decimal point in middle of digits + w += Copy(buf[w:w+a.dp], (&a.d)[0:a.dp]); + buf[w] = '.'; + w++; + w += Copy(buf[w:w+a.nd-a.dp], (&a.d)[a.dp:a.nd]); + + default: + // zeros fill space between digits and decimal point + w += Copy(buf[w:w+a.nd], (&a.d)[0:a.nd]); + w += DigitZero(buf[w:w+a.dp-a.nd]); + } + return string(buf[0:w]); +} + +func Copy(dst *[]byte, src *[]byte) int { + for i := 0; i < len(dst); i++ { + dst[i] = src[i]; + } + return len(dst); +} + +func DigitZero(dst *[]byte) int { + for i := 0; i < len(dst); i++ { + dst[i] = '0'; + } + return len(dst); +} + +// Trim trailing zeros from number. +// (They are meaningless; the decimal point is tracked +// independent of the number of digits.) +func Trim(a *Decimal) { + for a.nd > 0 && a.d[a.nd-1] == '0' { + a.nd--; + } + if a.nd == 0 { + a.dp = 0; + } +} + +// Assign v to a. +func (a *Decimal) Assign(v uint64) { + var buf [50]byte; + + // Write reversed decimal in buf. + n := 0; + for v > 0 { + v1 := v/10; + v -= 10*v1; + buf[n] = byte(v + '0'); + n++; + v = v1; + } + + // Reverse again to produce forward decimal in a.d. + a.nd = 0; + for n--; n>=0; n-- { + a.d[a.nd] = buf[n]; + a.nd++; + } + a.dp = a.nd; + Trim(a); +} + +package func NewDecimal(i uint64) *Decimal { + a := new(Decimal); + a.Assign(i); + return a; +} + +// Maximum shift that we can do in one pass without overflow. +// Signed int has 31 bits, and we have to be able to accomodate 9<>k == 0; r++ { + if r >= a.nd { + if n == 0 { + a.nd = 0; + return; + } + for n >> k == 0 { + n = n*10; + r++; + } + break; + } + c := int(a.d[r]); + n = n*10 + c-'0'; + } + a.dp -= r-1; + + // Pick up a digit, put down a digit. + for ; r < a.nd; r++ { + c := int(a.d[r]); + dig := n>>k; + n -= dig< 0 { + dig := n>>k; + n -= dig<= len(b) { + return true; + } + if b[i] != s[i] { + return b[i] < s[i]; + } + } + return false; +} + +// Binary shift left (/ 2) by k bits. k <= MaxShift to avoid overflow. +func LeftShift(a *Decimal, k uint) { + delta := leftcheat[k].delta; + if PrefixIsLessThan((&a.d)[0:a.nd], leftcheat[k].cutoff) { + delta--; + } + + r := a.nd; // read index + w := a.nd + delta; // write index + n := 0; + + // Pick up a digit, put down a digit. + for r--; r >= 0; r-- { + n += (int(a.d[r])-'0') << k; + quo := n/10; + rem := n - 10*quo; + w--; + a.d[w] = byte(rem+'0'); + n = quo; + } + + // Put down extra digits. + for n > 0 { + quo := n/10; + rem := n - 10*quo; + w--; + a.d[w] = byte(rem+'0'); + n = quo; + } + + if w != 0 { + // TODO: Remove - has no business panicking. + panic("fmt: bad LeftShift"); + } + a.nd += delta; + a.dp += delta; + Trim(a); +} + +// Binary shift left (k > 0) or right (k < 0). +// Returns receiver for convenience. +func (a *Decimal) Shift(k int) *Decimal { + switch { + case k > 0: + for k > MaxShift { + LeftShift(a, MaxShift); + k -= MaxShift; + } + LeftShift(a, uint(k)); + case k < 0: + for k < -MaxShift { + RightShift(a, MaxShift); + k += MaxShift; + } + RightShift(a, uint(-k)); + } + return a; +} + +// If we chop a at nd digits, should we round up? +func ShouldRoundUp(a *Decimal, nd int) bool { + if nd <= 0 || nd >= a.nd { + return false; + } + if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even + return (a.d[nd-1] - '0') % 2 != 0; + } + // not halfway - digit tells all + return a.d[nd] >= '5'; +} + +// Round a to nd digits (or fewer). +// Returns receiver for convenience. +func (a *Decimal) Round(nd int) *Decimal { + if nd <= 0 || nd >= a.nd { + return a; + } + if(ShouldRoundUp(a, nd)) { + return a.RoundUp(nd); + } + return a.RoundDown(nd); +} + +// Round a down to nd digits (or fewer). +// Returns receiver for convenience. +func (a *Decimal) RoundDown(nd int) *Decimal { + if nd <= 0 || nd >= a.nd { + return a; + } + a.nd = nd; + Trim(a); + return a; +} + +// Round a up to nd digits (or fewer). +// Returns receiver for convenience. +func (a *Decimal) RoundUp(nd int) *Decimal { + if nd <= 0 || nd >= a.nd { + return a; + } + + // round up + for i := nd-1; i >= 0; i-- { + c := a.d[i]; + if c < '9' { // can stop after this digit + a.d[i]++; + a.nd = i+1; + return a; + } + } + + // Number is all 9s. + // Change to single 1 with adjusted decimal point. + a.d[0] = '1'; + a.nd = 1; + a.dp++; + return a; +} + +// Extract integer part, rounded appropriately. +// No guarantees about overflow. +func (a *Decimal) RoundedInteger() uint64 { + if a.dp > 20 { + return 0xFFFFFFFFFFFFFFFF; + } + var i int; + n := uint64(0); + for i = 0; i < a.dp && i < a.nd; i++ { + n = n*10 + uint64(a.d[i] - '0'); + } + for ; i < a.dp; i++ { + n *= 10; + } + if ShouldRoundUp(a, a.dp) { + n++; + } + return n; +} + -- cgit v1.3