summaryrefslogtreecommitdiff
path: root/src/pkg/big/nat.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/big/nat.go')
-rwxr-xr-xsrc/pkg/big/nat.go48
1 files changed, 0 insertions, 48 deletions
diff --git a/src/pkg/big/nat.go b/src/pkg/big/nat.go
index 6755832be..be3aff29d 100755
--- a/src/pkg/big/nat.go
+++ b/src/pkg/big/nat.go
@@ -24,7 +24,6 @@ import (
"rand"
)
-
// An unsigned integer x of the form
//
// x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]
@@ -45,14 +44,12 @@ var (
natTen = nat{10}
)
-
func (z nat) clear() {
for i := range z {
z[i] = 0
}
}
-
func (z nat) norm() nat {
i := len(z)
for i > 0 && z[i-1] == 0 {
@@ -61,7 +58,6 @@ func (z nat) norm() nat {
return z[0:i]
}
-
func (z nat) make(n int) nat {
if n <= cap(z) {
return z[0:n] // reuse z
@@ -72,7 +68,6 @@ func (z nat) make(n int) nat {
return make(nat, n, n+e)
}
-
func (z nat) setWord(x Word) nat {
if x == 0 {
return z.make(0)
@@ -82,7 +77,6 @@ func (z nat) setWord(x Word) nat {
return z
}
-
func (z nat) setUint64(x uint64) nat {
// single-digit values
if w := Word(x); uint64(w) == x {
@@ -105,14 +99,12 @@ func (z nat) setUint64(x uint64) nat {
return z
}
-
func (z nat) set(x nat) nat {
z = z.make(len(x))
copy(z, x)
return z
}
-
func (z nat) add(x, y nat) nat {
m := len(x)
n := len(y)
@@ -139,7 +131,6 @@ func (z nat) add(x, y nat) nat {
return z.norm()
}
-
func (z nat) sub(x, y nat) nat {
m := len(x)
n := len(y)
@@ -168,7 +159,6 @@ func (z nat) sub(x, y nat) nat {
return z.norm()
}
-
func (x nat) cmp(y nat) (r int) {
m := len(x)
n := len(y)
@@ -196,7 +186,6 @@ func (x nat) cmp(y nat) (r int) {
return
}
-
func (z nat) mulAddWW(x nat, y, r Word) nat {
m := len(x)
if m == 0 || y == 0 {
@@ -210,7 +199,6 @@ func (z nat) mulAddWW(x nat, y, r Word) nat {
return z.norm()
}
-
// basicMul multiplies x and y and leaves the result in z.
// The (non-normalized) result is placed in z[0 : len(x) + len(y)].
func basicMul(z, x, y nat) {
@@ -222,7 +210,6 @@ func basicMul(z, x, y nat) {
}
}
-
// Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks.
// Factored out for readability - do not use outside karatsuba.
func karatsubaAdd(z, x nat, n int) {
@@ -231,7 +218,6 @@ func karatsubaAdd(z, x nat, n int) {
}
}
-
// Like karatsubaAdd, but does subtract.
func karatsubaSub(z, x nat, n int) {
if c := subVV(z[0:n], z, x); c != 0 {
@@ -239,7 +225,6 @@ func karatsubaSub(z, x nat, n int) {
}
}
-
// Operands that are shorter than karatsubaThreshold are multiplied using
// "grade school" multiplication; for longer operands the Karatsuba algorithm
// is used.
@@ -344,13 +329,11 @@ func karatsuba(z, x, y nat) {
}
}
-
// alias returns true if x and y share the same base array.
func alias(x, y nat) bool {
return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
}
-
// addAt implements z += x*(1<<(_W*i)); z must be long enough.
// (we don't use nat.add because we need z to stay the same
// slice, and we don't need to normalize z after each addition)
@@ -365,7 +348,6 @@ func addAt(z, x nat, i int) {
}
}
-
func max(x, y int) int {
if x > y {
return x
@@ -373,7 +355,6 @@ func max(x, y int) int {
return y
}
-
// karatsubaLen computes an approximation to the maximum k <= n such that
// k = p<<i for a number p <= karatsubaThreshold and an i >= 0. Thus, the
// result is the largest number that can be divided repeatedly by 2 before
@@ -387,7 +368,6 @@ func karatsubaLen(n int) int {
return n << i
}
-
func (z nat) mul(x, y nat) nat {
m := len(x)
n := len(y)
@@ -455,7 +435,6 @@ func (z nat) mul(x, y nat) nat {
return z.norm()
}
-
// mulRange computes the product of all the unsigned integers in the
// range [a, b] inclusively. If a > b (empty range), the result is 1.
func (z nat) mulRange(a, b uint64) nat {
@@ -474,7 +453,6 @@ func (z nat) mulRange(a, b uint64) nat {
return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
}
-
// q = (x-r)/y, with 0 <= r < y
func (z nat) divW(x nat, y Word) (q nat, r Word) {
m := len(x)
@@ -495,7 +473,6 @@ func (z nat) divW(x nat, y Word) (q nat, r Word) {
return
}
-
func (z nat) div(z2, u, v nat) (q, r nat) {
if len(v) == 0 {
panic("division by zero")
@@ -523,7 +500,6 @@ func (z nat) div(z2, u, v nat) (q, r nat) {
return
}
-
// q = (uIn-r)/v, with 0 <= r < y
// Uses z as storage for q, and u as storage for r if possible.
// See Knuth, Volume 2, section 4.3.1, Algorithm D.
@@ -602,7 +578,6 @@ func (z nat) divLarge(u, uIn, v nat) (q, r nat) {
return q, r
}
-
// Length of x in bits. x must be normalized.
func (x nat) bitLen() int {
if i := len(x) - 1; i >= 0 {
@@ -611,7 +586,6 @@ func (x nat) bitLen() int {
return 0
}
-
// MaxBase is the largest number base accepted for string conversions.
const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1
@@ -629,7 +603,6 @@ func hexValue(ch int) Word {
return Word(d)
}
-
// scan sets z to the natural number corresponding to the longest possible prefix
// read from r representing an unsigned integer in a given conversion base.
// It returns z, the actual conversion base used, and an error, if any. In the
@@ -727,21 +700,18 @@ func (z nat) scan(r io.RuneScanner, base int) (nat, int, os.Error) {
return z.norm(), int(b), nil
}
-
// 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[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.
@@ -863,7 +833,6 @@ func (x nat) string(charset string) string {
return string(s[i:])
}
-
const deBruijn32 = 0x077CB531
var deBruijn32Lookup = []byte{
@@ -880,7 +849,6 @@ 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
@@ -905,7 +873,6 @@ func trailingZeroBits(x Word) int {
return 0
}
-
// z = x << s
func (z nat) shl(x nat, s uint) nat {
m := len(x)
@@ -922,7 +889,6 @@ func (z nat) shl(x nat, s uint) nat {
return z.norm()
}
-
// z = x >> s
func (z nat) shr(x nat, s uint) nat {
m := len(x)
@@ -938,7 +904,6 @@ func (z nat) shr(x nat, s uint) nat {
return z.norm()
}
-
func (z nat) setBit(x nat, i uint, b uint) nat {
j := int(i / _W)
m := Word(1) << (i % _W)
@@ -966,7 +931,6 @@ func (z nat) setBit(x nat, i uint, b uint) nat {
panic("set bit is not 0 or 1")
}
-
func (z nat) bit(i uint) uint {
j := int(i / _W)
if j >= len(z) {
@@ -975,7 +939,6 @@ func (z nat) bit(i uint) uint {
return uint(z[j] >> (i % _W) & 1)
}
-
func (z nat) and(x, y nat) nat {
m := len(x)
n := len(y)
@@ -992,7 +955,6 @@ func (z nat) and(x, y nat) nat {
return z.norm()
}
-
func (z nat) andNot(x, y nat) nat {
m := len(x)
n := len(y)
@@ -1010,7 +972,6 @@ func (z nat) andNot(x, y nat) nat {
return z.norm()
}
-
func (z nat) or(x, y nat) nat {
m := len(x)
n := len(y)
@@ -1030,7 +991,6 @@ func (z nat) or(x, y nat) nat {
return z.norm()
}
-
func (z nat) xor(x, y nat) nat {
m := len(x)
n := len(y)
@@ -1050,13 +1010,11 @@ func (z nat) xor(x, y nat) nat {
return z.norm()
}
-
// 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
}
-
// modW returns x % d.
func (x nat) modW(d Word) (r Word) {
// TODO(agl): we don't actually need to store the q value.
@@ -1065,7 +1023,6 @@ func (x nat) modW(d Word) (r Word) {
return divWVW(q, 0, x, d)
}
-
// powersOfTwoDecompose finds q and k with x = q * 1<<k and q is odd, or q and k are 0.
func (x nat) powersOfTwoDecompose() (q nat, k int) {
if len(x) == 0 {
@@ -1089,7 +1046,6 @@ func (x nat) powersOfTwoDecompose() (q nat, k int) {
return
}
-
// random creates a random integer in [0..limit), using the space in z if
// possible. n is the bit length of limit.
func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
@@ -1120,7 +1076,6 @@ func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
return z.norm()
}
-
// If m != nil, expNN calculates x**y mod m. Otherwise it calculates x**y. It
// reuses the storage of z if possible.
func (z nat) expNN(x, y, m nat) nat {
@@ -1189,7 +1144,6 @@ func (z nat) expNN(x, y, m nat) nat {
return z
}
-
// probablyPrime performs reps Miller-Rabin tests to check whether n is prime.
// If it returns true, n is prime with probability 1 - 1/4^reps.
// If it returns false, n is not prime.
@@ -1272,7 +1226,6 @@ NextRandom:
return true
}
-
// bytes writes the value of z into buf using big-endian encoding.
// len(buf) must be >= len(z)*_S. The value of z is encoded in the
// slice buf[i:]. The number i of unused bytes at the beginning of
@@ -1294,7 +1247,6 @@ func (z nat) bytes(buf []byte) (i int) {
return
}
-
// setBytes interprets buf as the bytes of a big-endian unsigned
// integer, sets z to that value, and returns z.
func (z nat) setBytes(buf []byte) nat {
generated by cgit v1.2.3 (git 2.46.0) at 2025-10-28 20:19:13 +0000