The Go Programming Language

Source file src/pkg/strconv/decimal.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	// Multiprecision decimal numbers.
     6	// For floating-point formatting only; not general purpose.
     7	// Only operations are assign and (binary) left/right shift.
     8	// Can do binary floating point in multiprecision decimal precisely
     9	// because 2 divides 10; cannot do decimal floating point
    10	// in multiprecision binary precisely.
    11	
    12	package strconv
    13	
    14	type decimal struct {
    15		// TODO(rsc): Can make d[] a bit smaller and add
    16		// truncated bool;
    17		d  [2000]byte // digits
    18		nd int        // number of digits used
    19		dp int        // decimal point
    20	}
    21	
    22	func (a *decimal) String() string {
    23		n := 10 + a.nd
    24		if a.dp > 0 {
    25			n += a.dp
    26		}
    27		if a.dp < 0 {
    28			n += -a.dp
    29		}
    30	
    31		buf := make([]byte, n)
    32		w := 0
    33		switch {
    34		case a.nd == 0:
    35			return "0"
    36	
    37		case a.dp <= 0:
    38			// zeros fill space between decimal point and digits
    39			buf[w] = '0'
    40			w++
    41			buf[w] = '.'
    42			w++
    43			w += digitZero(buf[w : w+-a.dp])
    44			w += copy(buf[w:], a.d[0:a.nd])
    45	
    46		case a.dp < a.nd:
    47			// decimal point in middle of digits
    48			w += copy(buf[w:], a.d[0:a.dp])
    49			buf[w] = '.'
    50			w++
    51			w += copy(buf[w:], a.d[a.dp:a.nd])
    52	
    53		default:
    54			// zeros fill space between digits and decimal point
    55			w += copy(buf[w:], a.d[0:a.nd])
    56			w += digitZero(buf[w : w+a.dp-a.nd])
    57		}
    58		return string(buf[0:w])
    59	}
    60	
    61	func digitZero(dst []byte) int {
    62		for i := range dst {
    63			dst[i] = '0'
    64		}
    65		return len(dst)
    66	}
    67	
    68	// trim trailing zeros from number.
    69	// (They are meaningless; the decimal point is tracked
    70	// independent of the number of digits.)
    71	func trim(a *decimal) {
    72		for a.nd > 0 && a.d[a.nd-1] == '0' {
    73			a.nd--
    74		}
    75		if a.nd == 0 {
    76			a.dp = 0
    77		}
    78	}
    79	
    80	// Assign v to a.
    81	func (a *decimal) Assign(v uint64) {
    82		var buf [50]byte
    83	
    84		// Write reversed decimal in buf.
    85		n := 0
    86		for v > 0 {
    87			v1 := v / 10
    88			v -= 10 * v1
    89			buf[n] = byte(v + '0')
    90			n++
    91			v = v1
    92		}
    93	
    94		// Reverse again to produce forward decimal in a.d.
    95		a.nd = 0
    96		for n--; n >= 0; n-- {
    97			a.d[a.nd] = buf[n]
    98			a.nd++
    99		}
   100		a.dp = a.nd
   101		trim(a)
   102	}
   103	
   104	func newDecimal(i uint64) *decimal {
   105		a := new(decimal)
   106		a.Assign(i)
   107		return a
   108	}
   109	
   110	// Maximum shift that we can do in one pass without overflow.
   111	// Signed int has 31 bits, and we have to be able to accommodate 9<<k.
   112	const maxShift = 27
   113	
   114	// Binary shift right (* 2) by k bits.  k <= maxShift to avoid overflow.
   115	func rightShift(a *decimal, k uint) {
   116		r := 0 // read pointer
   117		w := 0 // write pointer
   118	
   119		// Pick up enough leading digits to cover first shift.
   120		n := 0
   121		for ; n>>k == 0; r++ {
   122			if r >= a.nd {
   123				if n == 0 {
   124					// a == 0; shouldn't get here, but handle anyway.
   125					a.nd = 0
   126					return
   127				}
   128				for n>>k == 0 {
   129					n = n * 10
   130					r++
   131				}
   132				break
   133			}
   134			c := int(a.d[r])
   135			n = n*10 + c - '0'
   136		}
   137		a.dp -= r - 1
   138	
   139		// Pick up a digit, put down a digit.
   140		for ; r < a.nd; r++ {
   141			c := int(a.d[r])
   142			dig := n >> k
   143			n -= dig << k
   144			a.d[w] = byte(dig + '0')
   145			w++
   146			n = n*10 + c - '0'
   147		}
   148	
   149		// Put down extra digits.
   150		for n > 0 {
   151			dig := n >> k
   152			n -= dig << k
   153			a.d[w] = byte(dig + '0')
   154			w++
   155			n = n * 10
   156		}
   157	
   158		a.nd = w
   159		trim(a)
   160	}
   161	
   162	// Cheat sheet for left shift: table indexed by shift count giving
   163	// number of new digits that will be introduced by that shift.
   164	//
   165	// For example, leftcheats[4] = {2, "625"}.  That means that
   166	// if we are shifting by 4 (multiplying by 16), it will add 2 digits
   167	// when the string prefix is "625" through "999", and one fewer digit
   168	// if the string prefix is "000" through "624".
   169	//
   170	// Credit for this trick goes to Ken.
   171	
   172	type leftCheat struct {
   173		delta  int    // number of new digits
   174		cutoff string //   minus one digit if original < a.
   175	}
   176	
   177	var leftcheats = []leftCheat{
   178		// Leading digits of 1/2^i = 5^i.
   179		// 5^23 is not an exact 64-bit floating point number,
   180		// so have to use bc for the math.
   181		/*
   182			seq 27 | sed 's/^/5^/' | bc |
   183			awk 'BEGIN{ print "\tleftCheat{ 0, \"\" }," }
   184			{
   185				log2 = log(2)/log(10)
   186				printf("\tleftCheat{ %d, \"%s\" },\t// * %d\n",
   187					int(log2*NR+1), $0, 2**NR)
   188			}'
   189		*/
   190		{0, ""},
   191		{1, "5"},                   // * 2
   192		{1, "25"},                  // * 4
   193		{1, "125"},                 // * 8
   194		{2, "625"},                 // * 16
   195		{2, "3125"},                // * 32
   196		{2, "15625"},               // * 64
   197		{3, "78125"},               // * 128
   198		{3, "390625"},              // * 256
   199		{3, "1953125"},             // * 512
   200		{4, "9765625"},             // * 1024
   201		{4, "48828125"},            // * 2048
   202		{4, "244140625"},           // * 4096
   203		{4, "1220703125"},          // * 8192
   204		{5, "6103515625"},          // * 16384
   205		{5, "30517578125"},         // * 32768
   206		{5, "152587890625"},        // * 65536
   207		{6, "762939453125"},        // * 131072
   208		{6, "3814697265625"},       // * 262144
   209		{6, "19073486328125"},      // * 524288
   210		{7, "95367431640625"},      // * 1048576
   211		{7, "476837158203125"},     // * 2097152
   212		{7, "2384185791015625"},    // * 4194304
   213		{7, "11920928955078125"},   // * 8388608
   214		{8, "59604644775390625"},   // * 16777216
   215		{8, "298023223876953125"},  // * 33554432
   216		{8, "1490116119384765625"}, // * 67108864
   217		{9, "7450580596923828125"}, // * 134217728
   218	}
   219	
   220	// Is the leading prefix of b lexicographically less than s?
   221	func prefixIsLessThan(b []byte, s string) bool {
   222		for i := 0; i < len(s); i++ {
   223			if i >= len(b) {
   224				return true
   225			}
   226			if b[i] != s[i] {
   227				return b[i] < s[i]
   228			}
   229		}
   230		return false
   231	}
   232	
   233	// Binary shift left (/ 2) by k bits.  k <= maxShift to avoid overflow.
   234	func leftShift(a *decimal, k uint) {
   235		delta := leftcheats[k].delta
   236		if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {
   237			delta--
   238		}
   239	
   240		r := a.nd         // read index
   241		w := a.nd + delta // write index
   242		n := 0
   243	
   244		// Pick up a digit, put down a digit.
   245		for r--; r >= 0; r-- {
   246			n += (int(a.d[r]) - '0') << k
   247			quo := n / 10
   248			rem := n - 10*quo
   249			w--
   250			a.d[w] = byte(rem + '0')
   251			n = quo
   252		}
   253	
   254		// Put down extra digits.
   255		for n > 0 {
   256			quo := n / 10
   257			rem := n - 10*quo
   258			w--
   259			a.d[w] = byte(rem + '0')
   260			n = quo
   261		}
   262	
   263		a.nd += delta
   264		a.dp += delta
   265		trim(a)
   266	}
   267	
   268	// Binary shift left (k > 0) or right (k < 0).
   269	// Returns receiver for convenience.
   270	func (a *decimal) Shift(k int) *decimal {
   271		switch {
   272		case a.nd == 0:
   273			// nothing to do: a == 0
   274		case k > 0:
   275			for k > maxShift {
   276				leftShift(a, maxShift)
   277				k -= maxShift
   278			}
   279			leftShift(a, uint(k))
   280		case k < 0:
   281			for k < -maxShift {
   282				rightShift(a, maxShift)
   283				k += maxShift
   284			}
   285			rightShift(a, uint(-k))
   286		}
   287		return a
   288	}
   289	
   290	// If we chop a at nd digits, should we round up?
   291	func shouldRoundUp(a *decimal, nd int) bool {
   292		if nd < 0 || nd >= a.nd {
   293			return false
   294		}
   295		if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even
   296			return nd > 0 && (a.d[nd-1]-'0')%2 != 0
   297		}
   298		// not halfway - digit tells all
   299		return a.d[nd] >= '5'
   300	}
   301	
   302	// Round a to nd digits (or fewer).
   303	// Returns receiver for convenience.
   304	// If nd is zero, it means we're rounding
   305	// just to the left of the digits, as in
   306	// 0.09 -> 0.1.
   307	func (a *decimal) Round(nd int) *decimal {
   308		if nd < 0 || nd >= a.nd {
   309			return a
   310		}
   311		if shouldRoundUp(a, nd) {
   312			return a.RoundUp(nd)
   313		}
   314		return a.RoundDown(nd)
   315	}
   316	
   317	// Round a down to nd digits (or fewer).
   318	// Returns receiver for convenience.
   319	func (a *decimal) RoundDown(nd int) *decimal {
   320		if nd < 0 || nd >= a.nd {
   321			return a
   322		}
   323		a.nd = nd
   324		trim(a)
   325		return a
   326	}
   327	
   328	// Round a up to nd digits (or fewer).
   329	// Returns receiver for convenience.
   330	func (a *decimal) RoundUp(nd int) *decimal {
   331		if nd < 0 || nd >= a.nd {
   332			return a
   333		}
   334	
   335		// round up
   336		for i := nd - 1; i >= 0; i-- {
   337			c := a.d[i]
   338			if c < '9' { // can stop after this digit
   339				a.d[i]++
   340				a.nd = i + 1
   341				return a
   342			}
   343		}
   344	
   345		// Number is all 9s.
   346		// Change to single 1 with adjusted decimal point.
   347		a.d[0] = '1'
   348		a.nd = 1
   349		a.dp++
   350		return a
   351	}
   352	
   353	// Extract integer part, rounded appropriately.
   354	// No guarantees about overflow.
   355	func (a *decimal) RoundedInteger() uint64 {
   356		if a.dp > 20 {
   357			return 0xFFFFFFFFFFFFFFFF
   358		}
   359		var i int
   360		n := uint64(0)
   361		for i = 0; i < a.dp && i < a.nd; i++ {
   362			n = n*10 + uint64(a.d[i]-'0')
   363		}
   364		for ; i < a.dp; i++ {
   365			n *= 10
   366		}
   367		if shouldRoundUp(a, a.dp) {
   368			n++
   369		}
   370		return n
   371	}

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.