// Use of this source code is governed by a BSD-style

// 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"

case .dp <= 0:
// zeros fill space between decimal point and digits
[] = '0'
++
[] = '.'
++
+= digitZero([ : +-.dp])
+= copy([:], .d[0:.nd])

case .dp < .nd:
// decimal point in middle of digits
+= copy([:], .d[0:.dp])
[] = '.'
++
+= copy([:], .d[.dp:.nd])

default:
// zeros fill space between digits and decimal point
+= copy([:], .d[0:.nd])
+= digitZero([ : +.dp-.nd])
}
return string([0:])
}

func digitZero( []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 trim( *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 rightShift( *decimal,  uint) {
:= 0 // write pointer

// Pick up enough leading digits to cover first shift.
var  uint
for ; >> == 0; ++ {
if  >= .nd {
if  == 0 {
// 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.
}

var leftcheats = []leftCheat{
// 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 prefixIsLessThan( []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 leftShift( *decimal,  uint) {
:= leftcheats[].delta
if prefixIsLessThan(.d[0:.nd], leftcheats[].cutoff) {
--
}

:= .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 {
case .nd == 0:
// 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 shouldRoundUp( *decimal,  int) bool {
if  < 0 ||  >= .nd {
return false
}
if .d[] == '5' && +1 == .nd { // exactly halfway - round to even
// 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.
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
}