````// Copyright 2015 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.`

`// This file implements nat-to-string conversion functions.`

`package big`

`import (`
`	"errors"`
`	"fmt"`
`	"io"`
`	"math"`
`	"math/bits"`
`	"sync"`
`)`

`const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"`

`// Note: MaxBase = len(digits), but it must remain an untyped rune constant`
`//       for API compatibility.`

`// MaxBase is the largest number base accepted for string conversions.`
`const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)`
`const maxBaseSmall = 10 + ('z' - 'a' + 1)`

`// maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M.`
`// For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word.`
`// In other words, at most n digits in base b fit into a Word.`
`// TODO(gri) replace this with a table, generated at build time.`
`func maxPow(b Word) (p Word, n int) {`
`	p, n = b, 1 // assuming b <= _M`
`	for max := _M / b; p <= max; {`
`		// p == b**n && p <= max`
`		p *= b`
`		n++`
`	}`
`	// p == b**n && p <= _M`
`	return`
`}`

`// pow returns x**n for n > 0, and 1 otherwise.`
`func pow(x Word, n int) (p Word) {`
`	// n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 1`
`	// thus x**n == product of x**(2**i) for all i where bi == 1`
`	// (Russian Peasant Method for exponentiation)`
`	p = 1`
`	for n > 0 {`
`		if n&1 != 0 {`
`			p *= x`
`		}`
`		x *= x`
`		n >>= 1`
`	}`
`	return`
`}`

`// scan errors`
`var (`
`	errNoDigits = errors.New("number has no digits")`
`	errInvalSep = errors.New("'_' must separate successive digits")`
`)`

`// scan scans the number corresponding to the longest possible prefix`
`// from r representing an unsigned number in a given conversion base.`
`// scan returns the corresponding natural number res, the actual base b,`
`// a digit count, and a read or syntax error err, if any.`
`//`
`// For base 0, an underscore character ``_'' may appear between a base`
`// prefix and an adjacent digit, and between successive digits; such`
`// underscores do not change the value of the number, or the returned`
`// digit count. Incorrect placement of underscores is reported as an`
`// error if there are no other errors. If base != 0, underscores are`
`// not recognized and thus terminate scanning like any other character`
`// that is not a valid radix point or digit.`
`//`
`//     number    = mantissa | prefix pmantissa .`
`//     prefix    = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .`
`//     mantissa  = digits "." [ digits ] | digits | "." digits .`
`//     pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .`
`//     digits    = digit { [ "_" ] digit } .`
`//     digit     = "0" ... "9" | "a" ... "z" | "A" ... "Z" .`
`//`
`// Unless fracOk is set, the base argument must be 0 or a value between`
`// 2 and MaxBase. If fracOk is set, the base argument must be one of`
`// 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run-`
`// time panic.`
`//`
`// For base 0, the number prefix determines the actual base: A prefix of`
`// ``0b'' or ``0B'' selects base 2, ``0o'' or ``0O'' selects base 8, and`
`// ``0x'' or ``0X'' selects base 16. If fracOk is false, a ``0'' prefix`
`// (immediately followed by digits) selects base 8 as well. Otherwise,`
`// the selected base is 10 and no prefix is accepted.`
`//`
`// If fracOk is set, a period followed by a fractional part is permitted.`
`// The result value is computed as if there were no period present; and`
`// the count value is used to determine the fractional part.`
`//`
`// For bases <= 36, lower and upper case letters are considered the same:`
`// The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.`
`// For bases > 36, the upper case letters 'A' to 'Z' represent the digit`
`// values 36 to 61.`
`//`
`// A result digit count > 0 corresponds to the number of (non-prefix) digits`
`// parsed. A digit count <= 0 indicates the presence of a period (if fracOk`
`// is set, only), and -count is the number of fractional digits found.`
`// In this case, the actual value of the scanned number is res * b**count.`
`//`
`func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) {`
`	// reject invalid bases`
`	baseOk := base == 0 ||`
`		!fracOk && 2 <= base && base <= MaxBase ||`
`		fracOk && (base == 2 || base == 8 || base == 10 || base == 16)`
`	if !baseOk {`
`		panic(fmt.Sprintf("invalid number base %d", base))`
`	}`

