src/math/big/natconv.go - go - Git at Google

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

 // MaxBase is the largest number base accepted for string conversions.
 const MaxBase = 'z' - 'a' + 10 + 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 scans the number corresponding to the longest possible prefix
 // from r representing an unsigned number in a given conversion base.
 // It returns the corresponding natural number res, the actual base b,
 // a digit count, and a read or syntax error err, if any.
 //
 //	number   = [ prefix ] mantissa .
 //	prefix   = "0" [ "x" | "X" | "b" | "B" ] .
 //      mantissa = 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, 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
 // ``0x'' or ``0X'' selects base 16; if fracOk is not set, the ``0'' prefix
 // selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise
 // the selected base is 10 and no prefix is accepted.
 //
 // If fracOk is set, an octal prefix is ignored (a leading ``0'' simply
 // stands for a zero digit), and 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.
 //
 // 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 illegal bases
 	baseOk := base == 0 ||
 		!fracOk && 2 <= base && base <= MaxBase ||
 		fracOk && (base == 2 || base == 10 || base == 16)
 	if !baseOk {
 		panic(fmt.Sprintf("illegal number base %d", base))
 	}

 	// one char look-ahead
 	ch, err := r.ReadByte()
 	if err != nil {
 		return
 	}

 	// determine actual base
 	b = base
 	if base == 0 {
 		// actual base is 10 unless there's a base prefix
 		b = 10
 		if ch == '0' {
 			count = 1
 			switch ch, err = r.ReadByte(); err {
 			case nil:
 				// possibly one of 0x, 0X, 0b, 0B
 				if !fracOk {
 					b = 8
 				}
 				switch ch {
 				case 'x', 'X':
 					b = 16
 				case 'b', 'B':
 					b = 2
 				}
 				switch b {
 				case 16, 2:
 					count = 0 // prefix is not counted
 					if ch, err = r.ReadByte(); err != nil {
 						// io.EOF is also an error in this case
 						return
 					}
 				case 8:
 					count = 0 // prefix is not counted
 				}
 			case io.EOF:
 				// input is "0"
 				res = z[:0]
 				err = nil
 				return
 			default:
 				// read error
 				return
 			}
 		}
 	}

 	// 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 {
 		if fracOk && ch == '.' {
 			fracOk = false
 			dp = count
 			// advance
 			if ch, err = r.ReadByte(); err != nil {
 				if err == io.EOF {
 					err = nil
 					break
 				}
 				return
 			}
 		}

 		// 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':
 			d1 = Word(ch - 'A' + 10)
 		default:
 			d1 = MaxBase + 1
 		}
 		if d1 >= b1 {
 			r.UnreadByte() // ch does not belong to number anymore
 			break
 		}
 		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
 		}

 		// advance
 		if ch, err = r.ReadByte(); err != nil {
 			if err == io.EOF {
 				err = nil
 				break
 			}
 			return
 		}
 	}

 	if count == 0 {
 		// no digits found
 		switch {
 		case base == 0 && b == 8:
 			// there was only the octal prefix 0 (possibly followed by digits > 7);
 			// count as one digit and return base 10, not 8
 			count = 1
 			b = 10
 		case base != 0 || b != 8:
 			// there was neither a mantissa digit nor the octal prefix 0
 			err = errors.New("syntax error scanning number")
 		}
 		return
 	}
 	// count > 0

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

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

 	return
 }

 // Character sets for string conversion.
 const (
 	lowercaseDigits = "0123456789abcdefghijklmnopqrstuvwxyz"
 	uppercaseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 )

 // decimalString returns a decimal representation of x.
 // It calls x.string with the charset "0123456789".
 func (x nat) decimalString() string {
 	return x.string(lowercaseDigits[:10])
 }

 // hexString returns a hexadecimal representation of x.
 // It calls x.string with the charset "0123456789abcdef".
 func (x nat) hexString() string {
 	return x.string(lowercaseDigits[:16])
 }

 // string converts x to a string using digits from a charset; a digit with
 // value d is represented by charset[d]. The conversion base is determined
 // by len(charset), which must be >= 2 and <= 256.
 func (x nat) string(charset string) string {
 	b := Word(len(charset))

 	// special cases
 	switch {
 	case b < 2 || b > 256:
 		panic("invalid character set length")
 	case len(x) == 0:
 		return string(charset[0])
 	}

 	// allocate buffer for conversion
 	i := int(float64(x.bitLen())/math.Log2(float64(b))) + 1 // off by one at most
 	s := make([]byte, i)

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

 		// convert less-significant words
 		for k := 1; k < len(x); k++ {
 			// convert full digits
 			for nbits >= shift {
 				i--
 				s[i] = charset[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 (k-1) and next (k) word
 				w |= x[k] << nbits
 				i--
 				s[i] = charset[w&mask]

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

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

 	} else {
 		bb, ndigits := maxPow(Word(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, charset, 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 zero := charset[0]; s[i] == zero; {
 			i++
 		}
 	}

 	return string(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, charset string, 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:], charset, b, ndigits, bb, table[0:index])
 			s = s[:h] // == q.convertWords(s, charset, 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] = charset[r-t<<3-t-t] // TODO(gri) replace w/ t*10 once compiler produces better code
 				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] = charset[r%b]
 				r /= b
 			}
 		}
 	}

 	// prepend high-order zeroes
 	zero := charset[0]
 	for i > 0 { // while need more leading zeroes
 		i--
 		s[i] = zero
 	}
 }

 // 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 zeroes) ~= log2(bbb)
 	ndigits int // digit length of divisor in terms of output base digits
 }

 var cacheBase10 struct {
 	sync.Mutex
 	table [64]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[0].bbb = nat(nil).expWW(bb, Word(leafSize))
 					table[0].ndigits = ndigits * leafSize
 				} else {
 					table[i].bbb = nat(nil).mul(table[i-1].bbb, 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
 }
	// 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"
	"sync"
	)

	// MaxBase is the largest number base accepted for string conversions.
	const MaxBase = 'z' - 'a' + 10 + 1

	// maxPow returns (bn, n) such that bn 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 xn == 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 scans the number corresponding to the longest possible prefix
	// from r representing an unsigned number in a given conversion base.
	// It returns the corresponding natural number res, the actual base b,
	// a digit count, and a read or syntax error err, if any.
	//
	// number = [ prefix ] mantissa .
	// prefix = "0" [ "x" \| "X" \| "b" \| "B" ] .
	// mantissa = 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, 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
	// ``0x'' or ``0X'' selects base 16; if fracOk is not set, the ``0'' prefix
	// selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise
	// the selected base is 10 and no prefix is accepted.
	//
	// If fracOk is set, an octal prefix is ignored (a leading ``0'' simply
	// stands for a zero digit), and 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.
	//
	// 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 illegal bases
	baseOk := base == 0 \|\|
	!fracOk && 2 <= base && base <= MaxBase \|\|
	fracOk && (base == 2 \|\| base == 10 \|\| base == 16)
	if !baseOk {
	panic(fmt.Sprintf("illegal number base %d", base))
	}

	// one char look-ahead
	ch, err := r.ReadByte()
	if err != nil {
	return
	}

	// determine actual base
	b = base
	if base == 0 {
	// actual base is 10 unless there's a base prefix
	b = 10
	if ch == '0' {
	count = 1
	switch ch, err = r.ReadByte(); err {
	case nil:
	// possibly one of 0x, 0X, 0b, 0B
	if !fracOk {
	b = 8
	}
	switch ch {
	case 'x', 'X':
	b = 16
	case 'b', 'B':
	b = 2
	}
	switch b {
	case 16, 2:
	count = 0 // prefix is not counted
	if ch, err = r.ReadByte(); err != nil {
	// io.EOF is also an error in this case
	return
	}
	case 8:
	count = 0 // prefix is not counted
	}
	case io.EOF:
	// input is "0"
	res = z[:0]
	err = nil
	return
	default:
	// read error
	return
	}
	}
	}

	// 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 {
	if fracOk && ch == '.' {
	fracOk = false
	dp = count
	// advance
	if ch, err = r.ReadByte(); err != nil {
	if err == io.EOF {
	err = nil
	break
	}
	return
	}
	}

	// 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':
	d1 = Word(ch - 'A' + 10)
	default:
	d1 = MaxBase + 1
	}
	if d1 >= b1 {
	r.UnreadByte() // ch does not belong to number anymore
	break
	}
	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
	}

	// advance
	if ch, err = r.ReadByte(); err != nil {
	if err == io.EOF {
	err = nil
	break
	}
	return
	}
	}

	if count == 0 {
	// no digits found
	switch {
	case base == 0 && b == 8:
	// there was only the octal prefix 0 (possibly followed by digits > 7);
	// count as one digit and return base 10, not 8
	count = 1
	b = 10
	case base != 0 \|\| b != 8:
	// there was neither a mantissa digit nor the octal prefix 0
	err = errors.New("syntax error scanning number")
	}
	return
	}
	// count > 0

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

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

	return
	}

	// Character sets for string conversion.
	const (
	lowercaseDigits = "0123456789abcdefghijklmnopqrstuvwxyz"
	uppercaseDigits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	)

	// decimalString returns a decimal representation of x.
	// It calls x.string with the charset "0123456789".
	func (x nat) decimalString() string {
	return x.string(lowercaseDigits[:10])
	}

	// hexString returns a hexadecimal representation of x.
	// It calls x.string with the charset "0123456789abcdef".
	func (x nat) hexString() string {
	return x.string(lowercaseDigits[:16])
	}

	// string converts x to a string using digits from a charset; a digit with
	// value d is represented by charset[d]. The conversion base is determined
	// by len(charset), which must be >= 2 and <= 256.
	func (x nat) string(charset string) string {
	b := Word(len(charset))

	// special cases
	switch {
	case b < 2 \|\| b > 256:
	panic("invalid character set length")
	case len(x) == 0:
	return string(charset[0])
	}

	// allocate buffer for conversion
	i := int(float64(x.bitLen())/math.Log2(float64(b))) + 1 // off by one at most
	s := make([]byte, i)

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

	// convert less-significant words
	for k := 1; k < len(x); k++ {
	// convert full digits
	for nbits >= shift {
	i--
	s[i] = charset[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 (k-1) and next (k) word
	w \|= x[k] << nbits
	i--
	s[i] = charset[w&mask]

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

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

	} else {
	bb, ndigits := maxPow(Word(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, charset, 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 zero := charset[0]; s[i] == zero; {
	i++
	}
	}

	return string(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, charset string, 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:], charset, b, ndigits, bb, table[0:index])
	s = s[:h] // == q.convertWords(s, charset, 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] = charset[r-t<<3-t-t] // TODO(gri) replace w/ t*10 once compiler produces better code
	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] = charset[r%b]
	r /= b
	}
	}
	}

	// prepend high-order zeroes
	zero := charset[0]
	for i > 0 { // while need more leading zeroes
	i--
	s[i] = zero
	}
	}

	// 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 zeroes) ~= log2(bbb)
	ndigits int // digit length of divisor in terms of output base digits
	}

	var cacheBase10 struct {
	sync.Mutex
	table [64]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 (bbleafSize)(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[0].bbb = nat(nil).expWW(bb, Word(leafSize))
	table[0].ndigits = ndigits * leafSize
	} else {
	table[i].bbb = nat(nil).mul(table[i-1].bbb, 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
	}