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.
5 // This file implements signed multi-precision integers.
16 // An Int represents a signed multi-precision integer.
17 // The zero value for an Int represents the value 0.
20 abs nat
// absolute value of the integer
23 var intOne
= &Int
{false, natOne
}
31 func (x
*Int
) Sign() int {
41 // SetInt64 sets z to x and returns z.
42 func (z
*Int
) SetInt64(x
int64) *Int
{
48 z
.abs
= z
.abs
.setUint64(uint64(x
))
53 // SetUint64 sets z to x and returns z.
54 func (z
*Int
) SetUint64(x
uint64) *Int
{
55 z
.abs
= z
.abs
.setUint64(x
)
60 // NewInt allocates and returns a new Int set to x.
61 func NewInt(x
int64) *Int
{
62 return new(Int
).SetInt64(x
)
65 // Set sets z to x and returns z.
66 func (z
*Int
) Set(x
*Int
) *Int
{
68 z
.abs
= z
.abs
.set(x
.abs
)
74 // Bits provides raw (unchecked but fast) access to x by returning its
75 // absolute value as a little-endian Word slice. The result and x share
76 // the same underlying array.
77 // Bits is intended to support implementation of missing low-level Int
78 // functionality outside this package; it should be avoided otherwise.
79 func (x
*Int
) Bits() []Word
{
83 // SetBits provides raw (unchecked but fast) access to z by setting its
84 // value to abs, interpreted as a little-endian Word slice, and returning
85 // z. The result and abs share the same underlying array.
86 // SetBits is intended to support implementation of missing low-level Int
87 // functionality outside this package; it should be avoided otherwise.
88 func (z
*Int
) SetBits(abs
[]Word
) *Int
{
89 z
.abs
= nat(abs
).norm()
94 // Abs sets z to |x| (the absolute value of x) and returns z.
95 func (z
*Int
) Abs(x
*Int
) *Int
{
101 // Neg sets z to -x and returns z.
102 func (z
*Int
) Neg(x
*Int
) *Int
{
104 z
.neg
= len(z
.abs
) > 0 && !z
.neg
// 0 has no sign
108 // Add sets z to the sum x+y and returns z.
109 func (z
*Int
) Add(x
, y
*Int
) *Int
{
113 // (-x) + (-y) == -(x + y)
114 z
.abs
= z
.abs
.add(x
.abs
, y
.abs
)
116 // x + (-y) == x - y == -(y - x)
117 // (-x) + y == y - x == -(x - y)
118 if x
.abs
.cmp(y
.abs
) >= 0 {
119 z
.abs
= z
.abs
.sub(x
.abs
, y
.abs
)
122 z
.abs
= z
.abs
.sub(y
.abs
, x
.abs
)
125 z
.neg
= len(z
.abs
) > 0 && neg
// 0 has no sign
129 // Sub sets z to the difference x-y and returns z.
130 func (z
*Int
) Sub(x
, y
*Int
) *Int
{
134 // (-x) - y == -(x + y)
135 z
.abs
= z
.abs
.add(x
.abs
, y
.abs
)
137 // x - y == x - y == -(y - x)
138 // (-x) - (-y) == y - x == -(x - y)
139 if x
.abs
.cmp(y
.abs
) >= 0 {
140 z
.abs
= z
.abs
.sub(x
.abs
, y
.abs
)
143 z
.abs
= z
.abs
.sub(y
.abs
, x
.abs
)
146 z
.neg
= len(z
.abs
) > 0 && neg
// 0 has no sign
150 // Mul sets z to the product x*y and returns z.
151 func (z
*Int
) Mul(x
, y
*Int
) *Int
{
153 // x * (-y) == -(x * y)
154 // (-x) * y == -(x * y)
155 // (-x) * (-y) == x * y
156 z
.abs
= z
.abs
.mul(x
.abs
, y
.abs
)
157 z
.neg
= len(z
.abs
) > 0 && x
.neg
!= y
.neg
// 0 has no sign
161 // MulRange sets z to the product of all integers
162 // in the range [a, b] inclusively and returns z.
163 // If a > b (empty range), the result is 1.
164 func (z
*Int
) MulRange(a
, b
int64) *Int
{
167 return z
.SetInt64(1) // empty range
168 case a
<= 0 && b
>= 0:
169 return z
.SetInt64(0) // range includes 0
171 // a <= b && (b < 0 || a > 0)
179 z
.abs
= z
.abs
.mulRange(uint64(a
), uint64(b
))
184 // Binomial sets z to the binomial coefficient of (n, k) and returns z.
185 func (z
*Int
) Binomial(n
, k
int64) *Int
{
186 // reduce the number of multiplications by reducing k
187 if n
/2 < k
&& k
<= n
{
188 k
= n
- k
// Binomial(n, k) == Binomial(n, n-k)
196 // Quo sets z to the quotient x/y for y != 0 and returns z.
197 // If y == 0, a division-by-zero run-time panic occurs.
198 // Quo implements truncated division (like Go); see QuoRem for more details.
199 func (z
*Int
) Quo(x
, y
*Int
) *Int
{
200 z
.abs
, _
= z
.abs
.div(nil, x
.abs
, y
.abs
)
201 z
.neg
= len(z
.abs
) > 0 && x
.neg
!= y
.neg
// 0 has no sign
205 // Rem sets z to the remainder x%y for y != 0 and returns z.
206 // If y == 0, a division-by-zero run-time panic occurs.
207 // Rem implements truncated modulus (like Go); see QuoRem for more details.
208 func (z
*Int
) Rem(x
, y
*Int
) *Int
{
209 _
, z
.abs
= nat(nil).div(z
.abs
, x
.abs
, y
.abs
)
210 z
.neg
= len(z
.abs
) > 0 && x
.neg
// 0 has no sign
214 // QuoRem sets z to the quotient x/y and r to the remainder x%y
215 // and returns the pair (z, r) for y != 0.
216 // If y == 0, a division-by-zero run-time panic occurs.
218 // QuoRem implements T-division and modulus (like Go):
220 // q = x/y with the result truncated to zero
223 // (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
224 // See DivMod for Euclidean division and modulus (unlike Go).
226 func (z
*Int
) QuoRem(x
, y
, r
*Int
) (*Int
, *Int
) {
227 z
.abs
, r
.abs
= z
.abs
.div(r
.abs
, x
.abs
, y
.abs
)
228 z
.neg
, r
.neg
= len(z
.abs
) > 0 && x
.neg
!= y
.neg
, len(r
.abs
) > 0 && x
.neg
// 0 has no sign
232 // Div sets z to the quotient x/y for y != 0 and returns z.
233 // If y == 0, a division-by-zero run-time panic occurs.
234 // Div implements Euclidean division (unlike Go); see DivMod for more details.
235 func (z
*Int
) Div(x
, y
*Int
) *Int
{
236 y_neg
:= y
.neg
// z may be an alias for y
249 // Mod sets z to the modulus x%y for y != 0 and returns z.
250 // If y == 0, a division-by-zero run-time panic occurs.
251 // Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
252 func (z
*Int
) Mod(x
, y
*Int
) *Int
{
254 if z
== y ||
alias(z
.abs
, y
.abs
) {
269 // DivMod sets z to the quotient x div y and m to the modulus x mod y
270 // and returns the pair (z, m) for y != 0.
271 // If y == 0, a division-by-zero run-time panic occurs.
273 // DivMod implements Euclidean division and modulus (unlike Go):
275 // q = x div y such that
276 // m = x - y*q with 0 <= m < |y|
278 // (See Raymond T. Boute, ``The Euclidean definition of the functions
279 // div and mod''. ACM Transactions on Programming Languages and
280 // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
282 // See QuoRem for T-division and modulus (like Go).
284 func (z
*Int
) DivMod(x
, y
, m
*Int
) (*Int
, *Int
) {
286 if z
== y ||
alias(z
.abs
, y
.abs
) {
302 // Cmp compares x and y and returns:
308 func (x
*Int
) Cmp(y
*Int
) (r
int) {
309 // x cmp y == x cmp y
312 // (-x) cmp (-y) == -(x cmp y)
327 // low32 returns the least significant 32 bits of x.
328 func low32(x nat
) uint32 {
335 // low64 returns the least significant 64 bits of x.
336 func low64(x nat
) uint64 {
341 if _W
== 32 && len(x
) > 1 {
342 return uint64(x
[1])<<32 | v
347 // Int64 returns the int64 representation of x.
348 // If x cannot be represented in an int64, the result is undefined.
349 func (x
*Int
) Int64() int64 {
350 v
:= int64(low64(x
.abs
))
357 // Uint64 returns the uint64 representation of x.
358 // If x cannot be represented in a uint64, the result is undefined.
359 func (x
*Int
) Uint64() uint64 {
363 // IsInt64 reports whether x can be represented as an int64.
364 func (x
*Int
) IsInt64() bool {
365 if len(x
.abs
) <= 64/_W
{
366 w
:= int64(low64(x
.abs
))
367 return w
>= 0 || x
.neg
&& w
== -w
372 // IsUint64 reports whether x can be represented as a uint64.
373 func (x
*Int
) IsUint64() bool {
374 return !x
.neg
&& len(x
.abs
) <= 64/_W
377 // SetString sets z to the value of s, interpreted in the given base,
378 // and returns z and a boolean indicating success. The entire string
379 // (not just a prefix) must be valid for success. If SetString fails,
380 // the value of z is undefined but the returned value is nil.
382 // The base argument must be 0 or a value between 2 and MaxBase. If the base
383 // is 0, the string prefix determines the actual conversion base. A prefix of
384 // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
385 // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
387 func (z
*Int
) SetString(s
string, base
int) (*Int
, bool) {
388 r
:= strings
.NewReader(s
)
389 if _
, _
, err
:= z
.scan(r
, base
); err
!= nil {
392 // entire string must have been consumed
393 if _
, err
:= r
.ReadByte(); err
!= io
.EOF
{
396 return z
, true // err == io.EOF => scan consumed all of s
399 // SetBytes interprets buf as the bytes of a big-endian unsigned
400 // integer, sets z to that value, and returns z.
401 func (z
*Int
) SetBytes(buf
[]byte) *Int
{
402 z
.abs
= z
.abs
.setBytes(buf
)
407 // Bytes returns the absolute value of x as a big-endian byte slice.
408 func (x
*Int
) Bytes() []byte {
409 buf
:= make([]byte, len(x
.abs
)*_S
)
410 return buf
[x
.abs
.bytes(buf
):]
413 // BitLen returns the length of the absolute value of x in bits.
414 // The bit length of 0 is 0.
415 func (x
*Int
) BitLen() int {
416 return x
.abs
.bitLen()
419 // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
420 // If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y.
422 // Modular exponentation of inputs of a particular size is not a
423 // cryptographically constant-time operation.
424 func (z
*Int
) Exp(x
, y
, m
*Int
) *Int
{
425 // See Knuth, volume 2, section 4.6.3.
434 mWords
= m
.abs
// m.abs may be nil for m == 0
437 z
.abs
= z
.abs
.expNN(x
.abs
, yWords
, mWords
)
438 z
.neg
= len(z
.abs
) > 0 && x
.neg
&& len(yWords
) > 0 && yWords
[0]&1 == 1 // 0 has no sign
439 if z
.neg
&& len(mWords
) > 0 {
440 // make modulus result positive
441 z
.abs
= z
.abs
.sub(mWords
, z
.abs
) // z == x**y mod |m| && 0 <= z < |m|
448 // GCD sets z to the greatest common divisor of a and b, which both must
449 // be > 0, and returns z.
450 // If x and y are not nil, GCD sets x and y such that z = a*x + b*y.
451 // If either a or b is <= 0, GCD sets z = x = y = 0.
452 func (z
*Int
) GCD(x
, y
, a
, b
*Int
) *Int
{
453 if a
.Sign() <= 0 || b
.Sign() <= 0 {
463 if x
== nil && y
== nil {
464 return z
.binaryGCD(a
, b
)
471 Y
:= new(Int
).SetInt64(1)
473 lastX
:= new(Int
).SetInt64(1)
481 q
, r
= q
.QuoRem(A
, B
, r
)
510 // binaryGCD sets z to the greatest common divisor of a and b, which both must
511 // be > 0, and returns z.
512 // See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B.
513 func (z
*Int
) binaryGCD(a
, b
*Int
) *Int
{
517 // use one Euclidean iteration to ensure that u and v are approx. the same size
519 case len(a
.abs
) > len(b
.abs
):
520 // must set v before u since u may be alias for a or b (was issue #11284)
523 case len(a
.abs
) < len(b
.abs
):
530 // a, b must not be used anymore (may be aliases with u)
538 // determine largest k such that u = u' << k, v = v' << k
539 k
:= u
.abs
.trailingZeroBits()
540 if vk
:= v
.abs
.trailingZeroBits(); vk
< k
{
546 // determine t (we know that u > 0)
557 t
.Rsh(t
, t
.abs
.trailingZeroBits())
560 v
.neg
= len(v
.abs
) > 0 && !v
.neg
// 0 has no sign
570 // Rand sets z to a pseudo-random number in [0, n) and returns z.
571 func (z
*Int
) Rand(rnd
*rand
.Rand
, n
*Int
) *Int
{
573 if n
.neg ||
len(n
.abs
) == 0 {
577 z
.abs
= z
.abs
.random(rnd
, n
.abs
, n
.abs
.bitLen())
581 // ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
582 // and returns z. If g and n are not relatively prime, the result is undefined.
583 func (z
*Int
) ModInverse(g
, n
*Int
) *Int
{
585 // GCD expects parameters a and b to be > 0.
591 // x and y are such that g*x + n*y = d. Since g and n are
592 // relatively prime, d = 1. Taking that modulo n results in
593 // g*x = 1, therefore x is the inverse element.
600 // Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
601 // The y argument must be an odd integer.
602 func Jacobi(x
, y
*Int
) int {
603 if len(y
.abs
) == 0 || y
.abs
[0]&1 == 0 {
604 panic(fmt
.Sprintf("big: invalid 2nd argument to Int.Jacobi: need odd integer but got %s", y
))
607 // We use the formulation described in chapter 2, section 2.4,
608 // "The Yacas Book of Algorithms":
609 // http://yacas.sourceforge.net/Algo.book.pdf
624 if b
.Cmp(intOne
) == 0 {
636 // handle factors of 2 in 'a'
637 s
:= a
.abs
.trailingZeroBits()
639 bmod8
:= b
.abs
[0] & 7
640 if bmod8
== 3 || bmod8
== 5 {
644 c
.Rsh(&a
, s
) // a = 2^s*c
646 // swap numerator and denominator
647 if b
.abs
[0]&3 == 3 && c
.abs
[0]&3 == 3 {
655 // modSqrt3Mod4 uses the identity
656 // (a^((p+1)/4))^2 mod p
659 // to calculate the square root of any quadratic residue mod p quickly for 3
661 func (z
*Int
) modSqrt3Mod4Prime(x
, p
*Int
) *Int
{
663 z
.Add(z
, intOne
) // z = p + 1
664 z
.Rsh(z
, 2) // z = (p + 1) / 4
665 z
.Exp(x
, z
, p
) // z = x^z mod p
669 // modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square
670 // root of a quadratic residue modulo any prime.
671 func (z
*Int
) modSqrtTonelliShanks(x
, p
*Int
) *Int
{
672 // Break p-1 into s*2^e such that s is odd.
675 e
:= s
.abs
.trailingZeroBits()
678 // find some non-square n
681 for Jacobi(&n
, p
) != -1 {
685 // Core of the Tonelli-Shanks algorithm. Follows the description in
686 // section 6 of "Square roots from 1; 24, 51, 10 to Dan Shanks" by Ezra
688 // https://www.maa.org/sites/default/files/pdf/upload_library/22/Polya/07468342.di020786.02p0470a.pdf
692 y
.Exp(x
, &y
, p
) // y = x^((s+1)/2)
693 b
.Exp(x
, &s
, p
) // b = x^s
694 g
.Exp(&n
, &s
, p
) // g = n^s
697 // find the least m such that ord_p(b) = 2^m
700 for t
.Cmp(intOne
) != 0 {
701 t
.Mul(&t
, &t
).Mod(&t
, p
)
709 t
.SetInt64(0).SetBit(&t
, int(r
-m
-1), 1).Exp(&g
, &t
, p
)
710 // t = g^(2^(r-m-1)) mod p
711 g
.Mul(&t
, &t
).Mod(&g
, p
) // g = g^(2^(r-m)) mod p
712 y
.Mul(&y
, &t
).Mod(&y
, p
)
713 b
.Mul(&b
, &g
).Mod(&b
, p
)
718 // ModSqrt sets z to a square root of x mod p if such a square root exists, and
719 // returns z. The modulus p must be an odd prime. If x is not a square mod p,
720 // ModSqrt leaves z unchanged and returns nil. This function panics if p is
721 // not an odd integer.
722 func (z
*Int
) ModSqrt(x
, p
*Int
) *Int
{
723 switch Jacobi(x
, p
) {
725 return nil // x is not a square mod p
727 return z
.SetInt64(0) // sqrt(0) mod p = 0
731 if x
.neg || x
.Cmp(p
) >= 0 { // ensure 0 <= x < p
732 x
= new(Int
).Mod(x
, p
)
735 // Check whether p is 3 mod 4, and if so, use the faster algorithm.
736 if len(p
.abs
) > 0 && p
.abs
[0]%4
== 3 {
737 return z
.modSqrt3Mod4Prime(x
, p
)
739 // Otherwise, use Tonelli-Shanks.
740 return z
.modSqrtTonelliShanks(x
, p
)
743 // Lsh sets z = x << n and returns z.
744 func (z
*Int
) Lsh(x
*Int
, n
uint) *Int
{
745 z
.abs
= z
.abs
.shl(x
.abs
, n
)
750 // Rsh sets z = x >> n and returns z.
751 func (z
*Int
) Rsh(x
*Int
, n
uint) *Int
{
753 // (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
754 t
:= z
.abs
.sub(x
.abs
, natOne
) // no underflow because |x| > 0
756 z
.abs
= t
.add(t
, natOne
)
757 z
.neg
= true // z cannot be zero if x is negative
761 z
.abs
= z
.abs
.shr(x
.abs
, n
)
766 // Bit returns the value of the i'th bit of x. That is, it
767 // returns (x>>i)&1. The bit index i must be >= 0.
768 func (x
*Int
) Bit(i
int) uint {
770 // optimization for common case: odd/even test of x
772 return uint(x
.abs
[0] & 1) // bit 0 is same for -x
777 panic("negative bit index")
780 t
:= nat(nil).sub(x
.abs
, natOne
)
781 return t
.bit(uint(i
)) ^ 1
784 return x
.abs
.bit(uint(i
))
787 // SetBit sets z to x, with x's i'th bit set to b (0 or 1).
788 // That is, if b is 1 SetBit sets z = x | (1 << i);
789 // if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1,
790 // SetBit will panic.
791 func (z
*Int
) SetBit(x
*Int
, i
int, b
uint) *Int
{
793 panic("negative bit index")
796 t
:= z
.abs
.sub(x
.abs
, natOne
)
797 t
= t
.setBit(t
, uint(i
), b
^1)
798 z
.abs
= t
.add(t
, natOne
)
799 z
.neg
= len(z
.abs
) > 0
802 z
.abs
= z
.abs
.setBit(x
.abs
, uint(i
), b
)
807 // And sets z = x & y and returns z.
808 func (z
*Int
) And(x
, y
*Int
) *Int
{
811 // (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
812 x1
:= nat(nil).sub(x
.abs
, natOne
)
813 y1
:= nat(nil).sub(y
.abs
, natOne
)
814 z
.abs
= z
.abs
.add(z
.abs
.or(x1
, y1
), natOne
)
815 z
.neg
= true // z cannot be zero if x and y are negative
820 z
.abs
= z
.abs
.and(x
.abs
, y
.abs
)
827 x
, y
= y
, x
// & is symmetric
830 // x & (-y) == x & ^(y-1) == x &^ (y-1)
831 y1
:= nat(nil).sub(y
.abs
, natOne
)
832 z
.abs
= z
.abs
.andNot(x
.abs
, y1
)
837 // AndNot sets z = x &^ y and returns z.
838 func (z
*Int
) AndNot(x
, y
*Int
) *Int
{
841 // (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
842 x1
:= nat(nil).sub(x
.abs
, natOne
)
843 y1
:= nat(nil).sub(y
.abs
, natOne
)
844 z
.abs
= z
.abs
.andNot(y1
, x1
)
850 z
.abs
= z
.abs
.andNot(x
.abs
, y
.abs
)
856 // (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
857 x1
:= nat(nil).sub(x
.abs
, natOne
)
858 z
.abs
= z
.abs
.add(z
.abs
.or(x1
, y
.abs
), natOne
)
859 z
.neg
= true // z cannot be zero if x is negative and y is positive
863 // x &^ (-y) == x &^ ^(y-1) == x & (y-1)
864 y1
:= nat(nil).sub(y
.abs
, natOne
)
865 z
.abs
= z
.abs
.and(x
.abs
, y1
)
870 // Or sets z = x | y and returns z.
871 func (z
*Int
) Or(x
, y
*Int
) *Int
{
874 // (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
875 x1
:= nat(nil).sub(x
.abs
, natOne
)
876 y1
:= nat(nil).sub(y
.abs
, natOne
)
877 z
.abs
= z
.abs
.add(z
.abs
.and(x1
, y1
), natOne
)
878 z
.neg
= true // z cannot be zero if x and y are negative
883 z
.abs
= z
.abs
.or(x
.abs
, y
.abs
)
890 x
, y
= y
, x
// | is symmetric
893 // x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
894 y1
:= nat(nil).sub(y
.abs
, natOne
)
895 z
.abs
= z
.abs
.add(z
.abs
.andNot(y1
, x
.abs
), natOne
)
896 z
.neg
= true // z cannot be zero if one of x or y is negative
900 // Xor sets z = x ^ y and returns z.
901 func (z
*Int
) Xor(x
, y
*Int
) *Int
{
904 // (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
905 x1
:= nat(nil).sub(x
.abs
, natOne
)
906 y1
:= nat(nil).sub(y
.abs
, natOne
)
907 z
.abs
= z
.abs
.xor(x1
, y1
)
913 z
.abs
= z
.abs
.xor(x
.abs
, y
.abs
)
920 x
, y
= y
, x
// ^ is symmetric
923 // x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
924 y1
:= nat(nil).sub(y
.abs
, natOne
)
925 z
.abs
= z
.abs
.add(z
.abs
.xor(x
.abs
, y1
), natOne
)
926 z
.neg
= true // z cannot be zero if only one of x or y is negative
930 // Not sets z = ^x and returns z.
931 func (z
*Int
) Not(x
*Int
) *Int
{
933 // ^(-x) == ^(^(x-1)) == x-1
934 z
.abs
= z
.abs
.sub(x
.abs
, natOne
)
939 // ^x == -x-1 == -(x+1)
940 z
.abs
= z
.abs
.add(x
.abs
, natOne
)
941 z
.neg
= true // z cannot be zero if x is positive
945 // Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
946 // It panics if x is negative.
947 func (z
*Int
) Sqrt(x
*Int
) *Int
{
949 panic("square root of negative number")
952 z
.abs
= z
.abs
.sqrt(x
.abs
)