`	// prev encodes the previously seen char: it is one`
`	// of '_', '0' (a digit), or '.' (anything else). A`
`	// valid separator '_' may only occur after a digit`
`	// and if base == 0.`
`	prev := '.'`
`	invalSep := false`

`	// one char look-ahead`
`	ch, err := r.ReadByte()`

`	// determine actual base`
`	b, prefix := base, 0`
`	if base == 0 {`
`		// actual base is 10 unless there's a base prefix`
`		b = 10`
`		if err == nil && ch == '0' {`
`			prev = '0'`
`			count = 1`
`			ch, err = r.ReadByte()`
`			if err == nil {`
`				// possibly one of 0b, 0B, 0o, 0O, 0x, 0X`
`				switch ch {`
`				case 'b', 'B':`
`					b, prefix = 2, 'b'`
`				case 'o', 'O':`
`					b, prefix = 8, 'o'`
`				case 'x', 'X':`
`					b, prefix = 16, 'x'`
`				default:`
`					if !fracOk {`
`						b, prefix = 8, '0'`
`					}`
`				}`
`				if prefix != 0 {`
`					count = 0 // prefix is not counted`
`					if prefix != '0' {`
`						ch, err = r.ReadByte()`
`					}`
`				}`
`			}`
`		}`
`	}`

`	// convert string`
`	// Algorithm: Collect digits in groups of at most n digits in di`
`	// and then use mulAddWW for every such group to add them to the`
`	// result.`
`	z = z[:0]`
`	b1 := Word(b)`
`	bn, n := maxPow(b1) // at most n digits in base b1 fit into Word`
`	di := Word(0)       // 0 <= di < b1**i < bn`
`	i := 0              // 0 <= i < n`
`	dp := -1            // position of decimal point`
`	for err == nil {`
`		if ch == '.' && fracOk {`
`			fracOk = false`
`			if prev == '_' {`
`				invalSep = true`
`			}`
`			prev = '.'`
`			dp = count`
`		} else if ch == '_' && base == 0 {`
`			if prev != '0' {`
`				invalSep = true`
`			}`
`			prev = '_'`
`		} else {`
`			// convert rune into digit value d1`
`			var d1 Word`
`			switch {`
`			case '0' <= ch && ch <= '9':`
`				d1 = Word(ch - '0')`
`			case 'a' <= ch && ch <= 'z':`
`				d1 = Word(ch - 'a' + 10)`
`			case 'A' <= ch && ch <= 'Z':`
`				if b <= maxBaseSmall {`
`					d1 = Word(ch - 'A' + 10)`
`				} else {`
`					d1 = Word(ch - 'A' + maxBaseSmall)`
`				}`
`			default:`
`				d1 = MaxBase + 1`
`			}`
`			if d1 >= b1 {`
`				r.UnreadByte() // ch does not belong to number anymore`
`				break`
`			}`
`			prev = '0'`
`			count++`

`			// collect d1 in di`
`			di = di*b1 + d1`
`			i++`

`			// if di is "full", add it to the result`
`			if i == n {`
`				z = z.mulAddWW(z, bn, di)`
`				di = 0`
`				i = 0`
`			}`
`		}`

`		ch, err = r.ReadByte()`
`	}`

`	if err == io.EOF {`
`		err = nil`
`	}`

`	// other errors take precedence over invalid separators`
`	if err == nil && (invalSep || prev == '_') {`
`		err = errInvalSep`
`	}`

`	if count == 0 {`
`		// no digits found`
`		if prefix == '0' {`
`			// there was only the octal prefix 0 (possibly followed by separators and digits > 7);`
`			// interpret as decimal 0`
`			return z[:0], 10, 1, err`
`		}`
`		err = errNoDigits // fall through; result will be 0`
`	}`

`	// add remaining digits to result`
`	if i > 0 {`
`		z = z.mulAddWW(z, pow(b1, i), di)`
`	}`
`	res = z.norm()`

`	// adjust count for fraction, if any`
`	if dp >= 0 {`
`		// 0 <= dp <= count`
`		count = dp - count`
`	}`

