const digits … const MaxBase … const maxBaseSmall … // 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) { … } // pow returns x**n for n > 0, and 1 otherwise. func pow(x Word, n int) (p Word) { … } var errNoDigits … var errInvalSep … // 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) { … } // 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 { … } // itoa is like utoa but it prepends a '-' if neg && x != 0. func (x nat) itoa(neg bool, base int) []byte { … } // 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) { … } var leafSize … type divisor … var cacheBase10 … // expWW computes x**y func (z nat) expWW(x, y Word) nat { … } // construct table of powers of bb*leafSize to use in subdivisions. func divisors(m int, b Word, ndigits int, bb Word) []divisor { … }
Codebase Browser
go