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

type decimal struct {
	d     [800]byte // digits, big-endian representation
	nd    int       // number of digits used
	dp    int       // decimal point
	neg   bool      // negative flag
	trunc bool      // discarded nonzero digits beyond d[:nd]
}

func ( *decimal) () string {
	 := 10 + .nd
	if .dp > 0 {
		 += .dp
	}
	if .dp < 0 {
		 += -.dp
	}

	 := make([]byte, )
	 := 0
	switch {
	case .nd == 0:
		return "0"
zeros fill space between decimal point and digits
		[] = '0'
		++
		[] = '.'
		++
		 += digitZero([ : +-.dp])
		 += copy([:], .d[0:.nd])
decimal point in middle of digits
		 += copy([:], .d[0:.dp])
		[] = '.'
		++
		 += copy([:], .d[.dp:.nd])
zeros fill space between digits and decimal point
		 += copy([:], .d[0:.nd])
		 += digitZero([ : +.dp-.nd])
	}
	return string([0:])
}

func ( []byte) int {
	for  := range  {
		[] = '0'
	}
	return len()
}
trim trailing zeros from number. (They are meaningless; the decimal point is tracked independent of the number of digits.)
func ( *decimal) {
	for .nd > 0 && .d[.nd-1] == '0' {
		.nd--
	}
	if .nd == 0 {
		.dp = 0
	}
}
Assign v to a.
func ( *decimal) ( uint64) {
	var  [24]byte
Write reversed decimal in buf.
	 := 0
	for  > 0 {
		 :=  / 10
		 -= 10 * 
		[] = byte( + '0')
		++
		 = 
	}
Reverse again to produce forward decimal in a.d.
	.nd = 0
	for --;  >= 0; -- {
		.d[.nd] = []
		.nd++
	}
	.dp = .nd
	trim()
}
Maximum shift that we can do in one pass without overflow. A uint has 32 or 64 bits, and we have to be able to accommodate 9<<k.
const uintSize = 32 << (^uint(0) >> 63)
const maxShift = uintSize - 4
Binary shift right (/ 2) by k bits. k <= maxShift to avoid overflow.
func ( *decimal,  uint) {
	 := 0 // read pointer
	 := 0 // write pointer
Pick up enough leading digits to cover first shift.
	var  uint
	for ; >> == 0; ++ {
		if  >= .nd {
a == 0; shouldn't get here, but handle anyway.
				.nd = 0
				return
			}
			for >> == 0 {
				 =  * 10
				++
			}
			break
		}
		 := uint(.d[])
		 = *10 +  - '0'
	}
	.dp -=  - 1

	var  uint = (1 << ) - 1
Pick up a digit, put down a digit.
	for ;  < .nd; ++ {
		 := uint(.d[])
		 :=  >> 
		 &= 
		.d[] = byte( + '0')
		++
		 = *10 +  - '0'
	}
Put down extra digits.
	for  > 0 {
		 :=  >> 
		 &= 
		if  < len(.d) {
			.d[] = byte( + '0')
			++
		} else if  > 0 {
			.trunc = true
		}
		 =  * 10
	}

	.nd = 
	trim()
}
Cheat sheet for left shift: table indexed by shift count giving number of new digits that will be introduced by that shift. For example, leftcheats[4] = {2, "625"}. That means that if we are shifting by 4 (multiplying by 16), it will add 2 digits when the string prefix is "625" through "999", and one fewer digit if the string prefix is "000" through "624". Credit for this trick goes to Ken.

