aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xsrc/pkg/big/nat.go129
-rwxr-xr-xsrc/pkg/big/nat_test.go213
2 files changed, 324 insertions, 18 deletions
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index fa09d65315..ea1903b166 100755
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -615,6 +615,7 @@ func (x nat) bitLen() int {
// MaxBase is the largest number base accepted for string conversions.
const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1
+
func hexValue(ch int) Word {
d := MaxBase + 1 // illegal base
switch {
@@ -733,46 +734,137 @@ const (
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[0:10])
+}
+
+
// 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.
func (x nat) string(charset string) string {
- base := len(charset)
+ b := Word(len(charset))
// special cases
switch {
- case base < 2:
+ case b < 2 || b > 256:
panic("illegal base")
case len(x) == 0:
return string(charset[0])
}
// allocate buffer for conversion
- i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
+ i := x.bitLen()/log2(b) + 1 // +1: round up
s := make([]byte, i)
- // don't destroy x
+ // special case: power of two bases can avoid divisions completely
+ if b == b&-b {
+ // shift is base-b digit size in bits
+ shift := uint(trailingZeroBits(b)) // shift > 0 because b >= 2
+ m := len(x)
+ mask := Word(1)<<shift - 1
+ w := x[0]
+ nbits := uint(_W) // number of unprocessed bits in w
+
+ // convert less-significant words
+ for k := 0; k < m-1; 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+1]
+ nbits = _W
+ } else {
+ // partial digit in current (k) and next (k+1) word
+ w |= x[k+1] << nbits
+ i--
+ s[i] = charset[w&mask]
+
+ // advance
+ w = x[k+1] >> (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
+ }
+
+ return string(s[i:])
+ }
+
+ // general case: extract groups of digits by multiprecision division
+
+ // maximize ndigits where b**ndigits < 2^_W; bb (big base) is b**ndigits
+ bb := Word(1)
+ ndigits := 0
+ for max := Word(_M / b); bb <= max; bb *= b {
+ ndigits++
+ }
+
+ // preserve x, create local copy for use in repeated divisions
q := nat(nil).set(x)
+ var r Word
// convert
- for len(q) > 0 {
- i--
- var r Word
- q, r = q.divW(q, Word(base))
- s[i] = charset[r]
+ if b == 10 { // hard-coding for 10 here speeds this up by 1.25x
+ for len(q) > 0 {
+ // extract least significant, base bb "digit"
+ q, r = q.divW(q, bb) // N.B. >82% of time is here. Optimize divW
+ if len(q) == 0 {
+ // skip leading zeros in most-significant group of digits
+ for j := 0; j < ndigits && r != 0; j++ {
+ i--
+ s[i] = charset[r%10]
+ r /= 10
+ }
+ } else {
+ for j := 0; j < ndigits; j++ {
+ i--
+ s[i] = charset[r%10]
+ r /= 10
+ }
+ }
+ }
+ } else {
+ for len(q) > 0 {
+ // extract least significant group of digits
+ q, r = q.divW(q, bb) // N.B. >82% of time is here. Optimize divW
+ if len(q) == 0 {
+ // skip leading zeros in most-significant group of digits
+ for j := 0; j < ndigits && r != 0; j++ {
+ i--
+ s[i] = charset[r%b]
+ r /= b
+ }
+ } else {
+ for j := 0; j < ndigits; j++ {
+ i--
+ s[i] = charset[r%b]
+ r /= b
+ }
+ }
+ }
}
return string(s[i:])
}
-// decimalString returns a decimal representation of x.
-// It calls x.string with the charset "0123456789".
-func (x nat) decimalString() string {
- return x.string(lowercaseDigits[0:10])
-}
-
-
const deBruijn32 = 0x077CB531
var deBruijn32Lookup = []byte{
@@ -789,6 +881,7 @@ var deBruijn64Lookup = []byte{
54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
}
+
// trailingZeroBits returns the number of consecutive zero bits on the right
// side of the given Word.
// See Knuth, volume 4, section 7.3.1
@@ -960,7 +1053,9 @@ func (z nat) xor(x, y nat) nat {
// greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
-func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 || x1 == y1 && x2 > y2 }
+func greaterThan(x1, x2, y1, y2 Word) bool {
+ return x1 > y1 || x1 == y1 && x2 > y2
+}
// modW returns x % d.
diff --git a/src/pkg/big/nat_test.go b/src/pkg/big/nat_test.go
index 50ea469be0..fd93592ddc 100755
--- a/src/pkg/big/nat_test.go
+++ b/src/pkg/big/nat_test.go
@@ -5,6 +5,7 @@
package big
import (
+ "fmt"
"os"
"strings"
"testing"
@@ -171,6 +172,36 @@ func BenchmarkMul(b *testing.B) {
}
+func toString(x nat, charset string) string {
+ base := len(charset)
+
+ // special cases
+ switch {
+ case base < 2:
+ panic("illegal base")
+ case len(x) == 0:
+ return string(charset[0])
+ }
+
+ // allocate buffer for conversion
+ i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
+ s := make([]byte, i)
+
+ // don't destroy x
+ q := nat(nil).set(x)
+
+ // convert
+ for len(q) > 0 {
+ i--
+ var r Word
+ q, r = q.divW(q, Word(base))
+ s[i] = charset[r]
+ }
+
+ return string(s[i:])
+}
+
+
var strTests = []struct {
x nat // nat value to be converted
c string // conversion charset
@@ -360,6 +391,187 @@ func BenchmarkScanPi(b *testing.B) {
}
+const (
+ // 314**271
+ // base 2: 2249 digits
+ // base 8: 751 digits
+ // base 10: 678 digits
+ // base 16: 563 digits
+ shortBase = 314
+ shortExponent = 271
+
+ // 3141**2178
+ // base 2: 31577 digits
+ // base 8: 10527 digits
+ // base 10: 9507 digits
+ // base 16: 7895 digits
+ mediumBase = 3141
+ mediumExponent = 2718
+
+ // 3141**2178
+ // base 2: 406078 digits
+ // base 8: 135360 digits
+ // base 10: 122243 digits
+ // base 16: 101521 digits
+ longBase = 31415
+ longExponent = 27182
+)
+
+
+func BenchmarkScanShort2(b *testing.B) {
+ ScanHelper(b, 2, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanShort8(b *testing.B) {
+ ScanHelper(b, 8, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanSort10(b *testing.B) {
+ ScanHelper(b, 10, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanShort16(b *testing.B) {
+ ScanHelper(b, 16, shortBase, shortExponent)
+}
+
+
+func BenchmarkScanMedium2(b *testing.B) {
+ ScanHelper(b, 2, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium8(b *testing.B) {
+ ScanHelper(b, 8, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium10(b *testing.B) {
+ ScanHelper(b, 10, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanMedium16(b *testing.B) {
+ ScanHelper(b, 16, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkScanLong2(b *testing.B) {
+ ScanHelper(b, 2, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong8(b *testing.B) {
+ ScanHelper(b, 8, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong10(b *testing.B) {
+ ScanHelper(b, 10, longBase, longExponent)
+}
+
+
+func BenchmarkScanLong16(b *testing.B) {
+ ScanHelper(b, 16, longBase, longExponent)
+}
+
+
+func ScanHelper(b *testing.B, base int, xv, yv Word) {
+ b.StopTimer()
+ var x, y, z nat
+ x = x.setWord(xv)
+ y = y.setWord(yv)
+ z = z.expNN(x, y, nil)
+
+ var s string
+ s = z.string(lowercaseDigits[0:base])
+ if t := toString(z, lowercaseDigits[0:base]); t != s {
+ panic(fmt.Sprintf("scanning: got %s; want %s", s, t))
+ }
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ x.scan(strings.NewReader(s), base)
+ }
+}
+
+
+func BenchmarkStringShort2(b *testing.B) {
+ StringHelper(b, 2, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort8(b *testing.B) {
+ StringHelper(b, 8, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort10(b *testing.B) {
+ StringHelper(b, 10, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringShort16(b *testing.B) {
+ StringHelper(b, 16, shortBase, shortExponent)
+}
+
+
+func BenchmarkStringMedium2(b *testing.B) {
+ StringHelper(b, 2, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium8(b *testing.B) {
+ StringHelper(b, 8, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium10(b *testing.B) {
+ StringHelper(b, 10, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringMedium16(b *testing.B) {
+ StringHelper(b, 16, mediumBase, mediumExponent)
+}
+
+
+func BenchmarkStringLong2(b *testing.B) {
+ StringHelper(b, 2, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong8(b *testing.B) {
+ StringHelper(b, 8, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong10(b *testing.B) {
+ StringHelper(b, 10, longBase, longExponent)
+}
+
+
+func BenchmarkStringLong16(b *testing.B) {
+ StringHelper(b, 16, longBase, longExponent)
+}
+
+
+func StringHelper(b *testing.B, base int, xv, yv Word) {
+ b.StopTimer()
+ var x, y, z nat
+ x = x.setWord(xv)
+ y = y.setWord(yv)
+ z = z.expNN(x, y, nil)
+ b.StartTimer()
+
+ for i := 0; i < b.N; i++ {
+ z.string(lowercaseDigits[0:base])
+ }
+}
+
+
func TestLeadingZeros(t *testing.T) {
var x Word = _B >> 1
for i := 0; i <= _W; i++ {
@@ -479,7 +691,6 @@ func TestTrailingZeroBits(t *testing.T) {
}
}
-
var expNNTests = []struct {
x, y, m string
out string
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion