decimal.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  // 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  	d		 [800]byte // digits, big-endian representation
		16  	nd		int			 // number of digits used
		17  	dp		int			 // decimal point
		18  	neg	 bool			// negative flag
		19  	trunc bool			// discarded nonzero digits beyond d[:nd]
		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 [24]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  // Maximum shift that we can do in one pass without overflow.
	 105  // A uint has 32 or 64 bits, and we have to be able to accommodate 9<<k.
	 106  const uintSize = 32 << (^uint(0) >> 63)
	 107  const maxShift = uintSize - 4
	 108  
	 109  // Binary shift right (/ 2) by k bits.	k <= maxShift to avoid overflow.
	 110  func rightShift(a *decimal, k uint) {
	 111  	r := 0 // read pointer
	 112  	w := 0 // write pointer
	 113  
	 114  	// Pick up enough leading digits to cover first shift.
	 115  	var n uint
	 116  	for ; n>>k == 0; r++ {
	 117  		if r >= a.nd {
	 118  			if n == 0 {
	 119  				// a == 0; shouldn't get here, but handle anyway.
	 120  				a.nd = 0
	 121  				return
	 122  			}
	 123  			for n>>k == 0 {
	 124  				n = n * 10
	 125  				r++
	 126  			}
	 127  			break
	 128  		}
	 129  		c := uint(a.d[r])
	 130  		n = n*10 + c - '0'
	 131  	}
	 132  	a.dp -= r - 1
	 133  
	 134  	var mask uint = (1 << k) - 1
	 135  
	 136  	// Pick up a digit, put down a digit.
	 137  	for ; r < a.nd; r++ {
	 138  		c := uint(a.d[r])
	 139  		dig := n >> k
	 140  		n &= mask
	 141  		a.d[w] = byte(dig + '0')
	 142  		w++
	 143  		n = n*10 + c - '0'
	 144  	}
	 145  
	 146  	// Put down extra digits.
	 147  	for n > 0 {
	 148  		dig := n >> k
	 149  		n &= mask
	 150  		if w < len(a.d) {
	 151  			a.d[w] = byte(dig + '0')
	 152  			w++
	 153  		} else if dig > 0 {
	 154  			a.trunc = true
	 155  		}
	 156  		n = n * 10
	 157  	}
	 158  
	 159  	a.nd = w
	 160  	trim(a)
	 161  }
	 162  
	 163  // Cheat sheet for left shift: table indexed by shift count giving
	 164  // number of new digits that will be introduced by that shift.
	 165  //
	 166  // For example, leftcheats[4] = {2, "625"}.	That means that
	 167  // if we are shifting by 4 (multiplying by 16), it will add 2 digits
	 168  // when the string prefix is "625" through "999", and one fewer digit
	 169  // if the string prefix is "000" through "624".
	 170  //
	 171  // Credit for this trick goes to Ken.
	 172  
	 173  type leftCheat struct {
	 174  	delta	int		// number of new digits
	 175  	cutoff string // minus one digit if original < a.
	 176  }
	 177  
	 178  var leftcheats = []leftCheat{
	 179  	// Leading digits of 1/2^i = 5^i.
	 180  	// 5^23 is not an exact 64-bit floating point number,
	 181  	// so have to use bc for the math.
	 182  	// Go up to 60 to be large enough for 32bit and 64bit platforms.
	 183  	/*
	 184  		seq 60 | sed 's/^/5^/' | bc |
	 185  		awk 'BEGIN{ print "\t{ 0, \"\" }," }
	 186  		{
	 187  			log2 = log(2)/log(10)
	 188  			printf("\t{ %d, \"%s\" },\t// * %d\n",
	 189  				int(log2*NR+1), $0, 2**NR)
	 190  		}'
	 191  	*/
	 192  	{0, ""},
	 193  	{1, "5"},																					 // * 2
	 194  	{1, "25"},																					// * 4
	 195  	{1, "125"},																				 // * 8
	 196  	{2, "625"},																				 // * 16
	 197  	{2, "3125"},																				// * 32
	 198  	{2, "15625"},																			 // * 64
	 199  	{3, "78125"},																			 // * 128
	 200  	{3, "390625"},																			// * 256
	 201  	{3, "1953125"},																		 // * 512
	 202  	{4, "9765625"},																		 // * 1024
	 203  	{4, "48828125"},																		// * 2048
	 204  	{4, "244140625"},																	 // * 4096
	 205  	{4, "1220703125"},																	// * 8192
	 206  	{5, "6103515625"},																	// * 16384
	 207  	{5, "30517578125"},																 // * 32768
	 208  	{5, "152587890625"},																// * 65536
	 209  	{6, "762939453125"},																// * 131072
	 210  	{6, "3814697265625"},															 // * 262144
	 211  	{6, "19073486328125"},															// * 524288
	 212  	{7, "95367431640625"},															// * 1048576
	 213  	{7, "476837158203125"},														 // * 2097152
	 214  	{7, "2384185791015625"},														// * 4194304
	 215  	{7, "11920928955078125"},													 // * 8388608
	 216  	{8, "59604644775390625"},													 // * 16777216
	 217  	{8, "298023223876953125"},													// * 33554432
	 218  	{8, "1490116119384765625"},												 // * 67108864
	 219  	{9, "7450580596923828125"},												 // * 134217728
	 220  	{9, "37252902984619140625"},												// * 268435456
	 221  	{9, "186264514923095703125"},											 // * 536870912
	 222  	{10, "931322574615478515625"},											// * 1073741824
	 223  	{10, "4656612873077392578125"},										 // * 2147483648
	 224  	{10, "23283064365386962890625"},										// * 4294967296
	 225  	{10, "116415321826934814453125"},									 // * 8589934592
	 226  	{11, "582076609134674072265625"},									 // * 17179869184
	 227  	{11, "2910383045673370361328125"},									// * 34359738368
	 228  	{11, "14551915228366851806640625"},								 // * 68719476736
	 229  	{12, "72759576141834259033203125"},								 // * 137438953472
	 230  	{12, "363797880709171295166015625"},								// * 274877906944
	 231  	{12, "1818989403545856475830078125"},							 // * 549755813888
	 232  	{13, "9094947017729282379150390625"},							 // * 1099511627776
	 233  	{13, "45474735088646411895751953125"},							// * 2199023255552
	 234  	{13, "227373675443232059478759765625"},						 // * 4398046511104
	 235  	{13, "1136868377216160297393798828125"},						// * 8796093022208
	 236  	{14, "5684341886080801486968994140625"},						// * 17592186044416
	 237  	{14, "28421709430404007434844970703125"},					 // * 35184372088832
	 238  	{14, "142108547152020037174224853515625"},					// * 70368744177664
	 239  	{15, "710542735760100185871124267578125"},					// * 140737488355328
	 240  	{15, "3552713678800500929355621337890625"},				 // * 281474976710656
	 241  	{15, "17763568394002504646778106689453125"},				// * 562949953421312
	 242  	{16, "88817841970012523233890533447265625"},				// * 1125899906842624
	 243  	{16, "444089209850062616169452667236328125"},			 // * 2251799813685248
	 244  	{16, "2220446049250313080847263336181640625"},			// * 4503599627370496
	 245  	{16, "11102230246251565404236316680908203125"},		 // * 9007199254740992
	 246  	{17, "55511151231257827021181583404541015625"},		 // * 18014398509481984
	 247  	{17, "277555756156289135105907917022705078125"},		// * 36028797018963968
	 248  	{17, "1387778780781445675529539585113525390625"},	 // * 72057594037927936
	 249  	{18, "6938893903907228377647697925567626953125"},	 // * 144115188075855872
	 250  	{18, "34694469519536141888238489627838134765625"},	// * 288230376151711744
	 251  	{18, "173472347597680709441192448139190673828125"}, // * 576460752303423488
	 252  	{19, "867361737988403547205962240695953369140625"}, // * 1152921504606846976
	 253  }
	 254  
	 255  // Is the leading prefix of b lexicographically less than s?
	 256  func prefixIsLessThan(b []byte, s string) bool {
	 257  	for i := 0; i < len(s); i++ {
	 258  		if i >= len(b) {
	 259  			return true
	 260  		}
	 261  		if b[i] != s[i] {
	 262  			return b[i] < s[i]
	 263  		}
	 264  	}
	 265  	return false
	 266  }
	 267  
	 268  // Binary shift left (* 2) by k bits.	k <= maxShift to avoid overflow.
	 269  func leftShift(a *decimal, k uint) {
	 270  	delta := leftcheats[k].delta
	 271  	if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) {
	 272  		delta--
	 273  	}
	 274  
	 275  	r := a.nd				 // read index
	 276  	w := a.nd + delta // write index
	 277  
	 278  	// Pick up a digit, put down a digit.
	 279  	var n uint
	 280  	for r--; r >= 0; r-- {
	 281  		n += (uint(a.d[r]) - '0') << k
	 282  		quo := n / 10
	 283  		rem := n - 10*quo
	 284  		w--
	 285  		if w < len(a.d) {
	 286  			a.d[w] = byte(rem + '0')
	 287  		} else if rem != 0 {
	 288  			a.trunc = true
	 289  		}
	 290  		n = quo
	 291  	}
	 292  
	 293  	// Put down extra digits.
	 294  	for n > 0 {
	 295  		quo := n / 10
	 296  		rem := n - 10*quo
	 297  		w--
	 298  		if w < len(a.d) {
	 299  			a.d[w] = byte(rem + '0')
	 300  		} else if rem != 0 {
	 301  			a.trunc = true
	 302  		}
	 303  		n = quo
	 304  	}
	 305  
	 306  	a.nd += delta
	 307  	if a.nd >= len(a.d) {
	 308  		a.nd = len(a.d)
	 309  	}
	 310  	a.dp += delta
	 311  	trim(a)
	 312  }
	 313  
	 314  // Binary shift left (k > 0) or right (k < 0).
	 315  func (a *decimal) Shift(k int) {
	 316  	switch {
	 317  	case a.nd == 0:
	 318  		// nothing to do: a == 0
	 319  	case k > 0:
	 320  		for k > maxShift {
	 321  			leftShift(a, maxShift)
	 322  			k -= maxShift
	 323  		}
	 324  		leftShift(a, uint(k))
	 325  	case k < 0:
	 326  		for k < -maxShift {
	 327  			rightShift(a, maxShift)
	 328  			k += maxShift
	 329  		}
	 330  		rightShift(a, uint(-k))
	 331  	}
	 332  }
	 333  
	 334  // If we chop a at nd digits, should we round up?
	 335  func shouldRoundUp(a *decimal, nd int) bool {
	 336  	if nd < 0 || nd >= a.nd {
	 337  		return false
	 338  	}
	 339  	if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even
	 340  		// if we truncated, a little higher than what's recorded - always round up
	 341  		if a.trunc {
	 342  			return true
	 343  		}
	 344  		return nd > 0 && (a.d[nd-1]-'0')%2 != 0
	 345  	}
	 346  	// not halfway - digit tells all
	 347  	return a.d[nd] >= '5'
	 348  }
	 349  
	 350  // Round a to nd digits (or fewer).
	 351  // If nd is zero, it means we're rounding
	 352  // just to the left of the digits, as in
	 353  // 0.09 -> 0.1.
	 354  func (a *decimal) Round(nd int) {
	 355  	if nd < 0 || nd >= a.nd {
	 356  		return
	 357  	}
	 358  	if shouldRoundUp(a, nd) {
	 359  		a.RoundUp(nd)
	 360  	} else {
	 361  		a.RoundDown(nd)
	 362  	}
	 363  }
	 364  
	 365  // Round a down to nd digits (or fewer).
	 366  func (a *decimal) RoundDown(nd int) {
	 367  	if nd < 0 || nd >= a.nd {
	 368  		return
	 369  	}
	 370  	a.nd = nd
	 371  	trim(a)
	 372  }
	 373  
	 374  // Round a up to nd digits (or fewer).
	 375  func (a *decimal) RoundUp(nd int) {
	 376  	if nd < 0 || nd >= a.nd {
	 377  		return
	 378  	}
	 379  
	 380  	// round up
	 381  	for i := nd - 1; i >= 0; i-- {
	 382  		c := a.d[i]
	 383  		if c < '9' { // can stop after this digit
	 384  			a.d[i]++
	 385  			a.nd = i + 1
	 386  			return
	 387  		}
	 388  	}
	 389  
	 390  	// Number is all 9s.
	 391  	// Change to single 1 with adjusted decimal point.
	 392  	a.d[0] = '1'
	 393  	a.nd = 1
	 394  	a.dp++
	 395  }
	 396  
	 397  // Extract integer part, rounded appropriately.
	 398  // No guarantees about overflow.
	 399  func (a *decimal) RoundedInteger() uint64 {
	 400  	if a.dp > 20 {
	 401  		return 0xFFFFFFFFFFFFFFFF
	 402  	}
	 403  	var i int
	 404  	n := uint64(0)
	 405  	for i = 0; i < a.dp && i < a.nd; i++ {
	 406  		n = n*10 + uint64(a.d[i]-'0')
	 407  	}
	 408  	for ; i < a.dp; i++ {
	 409  		n *= 10
	 410  	}
	 411  	if shouldRoundUp(a, a.dp) {
	 412  		n++
	 413  	}
	 414  	return n
	 415  }
	 416
View as plain text