blob: 716f03bfa43398019aa67d65958b5c28ac141ee1 [file] [log] [blame]
 // Copyright 2015 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. // This file implements multi-precision decimal numbers. // The implementation is for float to decimal conversion only; // not general purpose use. // The only operations are precise conversion from binary to // decimal and rounding. // // The key observation and some code (shr) is borrowed from // strconv/decimal.go: conversion of binary fractional values can be done // precisely in multi-precision decimal because 2 divides 10 (required for // >> of mantissa); but conversion of decimal floating-point values cannot // be done precisely in binary representation. // // In contrast to strconv/decimal.go, only right shift is implemented in // decimal format - left shift can be done precisely in binary format. package big // A decimal represents an unsigned floating-point number in decimal representation. // The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1, // with the most-significant mantissa digit at index 0. For the zero decimal, the // mantissa length and exponent are 0. // The zero value for decimal represents a ready-to-use 0.0. type decimal struct { mant []byte // mantissa ASCII digits, big-endian exp int // exponent } // at returns the i'th mantissa digit, starting with the most significant digit at 0. func (d *decimal) at(i int) byte { if 0 <= i && i < len(d.mant) { return d.mant[i] } return '0' } // Maximum shift amount that can be done in one pass without overflow. // A Word has _W bits and (1<= 0), or m >> -shift (for shift < 0). func (x *decimal) init(m nat, shift int) { // special case 0 if len(m) == 0 { x.mant = x.mant[:0] x.exp = 0 return } // Optimization: If we need to shift right, first remove any trailing // zero bits from m to reduce shift amount that needs to be done in // decimal format (since that is likely slower). if shift < 0 { ntz := m.trailingZeroBits() s := uint(-shift) if s >= ntz { s = ntz // shift at most ntz bits } m = nat(nil).shr(m, s) shift += int(s) } // Do any shift left in binary representation. if shift > 0 { m = nat(nil).shl(m, uint(shift)) shift = 0 } // Convert mantissa into decimal representation. s := m.utoa(10) n := len(s) x.exp = n // Trim trailing zeros; instead the exponent is tracking // the decimal point independent of the number of digits. for n > 0 && s[n-1] == '0' { n-- } x.mant = append(x.mant[:0], s[:n]...) // Do any (remaining) shift right in decimal representation. if shift < 0 { for shift < -maxShift { shr(x, maxShift) shift += maxShift } shr(x, uint(-shift)) } } // shr implements x >> s, for s <= maxShift. func shr(x *decimal, s uint) { // Division by 1<>s == 0 && r < len(x.mant) { ch := Word(x.mant[r]) r++ n = n*10 + ch - '0' } if n == 0 { // x == 0; shouldn't get here, but handle anyway x.mant = x.mant[:0] return } for n>>s == 0 { r++ n *= 10 } x.exp += 1 - r // read a digit, write a digit w := 0 // write index mask := Word(1)<> s n &= mask // n -= d << s x.mant[w] = byte(d + '0') w++ n = n*10 + ch - '0' } // write extra digits that still fit for n > 0 && w < len(x.mant) { d := n >> s n &= mask x.mant[w] = byte(d + '0') w++ n = n * 10 } x.mant = x.mant[:w] // the number may be shorter (e.g. 1024 >> 10) // append additional digits that didn't fit for n > 0 { d := n >> s n &= mask x.mant = append(x.mant, byte(d+'0')) n = n * 10 } trim(x) } func (x *decimal) String() string { if len(x.mant) == 0 { return "0" } var buf []byte switch { case x.exp <= 0: // 0.00ddd buf = make([]byte, 0, 2+(-x.exp)+len(x.mant)) buf = append(buf, "0."...) buf = appendZeros(buf, -x.exp) buf = append(buf, x.mant...) case /* 0 < */ x.exp < len(x.mant): // dd.ddd buf = make([]byte, 0, 1+len(x.mant)) buf = append(buf, x.mant[:x.exp]...) buf = append(buf, '.') buf = append(buf, x.mant[x.exp:]...) default: // len(x.mant) <= x.exp // ddd00 buf = make([]byte, 0, x.exp) buf = append(buf, x.mant...) buf = appendZeros(buf, x.exp-len(x.mant)) } return string(buf) } // appendZeros appends n 0 digits to buf and returns buf. func appendZeros(buf []byte, n int) []byte { for ; n > 0; n-- { buf = append(buf, '0') } return buf } // shouldRoundUp reports if x should be rounded up // if shortened to n digits. n must be a valid index // for x.mant. func shouldRoundUp(x *decimal, n int) bool { if x.mant[n] == '5' && n+1 == len(x.mant) { // exactly halfway - round to even return n > 0 && (x.mant[n-1]-'0')&1 != 0 } // not halfway - digit tells all (x.mant has no trailing zeros) return x.mant[n] >= '5' } // round sets x to (at most) n mantissa digits by rounding it // to the nearest even value with n (or fever) mantissa digits. // If n < 0, x remains unchanged. func (x *decimal) round(n int) { if n < 0 || n >= len(x.mant) { return // nothing to do } if shouldRoundUp(x, n) { x.roundUp(n) } else { x.roundDown(n) } } func (x *decimal) roundUp(n int) { if n < 0 || n >= len(x.mant) { return // nothing to do } // 0 <= n < len(x.mant) // find first digit < '9' for n > 0 && x.mant[n-1] >= '9' { n-- } if n == 0 { // all digits are '9's => round up to '1' and update exponent x.mant[0] = '1' // ok since len(x.mant) > n x.mant = x.mant[:1] x.exp++ return } // n > 0 && x.mant[n-1] < '9' x.mant[n-1]++ x.mant = x.mant[:n] // x already trimmed } func (x *decimal) roundDown(n int) { if n < 0 || n >= len(x.mant) { return // nothing to do } x.mant = x.mant[:n] trim(x) } // trim cuts off any trailing zeros from x's mantissa; // they are meaningless for the value of x. func trim(x *decimal) { i := len(x.mant) for i > 0 && x.mant[i-1] == '0' { i-- } x.mant = x.mant[:i] if i == 0 { x.exp = 0 } }