type leftCheat struct {
	delta  int    // number of new digits
	cutoff string // minus one digit if original < a.
}
Leading digits of 1/2^i = 5^i. 5^23 is not an exact 64-bit floating point number, so have to use bc for the math. Go up to 60 to be large enough for 32bit and 64bit platforms. seq 60 | sed 's/^/5^/' | bc | awk 'BEGIN{ print "\t{ 0, \"\" }," } { log2 = log(2)/log(10) printf("\t{ %d, \"%s\" },\t * %d\n", int(log2*NR+1), $0, 2**NR) }' 
	{0, ""},
	{1, "5"},                                           // * 2
	{1, "25"},                                          // * 4
	{1, "125"},                                         // * 8
	{2, "625"},                                         // * 16
	{2, "3125"},                                        // * 32
	{2, "15625"},                                       // * 64
	{3, "78125"},                                       // * 128
	{3, "390625"},                                      // * 256
	{3, "1953125"},                                     // * 512
	{4, "9765625"},                                     // * 1024
	{4, "48828125"},                                    // * 2048
	{4, "244140625"},                                   // * 4096
	{4, "1220703125"},                                  // * 8192
	{5, "6103515625"},                                  // * 16384
	{5, "30517578125"},                                 // * 32768
	{5, "152587890625"},                                // * 65536
	{6, "762939453125"},                                // * 131072
	{6, "3814697265625"},                               // * 262144
	{6, "19073486328125"},                              // * 524288
	{7, "95367431640625"},                              // * 1048576
	{7, "476837158203125"},                             // * 2097152
	{7, "2384185791015625"},                            // * 4194304
	{7, "11920928955078125"},                           // * 8388608
	{8, "59604644775390625"},                           // * 16777216
	{8, "298023223876953125"},                          // * 33554432
	{8, "1490116119384765625"},                         // * 67108864
	{9, "7450580596923828125"},                         // * 134217728
	{9, "37252902984619140625"},                        // * 268435456
	{9, "186264514923095703125"},                       // * 536870912
	{10, "931322574615478515625"},                      // * 1073741824
	{10, "4656612873077392578125"},                     // * 2147483648
	{10, "23283064365386962890625"},                    // * 4294967296
	{10, "116415321826934814453125"},                   // * 8589934592
	{11, "582076609134674072265625"},                   // * 17179869184
	{11, "2910383045673370361328125"},                  // * 34359738368
	{11, "14551915228366851806640625"},                 // * 68719476736
	{12, "72759576141834259033203125"},                 // * 137438953472
	{12, "363797880709171295166015625"},                // * 274877906944
	{12, "1818989403545856475830078125"},               // * 549755813888
	{13, "9094947017729282379150390625"},               // * 1099511627776
	{13, "45474735088646411895751953125"},              // * 2199023255552
	{13, "227373675443232059478759765625"},             // * 4398046511104
	{13, "1136868377216160297393798828125"},            // * 8796093022208
	{14, "5684341886080801486968994140625"},            // * 17592186044416
	{14, "28421709430404007434844970703125"},           // * 35184372088832
	{14, "142108547152020037174224853515625"},          // * 70368744177664
	{15, "710542735760100185871124267578125"},          // * 140737488355328
	{15, "3552713678800500929355621337890625"},         // * 281474976710656
	{15, "17763568394002504646778106689453125"},        // * 562949953421312
	{16, "88817841970012523233890533447265625"},        // * 1125899906842624
	{16, "444089209850062616169452667236328125"},       // * 2251799813685248
	{16, "2220446049250313080847263336181640625"},      // * 4503599627370496
	{16, "11102230246251565404236316680908203125"},     // * 9007199254740992
	{17, "55511151231257827021181583404541015625"},     // * 18014398509481984
	{17, "277555756156289135105907917022705078125"},    // * 36028797018963968
	{17, "1387778780781445675529539585113525390625"},   // * 72057594037927936
	{18, "6938893903907228377647697925567626953125"},   // * 144115188075855872
	{18, "34694469519536141888238489627838134765625"},  // * 288230376151711744
	{18, "173472347597680709441192448139190673828125"}, // * 576460752303423488
	{19, "867361737988403547205962240695953369140625"}, // * 1152921504606846976
}
Is the leading prefix of b lexicographically less than s?
func ( []byte,  string) bool {
	for  := 0;  < len(); ++ {
		if  >= len() {
			return true
		}
		if [] != [] {
			return [] < []
		}
	}
	return false
}
Binary shift left (* 2) by k bits. k <= maxShift to avoid overflow.
func ( *decimal,  uint) {
	 := leftcheats[].delta
	if prefixIsLessThan(.d[0:.nd], leftcheats[].cutoff) {
		--
	}

	 := .nd         // read index
	 := .nd +  // write index
Pick up a digit, put down a digit.
	var  uint
	for --;  >= 0; -- {
		 += (uint(.d[]) - '0') << 
		 :=  / 10
		 :=  - 10*
		--
		if  < len(.d) {
			.d[] = byte( + '0')
		} else if  != 0 {
			.trunc = true
		}
		 = 
	}
Put down extra digits.
	for  > 0 {
		 :=  / 10
		 :=  - 10*
		--
		if  < len(.d) {
			.d[] = byte( + '0')
		} else if  != 0 {
			.trunc = true
		}
		 = 
	}

	.nd += 
	if .nd >= len(.d) {
		.nd = len(.d)
	}
	.dp += 
	trim()
}
Binary shift left (k > 0) or right (k < 0).
func ( *decimal) ( int) {
	switch {
nothing to do: a == 0
	case  > 0:
		for  > maxShift {
			leftShift(, maxShift)
			 -= maxShift
		}
		leftShift(, uint())
	case  < 0:
		for  < -maxShift {
			rightShift(, maxShift)
			 += maxShift
		}
		rightShift(, uint(-))
	}
}
If we chop a at nd digits, should we round up?
func ( *decimal,  int) bool {
	if  < 0 ||  >= .nd {
		return false
	}
if we truncated, a little higher than what's recorded - always round up
		if .trunc {
			return true
		}
		return  > 0 && (.d[-1]-'0')%2 != 0
not halfway - digit tells all
	return .d[] >= '5'
}
Round a to nd digits (or fewer). If nd is zero, it means we're rounding just to the left of the digits, as in 0.09 -> 0.1.
func ( *decimal) ( int) {
	if  < 0 ||  >= .nd {
		return
	}
	if shouldRoundUp(, ) {
		.RoundUp()
	} else {
		.RoundDown()
	}
}
Round a down to nd digits (or fewer).
func ( *decimal) ( int) {
	if  < 0 ||  >= .nd {
		return
	}
	.nd = 
	trim()
}
Round a up to nd digits (or fewer).
func ( *decimal) ( int) {
	if  < 0 ||  >= .nd {
		return
	}
round up
	for  :=  - 1;  >= 0; -- {
		 := .d[]
		if  < '9' { // can stop after this digit
			.d[]++
			.nd =  + 1
			return
		}
	}
Number is all 9s. Change to single 1 with adjusted decimal point.
	.d[0] = '1'
	.nd = 1
	.dp++
}
Extract integer part, rounded appropriately. No guarantees about overflow.
func ( *decimal) () uint64 {
	if .dp > 20 {
		return 0xFFFFFFFFFFFFFFFF
	}
	var  int
	 := uint64(0)
	for  = 0;  < .dp &&  < .nd; ++ {
		 = *10 + uint64(.d[]-'0')
	}
	for ;  < .dp; ++ {
		 *= 10
	}
	if shouldRoundUp(, .dp) {
		++
	}
	return