1 // Copyright 2016 The Cockroach Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 12 // implied. See the License for the specific language governing 13 // permissions and limitations under the License. 14 15 package apd 16 17 // digitsLookupTable is used to map binary digit counts to their corresponding 18 // decimal border values. The map relies on the proof that (without leading zeros) 19 // for any given number of binary digits r, such that the number represented is 20 // between 2^r and 2^(r+1)-1, there are only two possible decimal digit counts 21 // k and k+1 that the binary r digits could be representing. 22 // 23 // Using this proof, for a given digit count, the map will return the lower number 24 // of decimal digits (k) the binary digit count could represent, along with the 25 // value of the border between the two decimal digit counts (10^k). 26 const digitsTableSize = 128 27 28 var digitsLookupTable [digitsTableSize + 1]tableVal 29 30 type tableVal struct { 31 digits int64 32 border BigInt 33 nborder BigInt 34 } 35 36 func init() { 37 curVal := NewBigInt(1) 38 curExp := new(BigInt) 39 for i := 1; i <= digitsTableSize; i++ { 40 if i > 1 { 41 curVal.Lsh(curVal, 1) 42 } 43 44 elem := &digitsLookupTable[i] 45 elem.digits = int64(len(curVal.String())) 46 47 elem.border.SetInt64(10) 48 curExp.SetInt64(elem.digits) 49 elem.border.Exp(&elem.border, curExp, nil) 50 elem.nborder.Neg(&elem.border) 51 } 52 } 53 54 // NumDigits returns the number of decimal digits of d.Coeff. 55 //gcassert:inline 56 func (d *Decimal) NumDigits() int64 { 57 return NumDigits(&d.Coeff) 58 } 59 60 // NumDigits returns the number of decimal digits of b. 61 func NumDigits(b *BigInt) int64 { 62 bl := b.BitLen() 63 if bl == 0 { 64 return 1 65 } 66 67 if bl <= digitsTableSize { 68 val := &digitsLookupTable[bl] 69 // In general, we either have val.digits or val.digits+1 digits and we have 70 // to compare with the border value. But that's not true for all values of 71 // bl: in particular, if bl+1 maps to the same number of digits, then we 72 // know for sure we have val.digits and we can skip the comparison. 73 // This is the case for about 2 out of 3 values. 74 if bl < digitsTableSize && digitsLookupTable[bl+1].digits == val.digits { 75 return val.digits 76 } 77 78 switch b.Sign() { 79 case 1: 80 if b.Cmp(&val.border) < 0 { 81 return val.digits 82 } 83 case -1: 84 if b.Cmp(&val.nborder) > 0 { 85 return val.digits 86 } 87 } 88 return val.digits + 1 89 } 90 91 n := int64(float64(bl) / digitsToBitsRatio) 92 var tmp BigInt 93 e := tableExp10(n, &tmp) 94 var a *BigInt 95 if b.Sign() < 0 { 96 var tmpA BigInt 97 a := &tmpA 98 a.Abs(b) 99 } else { 100 a = b 101 } 102 if a.Cmp(e) >= 0 { 103 n++ 104 } 105 return n 106 } 107 108 // powerTenTableSize is the magnitude of the maximum power of 10 exponent that 109 // is stored in the pow10LookupTable. For instance, if the powerTenTableSize 110 // if 3, then the lookup table will store power of 10 values from 10^0 to 111 // 10^3 inclusive. 112 const powerTenTableSize = 128 113 114 var pow10LookupTable [powerTenTableSize + 1]BigInt 115 116 func init() { 117 for i := int64(0); i <= powerTenTableSize; i++ { 118 setBigWithPow(&pow10LookupTable[i], i) 119 } 120 } 121 122 func setBigWithPow(res *BigInt, pow int64) { 123 var tmp BigInt 124 tmp.SetInt64(pow) 125 res.Exp(bigTen, &tmp, nil) 126 } 127 128 // tableExp10 returns 10^x for x >= 0, looked up from a table when 129 // possible. This returned value must not be mutated. tmp is used as an 130 // intermediate variable and must not be nil. 131 func tableExp10(x int64, tmp *BigInt) *BigInt { 132 if x <= powerTenTableSize { 133 return &pow10LookupTable[x] 134 } 135 setBigWithPow(tmp, x) 136 return tmp 137 } 138