Source file src/math/big/natconv.go
1 // Copyright 2015 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 // This file implements nat-to-string conversion functions. 6 7 package big 8 9 import ( 10 "errors" 11 "fmt" 12 "io" 13 "math" 14 "math/bits" 15 "sync" 16 ) 17 18 const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 19 20 // Note: MaxBase = len(digits), but it must remain an untyped rune constant 21 // for API compatibility. 22 23 // MaxBase is the largest number base accepted for string conversions. 24 const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1) 25 const maxBaseSmall = 10 + ('z' - 'a' + 1) 26 27 // maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M. 28 // For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word. 29 // In other words, at most n digits in base b fit into a Word. 30 // TODO(gri) replace this with a table, generated at build time. 31 func maxPow(b Word) (p Word, n int) { 32 p, n = b, 1 // assuming b <= _M 33 for max := _M / b; p <= max; { 34 // p == b**n && p <= max 35 p *= b 36 n++ 37 } 38 // p == b**n && p <= _M 39 return 40 } 41 42 // pow returns x**n for n > 0, and 1 otherwise. 43 func pow(x Word, n int) (p Word) { 44 // n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 1 45 // thus x**n == product of x**(2**i) for all i where bi == 1 46 // (Russian Peasant Method for exponentiation) 47 p = 1 48 for n > 0 { 49 if n&1 != 0 { 50 p *= x 51 } 52 x *= x 53 n >>= 1 54 } 55 return 56 } 57 58 // scan errors 59 var ( 60 errNoDigits = errors.New("number has no digits") 61 errInvalSep = errors.New("'_' must separate successive digits") 62 ) 63 64 // scan scans the number corresponding to the longest possible prefix 65 // from r representing an unsigned number in a given conversion base. 66 // scan returns the corresponding natural number res, the actual base b, 67 // a digit count, and a read or syntax error err, if any. 68 // 69 // For base 0, an underscore character “_” may appear between a base 70 // prefix and an adjacent digit, and between successive digits; such 71 // underscores do not change the value of the number, or the returned 72 // digit count. Incorrect placement of underscores is reported as an 73 // error if there are no other errors. If base != 0, underscores are 74 // not recognized and thus terminate scanning like any other character 75 // that is not a valid radix point or digit. 76 // 77 // number = mantissa | prefix pmantissa . 78 // prefix = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] . 79 // mantissa = digits "." [ digits ] | digits | "." digits . 80 // pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits . 81 // digits = digit { [ "_" ] digit } . 82 // digit = "0" ... "9" | "a" ... "z" | "A" ... "Z" . 83 // 84 // Unless fracOk is set, the base argument must be 0 or a value between 85 // 2 and MaxBase. If fracOk is set, the base argument must be one of 86 // 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run- 87 // time panic. 88 // 89 // For base 0, the number prefix determines the actual base: A prefix of 90 // “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and 91 // “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix 92 // (immediately followed by digits) selects base 8 as well. Otherwise, 93 // the selected base is 10 and no prefix is accepted. 94 // 95 // If fracOk is set, a period followed by a fractional part is permitted. 96 // The result value is computed as if there were no period present; and 97 // the count value is used to determine the fractional part. 98 // 99 // For bases <= 36, lower and upper case letters are considered the same: 100 // The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35. 101 // For bases > 36, the upper case letters 'A' to 'Z' represent the digit 102 // values 36 to 61. 103 // 104 // A result digit count > 0 corresponds to the number of (non-prefix) digits 105 // parsed. A digit count <= 0 indicates the presence of a period (if fracOk 106 // is set, only), and -count is the number of fractional digits found. 107 // In this case, the actual value of the scanned number is res * b**count. 108 func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) { 109 // reject invalid bases 110 baseOk := base == 0 || 111 !fracOk && 2 <= base && base <= MaxBase || 112 fracOk && (base == 2 || base == 8 || base == 10 || base == 16) 113 if !baseOk { 114 panic(fmt.Sprintf("invalid number base %d", base)) 115 } 116 117 // prev encodes the previously seen char: it is one 118 // of '_', '0' (a digit), or '.' (anything else). A 119 // valid separator '_' may only occur after a digit 120 // and if base == 0. 121 prev := '.' 122 invalSep := false 123 124 // one char look-ahead 125 ch, err := r.ReadByte() 126 127 // determine actual base 128 b, prefix := base, 0 129 if base == 0 { 130 // actual base is 10 unless there's a base prefix 131 b = 10 132 if err == nil && ch == '0' { 133 prev = '0' 134 count = 1 135 ch, err = r.ReadByte() 136 if err == nil { 137 // possibly one of 0b, 0B, 0o, 0O, 0x, 0X 138 switch ch { 139 case 'b', 'B': 140 b, prefix = 2, 'b' 141 case 'o', 'O': 142 b, prefix = 8, 'o' 143 case 'x', 'X': 144 b, prefix = 16, 'x' 145 default: 146 if !fracOk { 147 b, prefix = 8, '0' 148 } 149 } 150 if prefix != 0 { 151 count = 0 // prefix is not counted 152 if prefix != '0' { 153 ch, err = r.ReadByte() 154 } 155 } 156 } 157 } 158 } 159 160 // convert string 161 // Algorithm: Collect digits in groups of at most n digits in di 162 // and then use mulAddWW for every such group to add them to the 163 // result. 164 z = z[:0] 165 b1 := Word(b) 166 bn, n := maxPow(b1) // at most n digits in base b1 fit into Word 167 di := Word(0) // 0 <= di < b1**i < bn 168 i := 0 // 0 <= i < n 169 dp := -1 // position of decimal point 170 for err == nil { 171 if ch == '.' && fracOk { 172 fracOk = false 173 if prev == '_' { 174 invalSep = true 175 } 176 prev = '.' 177 dp = count 178 } else if ch == '_' && base == 0 { 179 if prev != '0' { 180 invalSep = true 181 } 182 prev = '_' 183 } else { 184 // convert rune into digit value d1 185 var d1 Word 186 switch { 187 case '0' <= ch && ch <= '9': 188 d1 = Word(ch - '0') 189 case 'a' <= ch && ch <= 'z': 190 d1 = Word(ch - 'a' + 10) 191 case 'A' <= ch && ch <= 'Z': 192 if b <= maxBaseSmall { 193 d1 = Word(ch - 'A' + 10) 194 } else { 195 d1 = Word(ch - 'A' + maxBaseSmall) 196 } 197 default: 198 d1 = MaxBase + 1 199 } 200 if d1 >= b1 { 201 r.UnreadByte() // ch does not belong to number anymore 202 break 203 } 204 prev = '0' 205 count++ 206 207 // collect d1 in di 208 di = di*b1 + d1 209 i++ 210 211 // if di is "full", add it to the result 212 if i == n { 213 z = z.mulAddWW(z, bn, di) 214 di = 0 215 i = 0 216 } 217 } 218 219 ch, err = r.ReadByte() 220 } 221 222 if err == io.EOF { 223 err = nil 224 } 225 226 // other errors take precedence over invalid separators 227 if err == nil && (invalSep || prev == '_') { 228 err = errInvalSep 229 } 230 231 if count == 0 { 232 // no digits found 233 if prefix == '0' { 234 // there was only the octal prefix 0 (possibly followed by separators and digits > 7); 235 // interpret as decimal 0 236 return z[:0], 10, 1, err 237 } 238 err = errNoDigits // fall through; result will be 0 239 } 240 241 // add remaining digits to result 242 if i > 0 { 243 z = z.mulAddWW(z, pow(b1, i), di) 244 } 245 res = z.norm() 246 247 // adjust count for fraction, if any 248 if dp >= 0 { 249 // 0 <= dp <= count 250 count = dp - count 251 } 252 253 return 254 } 255 256 // utoa converts x to an ASCII representation in the given base; 257 // base must be between 2 and MaxBase, inclusive. 258 func (x nat) utoa(base int) []byte { 259 return x.itoa(false, base) 260 } 261 262 // itoa is like utoa but it prepends a '-' if neg && x != 0. 263 func (x nat) itoa(neg bool, base int) []byte { 264 if base < 2 || base > MaxBase { 265 panic("invalid base") 266 } 267 268 // x == 0 269 if len(x) == 0 { 270 return []byte("0") 271 } 272 // len(x) > 0 273 274 // allocate buffer for conversion 275 i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most 276 if neg { 277 i++ 278 } 279 s := make([]byte, i) 280 281 // convert power of two and non power of two bases separately 282 if b := Word(base); b == b&-b { 283 // shift is base b digit size in bits 284 shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2 285 mask := Word(1<<shift - 1) 286 w := x[0] // current word 287 nbits := uint(_W) // number of unprocessed bits in w 288 289 // convert less-significant words (include leading zeros) 290 for k := 1; k < len(x); k++ { 291 // convert full digits 292 for nbits >= shift { 293 i-- 294 s[i] = digits[w&mask] 295 w >>= shift 296 nbits -= shift 297 } 298 299 // convert any partial leading digit and advance to next word 300 if nbits == 0 { 301 // no partial digit remaining, just advance 302 w = x[k] 303 nbits = _W 304 } else { 305 // partial digit in current word w (== x[k-1]) and next word x[k] 306 w |= x[k] << nbits 307 i-- 308 s[i] = digits[w&mask] 309 310 // advance 311 w = x[k] >> (shift - nbits) 312 nbits = _W - (shift - nbits) 313 } 314 } 315 316 // convert digits of most-significant word w (omit leading zeros) 317 for w != 0 { 318 i-- 319 s[i] = digits[w&mask] 320 w >>= shift 321 } 322 323 } else { 324 bb, ndigits := maxPow(b) 325 326 // construct table of successive squares of bb*leafSize to use in subdivisions 327 // result (table != nil) <=> (len(x) > leafSize > 0) 328 table := divisors(len(x), b, ndigits, bb) 329 330 // preserve x, create local copy for use by convertWords 331 q := nat(nil).set(x) 332 333 // convert q to string s in base b 334 q.convertWords(s, b, ndigits, bb, table) 335 336 // strip leading zeros 337 // (x != 0; thus s must contain at least one non-zero digit 338 // and the loop will terminate) 339 i = 0 340 for s[i] == '0' { 341 i++ 342 } 343 } 344 345 if neg { 346 i-- 347 s[i] = '-' 348 } 349 350 return s[i:] 351 } 352 353 // Convert words of q to base b digits in s. If q is large, it is recursively "split in half" 354 // by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using 355 // repeated nat/Word division. 356 // 357 // The iterative method processes n Words by n divW() calls, each of which visits every Word in the 358 // incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s. 359 // Recursive conversion divides q by its approximate square root, yielding two parts, each half 360 // the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s 361 // plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and 362 // is made better by splitting the subblocks recursively. Best is to split blocks until one more 363 // split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the 364 // iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the 365 // range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and 366 // ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for 367 // specific hardware. 368 func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor) { 369 // split larger blocks recursively 370 if table != nil { 371 // len(q) > leafSize > 0 372 var r nat 373 index := len(table) - 1 374 for len(q) > leafSize { 375 // find divisor close to sqrt(q) if possible, but in any case < q 376 maxLength := q.bitLen() // ~= log2 q, or at of least largest possible q of this bit length 377 minLength := maxLength >> 1 // ~= log2 sqrt(q) 378 for index > 0 && table[index-1].nbits > minLength { 379 index-- // desired 380 } 381 if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 { 382 index-- 383 if index < 0 { 384 panic("internal inconsistency") 385 } 386 } 387 388 // split q into the two digit number (q'*bbb + r) to form independent subblocks 389 q, r = q.div(r, q, table[index].bbb) 390 391 // convert subblocks and collect results in s[:h] and s[h:] 392 h := len(s) - table[index].ndigits 393 r.convertWords(s[h:], b, ndigits, bb, table[0:index]) 394 s = s[:h] // == q.convertWords(s, b, ndigits, bb, table[0:index+1]) 395 } 396 } 397 398 // having split any large blocks now process the remaining (small) block iteratively 399 i := len(s) 400 var r Word 401 if b == 10 { 402 // hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants) 403 for len(q) > 0 { 404 // extract least significant, base bb "digit" 405 q, r = q.divW(q, bb) 406 for j := 0; j < ndigits && i > 0; j++ { 407 i-- 408 // avoid % computation since r%10 == r - int(r/10)*10; 409 // this appears to be faster for BenchmarkString10000Base10 410 // and smaller strings (but a bit slower for larger ones) 411 t := r / 10 412 s[i] = '0' + byte(r-t*10) 413 r = t 414 } 415 } 416 } else { 417 for len(q) > 0 { 418 // extract least significant, base bb "digit" 419 q, r = q.divW(q, bb) 420 for j := 0; j < ndigits && i > 0; j++ { 421 i-- 422 s[i] = digits[r%b] 423 r /= b 424 } 425 } 426 } 427 428 // prepend high-order zeros 429 for i > 0 { // while need more leading zeros 430 i-- 431 s[i] = '0' 432 } 433 } 434 435 // Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion) 436 // Benchmark and configure leafSize using: go test -bench="Leaf" 437 // 438 // 8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines) 439 // 8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU 440 var leafSize int = 8 // number of Word-size binary values treat as a monolithic block 441 442 type divisor struct { 443 bbb nat // divisor 444 nbits int // bit length of divisor (discounting leading zeros) ~= log2(bbb) 445 ndigits int // digit length of divisor in terms of output base digits 446 } 447 448 var cacheBase10 struct { 449 sync.Mutex 450 table [64]divisor // cached divisors for base 10 451 } 452 453 // expWW computes x**y 454 func (z nat) expWW(x, y Word) nat { 455 return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil, false) 456 } 457 458 // construct table of powers of bb*leafSize to use in subdivisions. 459 func divisors(m int, b Word, ndigits int, bb Word) []divisor { 460 // only compute table when recursive conversion is enabled and x is large 461 if leafSize == 0 || m <= leafSize { 462 return nil 463 } 464 465 // determine k where (bb**leafSize)**(2**k) >= sqrt(x) 466 k := 1 467 for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 { 468 k++ 469 } 470 471 // reuse and extend existing table of divisors or create new table as appropriate 472 var table []divisor // for b == 10, table overlaps with cacheBase10.table 473 if b == 10 { 474 cacheBase10.Lock() 475 table = cacheBase10.table[0:k] // reuse old table for this conversion 476 } else { 477 table = make([]divisor, k) // create new table for this conversion 478 } 479 480 // extend table 481 if table[k-1].ndigits == 0 { 482 // add new entries as needed 483 var larger nat 484 for i := 0; i < k; i++ { 485 if table[i].ndigits == 0 { 486 if i == 0 { 487 table[0].bbb = nat(nil).expWW(bb, Word(leafSize)) 488 table[0].ndigits = ndigits * leafSize 489 } else { 490 table[i].bbb = nat(nil).sqr(table[i-1].bbb) 491 table[i].ndigits = 2 * table[i-1].ndigits 492 } 493 494 // optimization: exploit aggregated extra bits in macro blocks 495 larger = nat(nil).set(table[i].bbb) 496 for mulAddVWW(larger, larger, b, 0) == 0 { 497 table[i].bbb = table[i].bbb.set(larger) 498 table[i].ndigits++ 499 } 500 501 table[i].nbits = table[i].bbb.bitLen() 502 } 503 } 504 } 505 506 if b == 10 { 507 cacheBase10.Unlock() 508 } 509 510 return table 511 } 512