`	return`
`}`

`// utoa converts x to an ASCII representation in the given base;`
`// base must be between 2 and MaxBase, inclusive.`
`func (x nat) utoa(base int) []byte {`
`	return x.itoa(false, base)`
`}`

`// itoa is like utoa but it prepends a '-' if neg && x != 0.`
`func (x nat) itoa(neg bool, base int) []byte {`
`	if base < 2 || base > MaxBase {`
`		panic("invalid base")`
`	}`

`	// x == 0`
`	if len(x) == 0 {`
`		return []byte("0")`
`	}`
`	// len(x) > 0`

`	// allocate buffer for conversion`
`	i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most`
`	if neg {`
`		i++`
`	}`
`	s := make([]byte, i)`

`	// convert power of two and non power of two bases separately`
`	if b := Word(base); b == b&-b {`
`		// shift is base b digit size in bits`
`		shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2`
`		mask := Word(1<<shift - 1)`
`		w := x         // current word`
`		nbits := uint(_W) // number of unprocessed bits in w`

`		// convert less-significant words (include leading zeros)`
`		for k := 1; k < len(x); k++ {`
`			// convert full digits`
`			for nbits >= shift {`
`				i--`
`				s[i] = digits[w&mask]`
`				w >>= shift`
`				nbits -= shift`
`			}`

`			// convert any partial leading digit and advance to next word`
`			if nbits == 0 {`
`				// no partial digit remaining, just advance`
`				w = x[k]`
`				nbits = _W`
`			} else {`
`				// partial digit in current word w (== x[k-1]) and next word x[k]`
`				w |= x[k] << nbits`
`				i--`
`				s[i] = digits[w&mask]`

`				// advance`
`				w = x[k] >> (shift - nbits)`
`				nbits = _W - (shift - nbits)`
`			}`
`		}`

`		// convert digits of most-significant word w (omit leading zeros)`
`		for w != 0 {`
`			i--`
`			s[i] = digits[w&mask]`
`			w >>= shift`
`		}`

`	} else {`
`		bb, ndigits := maxPow(b)`

`		// construct table of successive squares of bb*leafSize to use in subdivisions`
`		// result (table != nil) <=> (len(x) > leafSize > 0)`
`		table := divisors(len(x), b, ndigits, bb)`

`		// preserve x, create local copy for use by convertWords`
`		q := nat(nil).set(x)`

`		// convert q to string s in base b`
`		q.convertWords(s, b, ndigits, bb, table)`

`		// strip leading zeros`
`		// (x != 0; thus s must contain at least one non-zero digit`
`		// and the loop will terminate)`
`		i = 0`
`		for s[i] == '0' {`
`			i++`
`		}`
`	}`

`	if neg {`
`		i--`
`		s[i] = '-'`
`	}`

`	return s[i:]`
`}`

`// Convert words of q to base b digits in s. If q is large, it is recursively "split in half"`
`// by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using`
`// repeated nat/Word division.`
`//`
`// The iterative method processes n Words by n divW() calls, each of which visits every Word in the`
`// incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s.`
`// Recursive conversion divides q by its approximate square root, yielding two parts, each half`
`// the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s`
`// plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and`
`// is made better by splitting the subblocks recursively. Best is to split blocks until one more`
`// split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the`
`// iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the`
`// range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and`
`// ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for`
`// specific hardware.`
`//`
`func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor) {`
`	// split larger blocks recursively`
`	if table != nil {`
`		// len(q) > leafSize > 0`
`		var r nat`
`		index := len(table) - 1`
`		for len(q) > leafSize {`
`			// find divisor close to sqrt(q) if possible, but in any case < q`
`			maxLength := q.bitLen()     // ~= log2 q, or at of least largest possible q of this bit length`
`			minLength := maxLength >> 1 // ~= log2 sqrt(q)`
`			for index > 0 && table[index-1].nbits > minLength {`
`				index-- // desired`
`			}`
`			if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 {`
`				index--`
`				if index < 0 {`
`					panic("internal inconsistency")`
`				}`
`			}`

`			// split q into the two digit number (q'*bbb + r) to form independent subblocks`
`			q, r = q.div(r, q, table[index].bbb)`

`			// convert subblocks and collect results in s[:h] and s[h:]`
`			h := len(s) - table[index].ndigits`
`			r.convertWords(s[h:], b, ndigits, bb, table[0:index])`
`			s = s[:h] // == q.convertWords(s, b, ndigits, bb, table[0:index+1])`
`		}`
`	}`

`	// having split any large blocks now process the remaining (small) block iteratively`
`	i := len(s)`
`	var r Word`
`	if b == 10 {`
`		// hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants)`
`		for len(q) > 0 {`
`			// extract least significant, base bb "digit"`
`			q, r = q.divW(q, bb)`
`			for j := 0; j < ndigits && i > 0; j++ {`
`				i--`
`				// avoid % computation since r%10 == r - int(r/10)*10;`
`				// this appears to be faster for BenchmarkString10000Base10`
`				// and smaller strings (but a bit slower for larger ones)`
`				t := r / 10`
`				s[i] = '0' + byte(r-t*10)`
`				r = t`
`			}`
`		}`
`	} else {`
`		for len(q) > 0 {`
`			// extract least significant, base bb "digit"`
`			q, r = q.divW(q, bb)`
`			for j := 0; j < ndigits && i > 0; j++ {`
`				i--`
`				s[i] = digits[r%b]`
`				r /= b`
`			}`
`		}`
`	}`

`	// prepend high-order zeros`
`	for i > 0 { // while need more leading zeros`
`		i--`
`		s[i] = '0'`
`	}`
`}`

`// Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion)`
`// Benchmark and configure leafSize using: go test -bench="Leaf"`
`//   8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines)`
`//   8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU`
`var leafSize int = 8 // number of Word-size binary values treat as a monolithic block`

`type divisor struct {`
`	bbb     nat // divisor`
`	nbits   int // bit length of divisor (discounting leading zeros) ~= log2(bbb)`
`	ndigits int // digit length of divisor in terms of output base digits`
`}`

`var cacheBase10 struct {`
`	sync.Mutex`
`	table divisor // cached divisors for base 10`
`}`

`// expWW computes x**y`
`func (z nat) expWW(x, y Word) nat {`
`	return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil)`
`}`

`// construct table of powers of bb*leafSize to use in subdivisions`
`func divisors(m int, b Word, ndigits int, bb Word) []divisor {`
`	// only compute table when recursive conversion is enabled and x is large`
`	if leafSize == 0 || m <= leafSize {`
`		return nil`
`	}`

`	// determine k where (bb**leafSize)**(2**k) >= sqrt(x)`
`	k := 1`
`	for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {`
`		k++`
`	}`

`	// reuse and extend existing table of divisors or create new table as appropriate`
`	var table []divisor // for b == 10, table overlaps with cacheBase10.table`
`	if b == 10 {`
`		cacheBase10.Lock()`
`		table = cacheBase10.table[0:k] // reuse old table for this conversion`
`	} else {`
`		table = make([]divisor, k) // create new table for this conversion`
`	}`

`	// extend table`
`	if table[k-1].ndigits == 0 {`
`		// add new entries as needed`
`		var larger nat`
`		for i := 0; i < k; i++ {`
`			if table[i].ndigits == 0 {`
`				if i == 0 {`
`					table.bbb = nat(nil).expWW(bb, Word(leafSize))`
`					table.ndigits = ndigits * leafSize`
`				} else {`
`					table[i].bbb = nat(nil).sqr(table[i-1].bbb)`
`					table[i].ndigits = 2 * table[i-1].ndigits`
`				}`

`				// optimization: exploit aggregated extra bits in macro blocks`
`				larger = nat(nil).set(table[i].bbb)`
`				for mulAddVWW(larger, larger, b, 0) == 0 {`
`					table[i].bbb = table[i].bbb.set(larger)`
`					table[i].ndigits++`
`				}`

`				table[i].nbits = table[i].bbb.bitLen()`
`			}`
`		}`
`	}`

`	if b == 10 {`
`		cacheBase10.Unlock()`
`	}`

`	return table`
`}`
```