Source file src/math/big/int.go

Documentation: math/big

		 1  // Copyright 2009 The Go Authors. All rights reserved.
		 2  // Use of this source code is governed by a BSD-style
		 3  // license that can be found in the LICENSE file.
		 4  
		 5  // This file implements signed multi-precision integers.
		 6  
		 7  package big
		 8  
		 9  import (
		10  	"fmt"
		11  	"io"
		12  	"math/rand"
		13  	"strings"
		14  )
		15  
		16  // An Int represents a signed multi-precision integer.
		17  // The zero value for an Int represents the value 0.
		18  //
		19  // Operations always take pointer arguments (*Int) rather
		20  // than Int values, and each unique Int value requires
		21  // its own unique *Int pointer. To "copy" an Int value,
		22  // an existing (or newly allocated) Int must be set to
		23  // a new value using the Int.Set method; shallow copies
		24  // of Ints are not supported and may lead to errors.
		25  type Int struct {
		26  	neg bool // sign
		27  	abs nat	// absolute value of the integer
		28  }
		29  
		30  var intOne = &Int{false, natOne}
		31  
		32  // Sign returns:
		33  //
		34  //	-1 if x <	0
		35  //	 0 if x == 0
		36  //	+1 if x >	0
		37  //
		38  func (x *Int) Sign() int {
		39  	if len(x.abs) == 0 {
		40  		return 0
		41  	}
		42  	if x.neg {
		43  		return -1
		44  	}
		45  	return 1
		46  }
		47  
		48  // SetInt64 sets z to x and returns z.
		49  func (z *Int) SetInt64(x int64) *Int {
		50  	neg := false
		51  	if x < 0 {
		52  		neg = true
		53  		x = -x
		54  	}
		55  	z.abs = z.abs.setUint64(uint64(x))
		56  	z.neg = neg
		57  	return z
		58  }
		59  
		60  // SetUint64 sets z to x and returns z.
		61  func (z *Int) SetUint64(x uint64) *Int {
		62  	z.abs = z.abs.setUint64(x)
		63  	z.neg = false
		64  	return z
		65  }
		66  
		67  // NewInt allocates and returns a new Int set to x.
		68  func NewInt(x int64) *Int {
		69  	return new(Int).SetInt64(x)
		70  }
		71  
		72  // Set sets z to x and returns z.
		73  func (z *Int) Set(x *Int) *Int {
		74  	if z != x {
		75  		z.abs = z.abs.set(x.abs)
		76  		z.neg = x.neg
		77  	}
		78  	return z
		79  }
		80  
		81  // Bits provides raw (unchecked but fast) access to x by returning its
		82  // absolute value as a little-endian Word slice. The result and x share
		83  // the same underlying array.
		84  // Bits is intended to support implementation of missing low-level Int
		85  // functionality outside this package; it should be avoided otherwise.
		86  func (x *Int) Bits() []Word {
		87  	return x.abs
		88  }
		89  
		90  // SetBits provides raw (unchecked but fast) access to z by setting its
		91  // value to abs, interpreted as a little-endian Word slice, and returning
		92  // z. The result and abs share the same underlying array.
		93  // SetBits is intended to support implementation of missing low-level Int
		94  // functionality outside this package; it should be avoided otherwise.
		95  func (z *Int) SetBits(abs []Word) *Int {
		96  	z.abs = nat(abs).norm()
		97  	z.neg = false
		98  	return z
		99  }
	 100  
	 101  // Abs sets z to |x| (the absolute value of x) and returns z.
	 102  func (z *Int) Abs(x *Int) *Int {
	 103  	z.Set(x)
	 104  	z.neg = false
	 105  	return z
	 106  }
	 107  
	 108  // Neg sets z to -x and returns z.
	 109  func (z *Int) Neg(x *Int) *Int {
	 110  	z.Set(x)
	 111  	z.neg = len(z.abs) > 0 && !z.neg // 0 has no sign
	 112  	return z
	 113  }
	 114  
	 115  // Add sets z to the sum x+y and returns z.
	 116  func (z *Int) Add(x, y *Int) *Int {
	 117  	neg := x.neg
	 118  	if x.neg == y.neg {
	 119  		// x + y == x + y
	 120  		// (-x) + (-y) == -(x + y)
	 121  		z.abs = z.abs.add(x.abs, y.abs)
	 122  	} else {
	 123  		// x + (-y) == x - y == -(y - x)
	 124  		// (-x) + y == y - x == -(x - y)
	 125  		if x.abs.cmp(y.abs) >= 0 {
	 126  			z.abs = z.abs.sub(x.abs, y.abs)
	 127  		} else {
	 128  			neg = !neg
	 129  			z.abs = z.abs.sub(y.abs, x.abs)
	 130  		}
	 131  	}
	 132  	z.neg = len(z.abs) > 0 && neg // 0 has no sign
	 133  	return z
	 134  }
	 135  
	 136  // Sub sets z to the difference x-y and returns z.
	 137  func (z *Int) Sub(x, y *Int) *Int {
	 138  	neg := x.neg
	 139  	if x.neg != y.neg {
	 140  		// x - (-y) == x + y
	 141  		// (-x) - y == -(x + y)
	 142  		z.abs = z.abs.add(x.abs, y.abs)
	 143  	} else {
	 144  		// x - y == x - y == -(y - x)
	 145  		// (-x) - (-y) == y - x == -(x - y)
	 146  		if x.abs.cmp(y.abs) >= 0 {
	 147  			z.abs = z.abs.sub(x.abs, y.abs)
	 148  		} else {
	 149  			neg = !neg
	 150  			z.abs = z.abs.sub(y.abs, x.abs)
	 151  		}
	 152  	}
	 153  	z.neg = len(z.abs) > 0 && neg // 0 has no sign
	 154  	return z
	 155  }
	 156  
	 157  // Mul sets z to the product x*y and returns z.
	 158  func (z *Int) Mul(x, y *Int) *Int {
	 159  	// x * y == x * y
	 160  	// x * (-y) == -(x * y)
	 161  	// (-x) * y == -(x * y)
	 162  	// (-x) * (-y) == x * y
	 163  	if x == y {
	 164  		z.abs = z.abs.sqr(x.abs)
	 165  		z.neg = false
	 166  		return z
	 167  	}
	 168  	z.abs = z.abs.mul(x.abs, y.abs)
	 169  	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
	 170  	return z
	 171  }
	 172  
	 173  // MulRange sets z to the product of all integers
	 174  // in the range [a, b] inclusively and returns z.
	 175  // If a > b (empty range), the result is 1.
	 176  func (z *Int) MulRange(a, b int64) *Int {
	 177  	switch {
	 178  	case a > b:
	 179  		return z.SetInt64(1) // empty range
	 180  	case a <= 0 && b >= 0:
	 181  		return z.SetInt64(0) // range includes 0
	 182  	}
	 183  	// a <= b && (b < 0 || a > 0)
	 184  
	 185  	neg := false
	 186  	if a < 0 {
	 187  		neg = (b-a)&1 == 0
	 188  		a, b = -b, -a
	 189  	}
	 190  
	 191  	z.abs = z.abs.mulRange(uint64(a), uint64(b))
	 192  	z.neg = neg
	 193  	return z
	 194  }
	 195  
	 196  // Binomial sets z to the binomial coefficient of (n, k) and returns z.
	 197  func (z *Int) Binomial(n, k int64) *Int {
	 198  	// reduce the number of multiplications by reducing k
	 199  	if n/2 < k && k <= n {
	 200  		k = n - k // Binomial(n, k) == Binomial(n, n-k)
	 201  	}
	 202  	var a, b Int
	 203  	a.MulRange(n-k+1, n)
	 204  	b.MulRange(1, k)
	 205  	return z.Quo(&a, &b)
	 206  }
	 207  
	 208  // Quo sets z to the quotient x/y for y != 0 and returns z.
	 209  // If y == 0, a division-by-zero run-time panic occurs.
	 210  // Quo implements truncated division (like Go); see QuoRem for more details.
	 211  func (z *Int) Quo(x, y *Int) *Int {
	 212  	z.abs, _ = z.abs.div(nil, x.abs, y.abs)
	 213  	z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
	 214  	return z
	 215  }
	 216  
	 217  // Rem sets z to the remainder x%y for y != 0 and returns z.
	 218  // If y == 0, a division-by-zero run-time panic occurs.
	 219  // Rem implements truncated modulus (like Go); see QuoRem for more details.
	 220  func (z *Int) Rem(x, y *Int) *Int {
	 221  	_, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
	 222  	z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
	 223  	return z
	 224  }
	 225  
	 226  // QuoRem sets z to the quotient x/y and r to the remainder x%y
	 227  // and returns the pair (z, r) for y != 0.
	 228  // If y == 0, a division-by-zero run-time panic occurs.
	 229  //
	 230  // QuoRem implements T-division and modulus (like Go):
	 231  //
	 232  //	q = x/y			with the result truncated to zero
	 233  //	r = x - y*q
	 234  //
	 235  // (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
	 236  // See DivMod for Euclidean division and modulus (unlike Go).
	 237  //
	 238  func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
	 239  	z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
	 240  	z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign
	 241  	return z, r
	 242  }
	 243  
	 244  // Div sets z to the quotient x/y for y != 0 and returns z.
	 245  // If y == 0, a division-by-zero run-time panic occurs.
	 246  // Div implements Euclidean division (unlike Go); see DivMod for more details.
	 247  func (z *Int) Div(x, y *Int) *Int {
	 248  	y_neg := y.neg // z may be an alias for y
	 249  	var r Int
	 250  	z.QuoRem(x, y, &r)
	 251  	if r.neg {
	 252  		if y_neg {
	 253  			z.Add(z, intOne)
	 254  		} else {
	 255  			z.Sub(z, intOne)
	 256  		}
	 257  	}
	 258  	return z
	 259  }
	 260  
	 261  // Mod sets z to the modulus x%y for y != 0 and returns z.
	 262  // If y == 0, a division-by-zero run-time panic occurs.
	 263  // Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
	 264  func (z *Int) Mod(x, y *Int) *Int {
	 265  	y0 := y // save y
	 266  	if z == y || alias(z.abs, y.abs) {
	 267  		y0 = new(Int).Set(y)
	 268  	}
	 269  	var q Int
	 270  	q.QuoRem(x, y, z)
	 271  	if z.neg {
	 272  		if y0.neg {
	 273  			z.Sub(z, y0)
	 274  		} else {
	 275  			z.Add(z, y0)
	 276  		}
	 277  	}
	 278  	return z
	 279  }
	 280  
	 281  // DivMod sets z to the quotient x div y and m to the modulus x mod y
	 282  // and returns the pair (z, m) for y != 0.
	 283  // If y == 0, a division-by-zero run-time panic occurs.
	 284  //
	 285  // DivMod implements Euclidean division and modulus (unlike Go):
	 286  //
	 287  //	q = x div y	such that
	 288  //	m = x - y*q	with 0 <= m < |y|
	 289  //
	 290  // (See Raymond T. Boute, ``The Euclidean definition of the functions
	 291  // div and mod''. ACM Transactions on Programming Languages and
	 292  // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
	 293  // ACM press.)
	 294  // See QuoRem for T-division and modulus (like Go).
	 295  //
	 296  func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
	 297  	y0 := y // save y
	 298  	if z == y || alias(z.abs, y.abs) {
	 299  		y0 = new(Int).Set(y)
	 300  	}
	 301  	z.QuoRem(x, y, m)
	 302  	if m.neg {
	 303  		if y0.neg {
	 304  			z.Add(z, intOne)
	 305  			m.Sub(m, y0)
	 306  		} else {
	 307  			z.Sub(z, intOne)
	 308  			m.Add(m, y0)
	 309  		}
	 310  	}
	 311  	return z, m
	 312  }
	 313  
	 314  // Cmp compares x and y and returns:
	 315  //
	 316  //	 -1 if x <	y
	 317  //		0 if x == y
	 318  //	 +1 if x >	y
	 319  //
	 320  func (x *Int) Cmp(y *Int) (r int) {
	 321  	// x cmp y == x cmp y
	 322  	// x cmp (-y) == x
	 323  	// (-x) cmp y == y
	 324  	// (-x) cmp (-y) == -(x cmp y)
	 325  	switch {
	 326  	case x == y:
	 327  		// nothing to do
	 328  	case x.neg == y.neg:
	 329  		r = x.abs.cmp(y.abs)
	 330  		if x.neg {
	 331  			r = -r
	 332  		}
	 333  	case x.neg:
	 334  		r = -1
	 335  	default:
	 336  		r = 1
	 337  	}
	 338  	return
	 339  }
	 340  
	 341  // CmpAbs compares the absolute values of x and y and returns:
	 342  //
	 343  //	 -1 if |x| <	|y|
	 344  //		0 if |x| == |y|
	 345  //	 +1 if |x| >	|y|
	 346  //
	 347  func (x *Int) CmpAbs(y *Int) int {
	 348  	return x.abs.cmp(y.abs)
	 349  }
	 350  
	 351  // low32 returns the least significant 32 bits of x.
	 352  func low32(x nat) uint32 {
	 353  	if len(x) == 0 {
	 354  		return 0
	 355  	}
	 356  	return uint32(x[0])
	 357  }
	 358  
	 359  // low64 returns the least significant 64 bits of x.
	 360  func low64(x nat) uint64 {
	 361  	if len(x) == 0 {
	 362  		return 0
	 363  	}
	 364  	v := uint64(x[0])
	 365  	if _W == 32 && len(x) > 1 {
	 366  		return uint64(x[1])<<32 | v
	 367  	}
	 368  	return v
	 369  }
	 370  
	 371  // Int64 returns the int64 representation of x.
	 372  // If x cannot be represented in an int64, the result is undefined.
	 373  func (x *Int) Int64() int64 {
	 374  	v := int64(low64(x.abs))
	 375  	if x.neg {
	 376  		v = -v
	 377  	}
	 378  	return v
	 379  }
	 380  
	 381  // Uint64 returns the uint64 representation of x.
	 382  // If x cannot be represented in a uint64, the result is undefined.
	 383  func (x *Int) Uint64() uint64 {
	 384  	return low64(x.abs)
	 385  }
	 386  
	 387  // IsInt64 reports whether x can be represented as an int64.
	 388  func (x *Int) IsInt64() bool {
	 389  	if len(x.abs) <= 64/_W {
	 390  		w := int64(low64(x.abs))
	 391  		return w >= 0 || x.neg && w == -w
	 392  	}
	 393  	return false
	 394  }
	 395  
	 396  // IsUint64 reports whether x can be represented as a uint64.
	 397  func (x *Int) IsUint64() bool {
	 398  	return !x.neg && len(x.abs) <= 64/_W
	 399  }
	 400  
	 401  // SetString sets z to the value of s, interpreted in the given base,
	 402  // and returns z and a boolean indicating success. The entire string
	 403  // (not just a prefix) must be valid for success. If SetString fails,
	 404  // the value of z is undefined but the returned value is nil.
	 405  //
	 406  // The base argument must be 0 or a value between 2 and MaxBase.
	 407  // For base 0, the number prefix determines the actual base: A prefix of
	 408  // ``0b'' or ``0B'' selects base 2, ``0'', ``0o'' or ``0O'' selects base 8,
	 409  // and ``0x'' or ``0X'' selects base 16. Otherwise, the selected base is 10
	 410  // and no prefix is accepted.
	 411  //
	 412  // For bases <= 36, lower and upper case letters are considered the same:
	 413  // The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.
	 414  // For bases > 36, the upper case letters 'A' to 'Z' represent the digit
	 415  // values 36 to 61.
	 416  //
	 417  // For base 0, an underscore character ``_'' may appear between a base
	 418  // prefix and an adjacent digit, and between successive digits; such
	 419  // underscores do not change the value of the number.
	 420  // Incorrect placement of underscores is reported as an error if there
	 421  // are no other errors. If base != 0, underscores are not recognized
	 422  // and act like any other character that is not a valid digit.
	 423  //
	 424  func (z *Int) SetString(s string, base int) (*Int, bool) {
	 425  	return z.setFromScanner(strings.NewReader(s), base)
	 426  }
	 427  
	 428  // setFromScanner implements SetString given an io.ByteScanner.
	 429  // For documentation see comments of SetString.
	 430  func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool) {
	 431  	if _, _, err := z.scan(r, base); err != nil {
	 432  		return nil, false
	 433  	}
	 434  	// entire content must have been consumed
	 435  	if _, err := r.ReadByte(); err != io.EOF {
	 436  		return nil, false
	 437  	}
	 438  	return z, true // err == io.EOF => scan consumed all content of r
	 439  }
	 440  
	 441  // SetBytes interprets buf as the bytes of a big-endian unsigned
	 442  // integer, sets z to that value, and returns z.
	 443  func (z *Int) SetBytes(buf []byte) *Int {
	 444  	z.abs = z.abs.setBytes(buf)
	 445  	z.neg = false
	 446  	return z
	 447  }
	 448  
	 449  // Bytes returns the absolute value of x as a big-endian byte slice.
	 450  //
	 451  // To use a fixed length slice, or a preallocated one, use FillBytes.
	 452  func (x *Int) Bytes() []byte {
	 453  	buf := make([]byte, len(x.abs)*_S)
	 454  	return buf[x.abs.bytes(buf):]
	 455  }
	 456  
	 457  // FillBytes sets buf to the absolute value of x, storing it as a zero-extended
	 458  // big-endian byte slice, and returns buf.
	 459  //
	 460  // If the absolute value of x doesn't fit in buf, FillBytes will panic.
	 461  func (x *Int) FillBytes(buf []byte) []byte {
	 462  	// Clear whole buffer. (This gets optimized into a memclr.)
	 463  	for i := range buf {
	 464  		buf[i] = 0
	 465  	}
	 466  	x.abs.bytes(buf)
	 467  	return buf
	 468  }
	 469  
	 470  // BitLen returns the length of the absolute value of x in bits.
	 471  // The bit length of 0 is 0.
	 472  func (x *Int) BitLen() int {
	 473  	return x.abs.bitLen()
	 474  }
	 475  
	 476  // TrailingZeroBits returns the number of consecutive least significant zero
	 477  // bits of |x|.
	 478  func (x *Int) TrailingZeroBits() uint {
	 479  	return x.abs.trailingZeroBits()
	 480  }
	 481  
	 482  // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
	 483  // If m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m != 0, y < 0,
	 484  // and x and m are not relatively prime, z is unchanged and nil is returned.
	 485  //
	 486  // Modular exponentiation of inputs of a particular size is not a
	 487  // cryptographically constant-time operation.
	 488  func (z *Int) Exp(x, y, m *Int) *Int {
	 489  	// See Knuth, volume 2, section 4.6.3.
	 490  	xWords := x.abs
	 491  	if y.neg {
	 492  		if m == nil || len(m.abs) == 0 {
	 493  			return z.SetInt64(1)
	 494  		}
	 495  		// for y < 0: x**y mod m == (x**(-1))**|y| mod m
	 496  		inverse := new(Int).ModInverse(x, m)
	 497  		if inverse == nil {
	 498  			return nil
	 499  		}
	 500  		xWords = inverse.abs
	 501  	}
	 502  	yWords := y.abs
	 503  
	 504  	var mWords nat
	 505  	if m != nil {
	 506  		mWords = m.abs // m.abs may be nil for m == 0
	 507  	}
	 508  
	 509  	z.abs = z.abs.expNN(xWords, yWords, mWords)
	 510  	z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign
	 511  	if z.neg && len(mWords) > 0 {
	 512  		// make modulus result positive
	 513  		z.abs = z.abs.sub(mWords, z.abs) // z == x**y mod |m| && 0 <= z < |m|
	 514  		z.neg = false
	 515  	}
	 516  
	 517  	return z
	 518  }
	 519  
	 520  // GCD sets z to the greatest common divisor of a and b and returns z.
	 521  // If x or y are not nil, GCD sets their value such that z = a*x + b*y.
	 522  //
	 523  // a and b may be positive, zero or negative. (Before Go 1.14 both had
	 524  // to be > 0.) Regardless of the signs of a and b, z is always >= 0.
	 525  //
	 526  // If a == b == 0, GCD sets z = x = y = 0.
	 527  //
	 528  // If a == 0 and b != 0, GCD sets z = |b|, x = 0, y = sign(b) * 1.
	 529  //
	 530  // If a != 0 and b == 0, GCD sets z = |a|, x = sign(a) * 1, y = 0.
	 531  func (z *Int) GCD(x, y, a, b *Int) *Int {
	 532  	if len(a.abs) == 0 || len(b.abs) == 0 {
	 533  		lenA, lenB, negA, negB := len(a.abs), len(b.abs), a.neg, b.neg
	 534  		if lenA == 0 {
	 535  			z.Set(b)
	 536  		} else {
	 537  			z.Set(a)
	 538  		}
	 539  		z.neg = false
	 540  		if x != nil {
	 541  			if lenA == 0 {
	 542  				x.SetUint64(0)
	 543  			} else {
	 544  				x.SetUint64(1)
	 545  				x.neg = negA
	 546  			}
	 547  		}
	 548  		if y != nil {
	 549  			if lenB == 0 {
	 550  				y.SetUint64(0)
	 551  			} else {
	 552  				y.SetUint64(1)
	 553  				y.neg = negB
	 554  			}
	 555  		}
	 556  		return z
	 557  	}
	 558  
	 559  	return z.lehmerGCD(x, y, a, b)
	 560  }
	 561  
	 562  // lehmerSimulate attempts to simulate several Euclidean update steps
	 563  // using the leading digits of A and B.	It returns u0, u1, v0, v1
	 564  // such that A and B can be updated as:
	 565  //		A = u0*A + v0*B
	 566  //		B = u1*A + v1*B
	 567  // Requirements: A >= B and len(B.abs) >= 2
	 568  // Since we are calculating with full words to avoid overflow,
	 569  // we use 'even' to track the sign of the cosequences.
	 570  // For even iterations: u0, v1 >= 0 && u1, v0 <= 0
	 571  // For odd	iterations: u0, v1 <= 0 && u1, v0 >= 0
	 572  func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool) {
	 573  	// initialize the digits
	 574  	var a1, a2, u2, v2 Word
	 575  
	 576  	m := len(B.abs) // m >= 2
	 577  	n := len(A.abs) // n >= m >= 2
	 578  
	 579  	// extract the top Word of bits from A and B
	 580  	h := nlz(A.abs[n-1])
	 581  	a1 = A.abs[n-1]<<h | A.abs[n-2]>>(_W-h)
	 582  	// B may have implicit zero words in the high bits if the lengths differ
	 583  	switch {
	 584  	case n == m:
	 585  		a2 = B.abs[n-1]<<h | B.abs[n-2]>>(_W-h)
	 586  	case n == m+1:
	 587  		a2 = B.abs[n-2] >> (_W - h)
	 588  	default:
	 589  		a2 = 0
	 590  	}
	 591  
	 592  	// Since we are calculating with full words to avoid overflow,
	 593  	// we use 'even' to track the sign of the cosequences.
	 594  	// For even iterations: u0, v1 >= 0 && u1, v0 <= 0
	 595  	// For odd	iterations: u0, v1 <= 0 && u1, v0 >= 0
	 596  	// The first iteration starts with k=1 (odd).
	 597  	even = false
	 598  	// variables to track the cosequences
	 599  	u0, u1, u2 = 0, 1, 0
	 600  	v0, v1, v2 = 0, 0, 1
	 601  
	 602  	// Calculate the quotient and cosequences using Collins' stopping condition.
	 603  	// Note that overflow of a Word is not possible when computing the remainder
	 604  	// sequence and cosequences since the cosequence size is bounded by the input size.
	 605  	// See section 4.2 of Jebelean for details.
	 606  	for a2 >= v2 && a1-a2 >= v1+v2 {
	 607  		q, r := a1/a2, a1%a2
	 608  		a1, a2 = a2, r
	 609  		u0, u1, u2 = u1, u2, u1+q*u2
	 610  		v0, v1, v2 = v1, v2, v1+q*v2
	 611  		even = !even
	 612  	}
	 613  	return
	 614  }
	 615  
	 616  // lehmerUpdate updates the inputs A and B such that:
	 617  //		A = u0*A + v0*B
	 618  //		B = u1*A + v1*B
	 619  // where the signs of u0, u1, v0, v1 are given by even
	 620  // For even == true: u0, v1 >= 0 && u1, v0 <= 0
	 621  // For even == false: u0, v1 <= 0 && u1, v0 >= 0
	 622  // q, r, s, t are temporary variables to avoid allocations in the multiplication
	 623  func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool) {
	 624  
	 625  	t.abs = t.abs.setWord(u0)
	 626  	s.abs = s.abs.setWord(v0)
	 627  	t.neg = !even
	 628  	s.neg = even
	 629  
	 630  	t.Mul(A, t)
	 631  	s.Mul(B, s)
	 632  
	 633  	r.abs = r.abs.setWord(u1)
	 634  	q.abs = q.abs.setWord(v1)
	 635  	r.neg = even
	 636  	q.neg = !even
	 637  
	 638  	r.Mul(A, r)
	 639  	q.Mul(B, q)
	 640  
	 641  	A.Add(t, s)
	 642  	B.Add(r, q)
	 643  }
	 644  
	 645  // euclidUpdate performs a single step of the Euclidean GCD algorithm
	 646  // if extended is true, it also updates the cosequence Ua, Ub
	 647  func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool) {
	 648  	q, r = q.QuoRem(A, B, r)
	 649  
	 650  	*A, *B, *r = *B, *r, *A
	 651  
	 652  	if extended {
	 653  		// Ua, Ub = Ub, Ua - q*Ub
	 654  		t.Set(Ub)
	 655  		s.Mul(Ub, q)
	 656  		Ub.Sub(Ua, s)
	 657  		Ua.Set(t)
	 658  	}
	 659  }
	 660  
	 661  // lehmerGCD sets z to the greatest common divisor of a and b,
	 662  // which both must be != 0, and returns z.
	 663  // If x or y are not nil, their values are set such that z = a*x + b*y.
	 664  // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm L.
	 665  // This implementation uses the improved condition by Collins requiring only one
	 666  // quotient and avoiding the possibility of single Word overflow.
	 667  // See Jebelean, "Improving the multiprecision Euclidean algorithm",
	 668  // Design and Implementation of Symbolic Computation Systems, pp 45-58.
	 669  // The cosequences are updated according to Algorithm 10.45 from
	 670  // Cohen et al. "Handbook of Elliptic and Hyperelliptic Curve Cryptography" pp 192.
	 671  func (z *Int) lehmerGCD(x, y, a, b *Int) *Int {
	 672  	var A, B, Ua, Ub *Int
	 673  
	 674  	A = new(Int).Abs(a)
	 675  	B = new(Int).Abs(b)
	 676  
	 677  	extended := x != nil || y != nil
	 678  
	 679  	if extended {
	 680  		// Ua (Ub) tracks how many times input a has been accumulated into A (B).
	 681  		Ua = new(Int).SetInt64(1)
	 682  		Ub = new(Int)
	 683  	}
	 684  
	 685  	// temp variables for multiprecision update
	 686  	q := new(Int)
	 687  	r := new(Int)
	 688  	s := new(Int)
	 689  	t := new(Int)
	 690  
	 691  	// ensure A >= B
	 692  	if A.abs.cmp(B.abs) < 0 {
	 693  		A, B = B, A
	 694  		Ub, Ua = Ua, Ub
	 695  	}
	 696  
	 697  	// loop invariant A >= B
	 698  	for len(B.abs) > 1 {
	 699  		// Attempt to calculate in single-precision using leading words of A and B.
	 700  		u0, u1, v0, v1, even := lehmerSimulate(A, B)
	 701  
	 702  		// multiprecision Step
	 703  		if v0 != 0 {
	 704  			// Simulate the effect of the single-precision steps using the cosequences.
	 705  			// A = u0*A + v0*B
	 706  			// B = u1*A + v1*B
	 707  			lehmerUpdate(A, B, q, r, s, t, u0, u1, v0, v1, even)
	 708  
	 709  			if extended {
	 710  				// Ua = u0*Ua + v0*Ub
	 711  				// Ub = u1*Ua + v1*Ub
	 712  				lehmerUpdate(Ua, Ub, q, r, s, t, u0, u1, v0, v1, even)
	 713  			}
	 714  
	 715  		} else {
	 716  			// Single-digit calculations failed to simulate any quotients.
	 717  			// Do a standard Euclidean step.
	 718  			euclidUpdate(A, B, Ua, Ub, q, r, s, t, extended)
	 719  		}
	 720  	}
	 721  
	 722  	if len(B.abs) > 0 {
	 723  		// extended Euclidean algorithm base case if B is a single Word
	 724  		if len(A.abs) > 1 {
	 725  			// A is longer than a single Word, so one update is needed.
	 726  			euclidUpdate(A, B, Ua, Ub, q, r, s, t, extended)
	 727  		}
	 728  		if len(B.abs) > 0 {
	 729  			// A and B are both a single Word.
	 730  			aWord, bWord := A.abs[0], B.abs[0]
	 731  			if extended {
	 732  				var ua, ub, va, vb Word
	 733  				ua, ub = 1, 0
	 734  				va, vb = 0, 1
	 735  				even := true
	 736  				for bWord != 0 {
	 737  					q, r := aWord/bWord, aWord%bWord
	 738  					aWord, bWord = bWord, r
	 739  					ua, ub = ub, ua+q*ub
	 740  					va, vb = vb, va+q*vb
	 741  					even = !even
	 742  				}
	 743  
	 744  				t.abs = t.abs.setWord(ua)
	 745  				s.abs = s.abs.setWord(va)
	 746  				t.neg = !even
	 747  				s.neg = even
	 748  
	 749  				t.Mul(Ua, t)
	 750  				s.Mul(Ub, s)
	 751  
	 752  				Ua.Add(t, s)
	 753  			} else {
	 754  				for bWord != 0 {
	 755  					aWord, bWord = bWord, aWord%bWord
	 756  				}
	 757  			}
	 758  			A.abs[0] = aWord
	 759  		}
	 760  	}
	 761  	negA := a.neg
	 762  	if y != nil {
	 763  		// avoid aliasing b needed in the division below
	 764  		if y == b {
	 765  			B.Set(b)
	 766  		} else {
	 767  			B = b
	 768  		}
	 769  		// y = (z - a*x)/b
	 770  		y.Mul(a, Ua) // y can safely alias a
	 771  		if negA {
	 772  			y.neg = !y.neg
	 773  		}
	 774  		y.Sub(A, y)
	 775  		y.Div(y, B)
	 776  	}
	 777  
	 778  	if x != nil {
	 779  		*x = *Ua
	 780  		if negA {
	 781  			x.neg = !x.neg
	 782  		}
	 783  	}
	 784  
	 785  	*z = *A
	 786  
	 787  	return z
	 788  }
	 789  
	 790  // Rand sets z to a pseudo-random number in [0, n) and returns z.
	 791  //
	 792  // As this uses the math/rand package, it must not be used for
	 793  // security-sensitive work. Use crypto/rand.Int instead.
	 794  func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
	 795  	z.neg = false
	 796  	if n.neg || len(n.abs) == 0 {
	 797  		z.abs = nil
	 798  		return z
	 799  	}
	 800  	z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
	 801  	return z
	 802  }
	 803  
	 804  // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
	 805  // and returns z. If g and n are not relatively prime, g has no multiplicative
	 806  // inverse in the ring ℤ/nℤ.	In this case, z is unchanged and the return value
	 807  // is nil.
	 808  func (z *Int) ModInverse(g, n *Int) *Int {
	 809  	// GCD expects parameters a and b to be > 0.
	 810  	if n.neg {
	 811  		var n2 Int
	 812  		n = n2.Neg(n)
	 813  	}
	 814  	if g.neg {
	 815  		var g2 Int
	 816  		g = g2.Mod(g, n)
	 817  	}
	 818  	var d, x Int
	 819  	d.GCD(&x, nil, g, n)
	 820  
	 821  	// if and only if d==1, g and n are relatively prime
	 822  	if d.Cmp(intOne) != 0 {
	 823  		return nil
	 824  	}
	 825  
	 826  	// x and y are such that g*x + n*y = 1, therefore x is the inverse element,
	 827  	// but it may be negative, so convert to the range 0 <= z < |n|
	 828  	if x.neg {
	 829  		z.Add(&x, n)
	 830  	} else {
	 831  		z.Set(&x)
	 832  	}
	 833  	return z
	 834  }
	 835  
	 836  // Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
	 837  // The y argument must be an odd integer.
	 838  func Jacobi(x, y *Int) int {
	 839  	if len(y.abs) == 0 || y.abs[0]&1 == 0 {
	 840  		panic(fmt.Sprintf("big: invalid 2nd argument to Int.Jacobi: need odd integer but got %s", y))
	 841  	}
	 842  
	 843  	// We use the formulation described in chapter 2, section 2.4,
	 844  	// "The Yacas Book of Algorithms":
	 845  	// http://yacas.sourceforge.net/Algo.book.pdf
	 846  
	 847  	var a, b, c Int
	 848  	a.Set(x)
	 849  	b.Set(y)
	 850  	j := 1
	 851  
	 852  	if b.neg {
	 853  		if a.neg {
	 854  			j = -1
	 855  		}
	 856  		b.neg = false
	 857  	}
	 858  
	 859  	for {
	 860  		if b.Cmp(intOne) == 0 {
	 861  			return j
	 862  		}
	 863  		if len(a.abs) == 0 {
	 864  			return 0
	 865  		}
	 866  		a.Mod(&a, &b)
	 867  		if len(a.abs) == 0 {
	 868  			return 0
	 869  		}
	 870  		// a > 0
	 871  
	 872  		// handle factors of 2 in 'a'
	 873  		s := a.abs.trailingZeroBits()
	 874  		if s&1 != 0 {
	 875  			bmod8 := b.abs[0] & 7
	 876  			if bmod8 == 3 || bmod8 == 5 {
	 877  				j = -j
	 878  			}
	 879  		}
	 880  		c.Rsh(&a, s) // a = 2^s*c
	 881  
	 882  		// swap numerator and denominator
	 883  		if b.abs[0]&3 == 3 && c.abs[0]&3 == 3 {
	 884  			j = -j
	 885  		}
	 886  		a.Set(&b)
	 887  		b.Set(&c)
	 888  	}
	 889  }
	 890  
	 891  // modSqrt3Mod4 uses the identity
	 892  //			(a^((p+1)/4))^2	mod p
	 893  //	 == u^(p+1)					mod p
	 894  //	 == u^2							mod p
	 895  // to calculate the square root of any quadratic residue mod p quickly for 3
	 896  // mod 4 primes.
	 897  func (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int {
	 898  	e := new(Int).Add(p, intOne) // e = p + 1
	 899  	e.Rsh(e, 2)									// e = (p + 1) / 4
	 900  	z.Exp(x, e, p)							 // z = x^e mod p
	 901  	return z
	 902  }
	 903  
	 904  // modSqrt5Mod8 uses Atkin's observation that 2 is not a square mod p
	 905  //	 alpha ==	(2*a)^((p-5)/8)		mod p
	 906  //	 beta	==	2*a*alpha^2				mod p	is a square root of -1
	 907  //	 b		 ==	a*alpha*(beta-1)	 mod p	is a square root of a
	 908  // to calculate the square root of any quadratic residue mod p quickly for 5
	 909  // mod 8 primes.
	 910  func (z *Int) modSqrt5Mod8Prime(x, p *Int) *Int {
	 911  	// p == 5 mod 8 implies p = e*8 + 5
	 912  	// e is the quotient and 5 the remainder on division by 8
	 913  	e := new(Int).Rsh(p, 3)	// e = (p - 5) / 8
	 914  	tx := new(Int).Lsh(x, 1) // tx = 2*x
	 915  	alpha := new(Int).Exp(tx, e, p)
	 916  	beta := new(Int).Mul(alpha, alpha)
	 917  	beta.Mod(beta, p)
	 918  	beta.Mul(beta, tx)
	 919  	beta.Mod(beta, p)
	 920  	beta.Sub(beta, intOne)
	 921  	beta.Mul(beta, x)
	 922  	beta.Mod(beta, p)
	 923  	beta.Mul(beta, alpha)
	 924  	z.Mod(beta, p)
	 925  	return z
	 926  }
	 927  
	 928  // modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square
	 929  // root of a quadratic residue modulo any prime.
	 930  func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int {
	 931  	// Break p-1 into s*2^e such that s is odd.
	 932  	var s Int
	 933  	s.Sub(p, intOne)
	 934  	e := s.abs.trailingZeroBits()
	 935  	s.Rsh(&s, e)
	 936  
	 937  	// find some non-square n
	 938  	var n Int
	 939  	n.SetInt64(2)
	 940  	for Jacobi(&n, p) != -1 {
	 941  		n.Add(&n, intOne)
	 942  	}
	 943  
	 944  	// Core of the Tonelli-Shanks algorithm. Follows the description in
	 945  	// section 6 of "Square roots from 1; 24, 51, 10 to Dan Shanks" by Ezra
	 946  	// Brown:
	 947  	// https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
	 948  	var y, b, g, t Int
	 949  	y.Add(&s, intOne)
	 950  	y.Rsh(&y, 1)
	 951  	y.Exp(x, &y, p)	// y = x^((s+1)/2)
	 952  	b.Exp(x, &s, p)	// b = x^s
	 953  	g.Exp(&n, &s, p) // g = n^s
	 954  	r := e
	 955  	for {
	 956  		// find the least m such that ord_p(b) = 2^m
	 957  		var m uint
	 958  		t.Set(&b)
	 959  		for t.Cmp(intOne) != 0 {
	 960  			t.Mul(&t, &t).Mod(&t, p)
	 961  			m++
	 962  		}
	 963  
	 964  		if m == 0 {
	 965  			return z.Set(&y)
	 966  		}
	 967  
	 968  		t.SetInt64(0).SetBit(&t, int(r-m-1), 1).Exp(&g, &t, p)
	 969  		// t = g^(2^(r-m-1)) mod p
	 970  		g.Mul(&t, &t).Mod(&g, p) // g = g^(2^(r-m)) mod p
	 971  		y.Mul(&y, &t).Mod(&y, p)
	 972  		b.Mul(&b, &g).Mod(&b, p)
	 973  		r = m
	 974  	}
	 975  }
	 976  
	 977  // ModSqrt sets z to a square root of x mod p if such a square root exists, and
	 978  // returns z. The modulus p must be an odd prime. If x is not a square mod p,
	 979  // ModSqrt leaves z unchanged and returns nil. This function panics if p is
	 980  // not an odd integer.
	 981  func (z *Int) ModSqrt(x, p *Int) *Int {
	 982  	switch Jacobi(x, p) {
	 983  	case -1:
	 984  		return nil // x is not a square mod p
	 985  	case 0:
	 986  		return z.SetInt64(0) // sqrt(0) mod p = 0
	 987  	case 1:
	 988  		break
	 989  	}
	 990  	if x.neg || x.Cmp(p) >= 0 { // ensure 0 <= x < p
	 991  		x = new(Int).Mod(x, p)
	 992  	}
	 993  
	 994  	switch {
	 995  	case p.abs[0]%4 == 3:
	 996  		// Check whether p is 3 mod 4, and if so, use the faster algorithm.
	 997  		return z.modSqrt3Mod4Prime(x, p)
	 998  	case p.abs[0]%8 == 5:
	 999  		// Check whether p is 5 mod 8, use Atkin's algorithm.
	1000  		return z.modSqrt5Mod8Prime(x, p)
	1001  	default:
	1002  		// Otherwise, use Tonelli-Shanks.
	1003  		return z.modSqrtTonelliShanks(x, p)
	1004  	}
	1005  }
	1006  
	1007  // Lsh sets z = x << n and returns z.
	1008  func (z *Int) Lsh(x *Int, n uint) *Int {
	1009  	z.abs = z.abs.shl(x.abs, n)
	1010  	z.neg = x.neg
	1011  	return z
	1012  }
	1013  
	1014  // Rsh sets z = x >> n and returns z.
	1015  func (z *Int) Rsh(x *Int, n uint) *Int {
	1016  	if x.neg {
	1017  		// (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
	1018  		t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0
	1019  		t = t.shr(t, n)
	1020  		z.abs = t.add(t, natOne)
	1021  		z.neg = true // z cannot be zero if x is negative
	1022  		return z
	1023  	}
	1024  
	1025  	z.abs = z.abs.shr(x.abs, n)
	1026  	z.neg = false
	1027  	return z
	1028  }
	1029  
	1030  // Bit returns the value of the i'th bit of x. That is, it
	1031  // returns (x>>i)&1. The bit index i must be >= 0.
	1032  func (x *Int) Bit(i int) uint {
	1033  	if i == 0 {
	1034  		// optimization for common case: odd/even test of x
	1035  		if len(x.abs) > 0 {
	1036  			return uint(x.abs[0] & 1) // bit 0 is same for -x
	1037  		}
	1038  		return 0
	1039  	}
	1040  	if i < 0 {
	1041  		panic("negative bit index")
	1042  	}
	1043  	if x.neg {
	1044  		t := nat(nil).sub(x.abs, natOne)
	1045  		return t.bit(uint(i)) ^ 1
	1046  	}
	1047  
	1048  	return x.abs.bit(uint(i))
	1049  }
	1050  
	1051  // SetBit sets z to x, with x's i'th bit set to b (0 or 1).
	1052  // That is, if b is 1 SetBit sets z = x | (1 << i);
	1053  // if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1,
	1054  // SetBit will panic.
	1055  func (z *Int) SetBit(x *Int, i int, b uint) *Int {
	1056  	if i < 0 {
	1057  		panic("negative bit index")
	1058  	}
	1059  	if x.neg {
	1060  		t := z.abs.sub(x.abs, natOne)
	1061  		t = t.setBit(t, uint(i), b^1)
	1062  		z.abs = t.add(t, natOne)
	1063  		z.neg = len(z.abs) > 0
	1064  		return z
	1065  	}
	1066  	z.abs = z.abs.setBit(x.abs, uint(i), b)
	1067  	z.neg = false
	1068  	return z
	1069  }
	1070  
	1071  // And sets z = x & y and returns z.
	1072  func (z *Int) And(x, y *Int) *Int {
	1073  	if x.neg == y.neg {
	1074  		if x.neg {
	1075  			// (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
	1076  			x1 := nat(nil).sub(x.abs, natOne)
	1077  			y1 := nat(nil).sub(y.abs, natOne)
	1078  			z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
	1079  			z.neg = true // z cannot be zero if x and y are negative
	1080  			return z
	1081  		}
	1082  
	1083  		// x & y == x & y
	1084  		z.abs = z.abs.and(x.abs, y.abs)
	1085  		z.neg = false
	1086  		return z
	1087  	}
	1088  
	1089  	// x.neg != y.neg
	1090  	if x.neg {
	1091  		x, y = y, x // & is symmetric
	1092  	}
	1093  
	1094  	// x & (-y) == x & ^(y-1) == x &^ (y-1)
	1095  	y1 := nat(nil).sub(y.abs, natOne)
	1096  	z.abs = z.abs.andNot(x.abs, y1)
	1097  	z.neg = false
	1098  	return z
	1099  }
	1100  
	1101  // AndNot sets z = x &^ y and returns z.
	1102  func (z *Int) AndNot(x, y *Int) *Int {
	1103  	if x.neg == y.neg {
	1104  		if x.neg {
	1105  			// (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
	1106  			x1 := nat(nil).sub(x.abs, natOne)
	1107  			y1 := nat(nil).sub(y.abs, natOne)
	1108  			z.abs = z.abs.andNot(y1, x1)
	1109  			z.neg = false
	1110  			return z
	1111  		}
	1112  
	1113  		// x &^ y == x &^ y
	1114  		z.abs = z.abs.andNot(x.abs, y.abs)
	1115  		z.neg = false
	1116  		return z
	1117  	}
	1118  
	1119  	if x.neg {
	1120  		// (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
	1121  		x1 := nat(nil).sub(x.abs, natOne)
	1122  		z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
	1123  		z.neg = true // z cannot be zero if x is negative and y is positive
	1124  		return z
	1125  	}
	1126  
	1127  	// x &^ (-y) == x &^ ^(y-1) == x & (y-1)
	1128  	y1 := nat(nil).sub(y.abs, natOne)
	1129  	z.abs = z.abs.and(x.abs, y1)
	1130  	z.neg = false
	1131  	return z
	1132  }
	1133  
	1134  // Or sets z = x | y and returns z.
	1135  func (z *Int) Or(x, y *Int) *Int {
	1136  	if x.neg == y.neg {
	1137  		if x.neg {
	1138  			// (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
	1139  			x1 := nat(nil).sub(x.abs, natOne)
	1140  			y1 := nat(nil).sub(y.abs, natOne)
	1141  			z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
	1142  			z.neg = true // z cannot be zero if x and y are negative
	1143  			return z
	1144  		}
	1145  
	1146  		// x | y == x | y
	1147  		z.abs = z.abs.or(x.abs, y.abs)
	1148  		z.neg = false
	1149  		return z
	1150  	}
	1151  
	1152  	// x.neg != y.neg
	1153  	if x.neg {
	1154  		x, y = y, x // | is symmetric
	1155  	}
	1156  
	1157  	// x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
	1158  	y1 := nat(nil).sub(y.abs, natOne)
	1159  	z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
	1160  	z.neg = true // z cannot be zero if one of x or y is negative
	1161  	return z
	1162  }
	1163  
	1164  // Xor sets z = x ^ y and returns z.
	1165  func (z *Int) Xor(x, y *Int) *Int {
	1166  	if x.neg == y.neg {
	1167  		if x.neg {
	1168  			// (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
	1169  			x1 := nat(nil).sub(x.abs, natOne)
	1170  			y1 := nat(nil).sub(y.abs, natOne)
	1171  			z.abs = z.abs.xor(x1, y1)
	1172  			z.neg = false
	1173  			return z
	1174  		}
	1175  
	1176  		// x ^ y == x ^ y
	1177  		z.abs = z.abs.xor(x.abs, y.abs)
	1178  		z.neg = false
	1179  		return z
	1180  	}
	1181  
	1182  	// x.neg != y.neg
	1183  	if x.neg {
	1184  		x, y = y, x // ^ is symmetric
	1185  	}
	1186  
	1187  	// x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
	1188  	y1 := nat(nil).sub(y.abs, natOne)
	1189  	z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
	1190  	z.neg = true // z cannot be zero if only one of x or y is negative
	1191  	return z
	1192  }
	1193  
	1194  // Not sets z = ^x and returns z.
	1195  func (z *Int) Not(x *Int) *Int {
	1196  	if x.neg {
	1197  		// ^(-x) == ^(^(x-1)) == x-1
	1198  		z.abs = z.abs.sub(x.abs, natOne)
	1199  		z.neg = false
	1200  		return z
	1201  	}
	1202  
	1203  	// ^x == -x-1 == -(x+1)
	1204  	z.abs = z.abs.add(x.abs, natOne)
	1205  	z.neg = true // z cannot be zero if x is positive
	1206  	return z
	1207  }
	1208  
	1209  // Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
	1210  // It panics if x is negative.
	1211  func (z *Int) Sqrt(x *Int) *Int {
	1212  	if x.neg {
	1213  		panic("square root of negative number")
	1214  	}
	1215  	z.neg = false
	1216  	z.abs = z.abs.sqrt(x.abs)
	1217  	return z
	1218  }
	1219  

View as plain text