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.
17 // An Int represents a signed multi-precision integer.
18 // The zero value for an Int represents the value 0.
21 abs nat // absolute value of the integer
24 var intOne = &Int{false, natOne}
32 func (x *Int) Sign() int {
42 // SetInt64 sets z to x and returns z.
43 func (z *Int) SetInt64(x int64) *Int {
49 z.abs = z.abs.setUint64(uint64(x))
54 // NewInt allocates and returns a new Int set to x.
55 func NewInt(x int64) *Int {
56 return new(Int).SetInt64(x)
59 // Set sets z to x and returns z.
60 func (z *Int) Set(x *Int) *Int {
62 z.abs = z.abs.set(x.abs)
68 // Abs sets z to |x| (the absolute value of x) and returns z.
69 func (z *Int) Abs(x *Int) *Int {
75 // Neg sets z to -x and returns z.
76 func (z *Int) Neg(x *Int) *Int {
78 z.neg = len(z.abs) > 0 && !z.neg // 0 has no sign
82 // Add sets z to the sum x+y and returns z.
83 func (z *Int) Add(x, y *Int) *Int {
87 // (-x) + (-y) == -(x + y)
88 z.abs = z.abs.add(x.abs, y.abs)
90 // x + (-y) == x - y == -(y - x)
91 // (-x) + y == y - x == -(x - y)
92 if x.abs.cmp(y.abs) >= 0 {
93 z.abs = z.abs.sub(x.abs, y.abs)
96 z.abs = z.abs.sub(y.abs, x.abs)
99 z.neg = len(z.abs) > 0 && neg // 0 has no sign
103 // Sub sets z to the difference x-y and returns z.
104 func (z *Int) Sub(x, y *Int) *Int {
108 // (-x) - y == -(x + y)
109 z.abs = z.abs.add(x.abs, y.abs)
111 // x - y == x - y == -(y - x)
112 // (-x) - (-y) == y - x == -(x - y)
113 if x.abs.cmp(y.abs) >= 0 {
114 z.abs = z.abs.sub(x.abs, y.abs)
117 z.abs = z.abs.sub(y.abs, x.abs)
120 z.neg = len(z.abs) > 0 && neg // 0 has no sign
124 // Mul sets z to the product x*y and returns z.
125 func (z *Int) Mul(x, y *Int) *Int {
127 // x * (-y) == -(x * y)
128 // (-x) * y == -(x * y)
129 // (-x) * (-y) == x * y
130 z.abs = z.abs.mul(x.abs, y.abs)
131 z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
135 // MulRange sets z to the product of all integers
136 // in the range [a, b] inclusively and returns z.
137 // If a > b (empty range), the result is 1.
138 func (z *Int) MulRange(a, b int64) *Int {
141 return z.SetInt64(1) // empty range
142 case a <= 0 && b >= 0:
143 return z.SetInt64(0) // range includes 0
145 // a <= b && (b < 0 || a > 0)
153 z.abs = z.abs.mulRange(uint64(a), uint64(b))
158 // Binomial sets z to the binomial coefficient of (n, k) and returns z.
159 func (z *Int) Binomial(n, k int64) *Int {
166 // Quo sets z to the quotient x/y for y != 0 and returns z.
167 // If y == 0, a division-by-zero run-time panic occurs.
168 // Quo implements truncated division (like Go); see QuoRem for more details.
169 func (z *Int) Quo(x, y *Int) *Int {
170 z.abs, _ = z.abs.div(nil, x.abs, y.abs)
171 z.neg = len(z.abs) > 0 && x.neg != y.neg // 0 has no sign
175 // Rem sets z to the remainder x%y for y != 0 and returns z.
176 // If y == 0, a division-by-zero run-time panic occurs.
177 // Rem implements truncated modulus (like Go); see QuoRem for more details.
178 func (z *Int) Rem(x, y *Int) *Int {
179 _, z.abs = nat{}.div(z.abs, x.abs, y.abs)
180 z.neg = len(z.abs) > 0 && x.neg // 0 has no sign
184 // QuoRem sets z to the quotient x/y and r to the remainder x%y
185 // and returns the pair (z, r) for y != 0.
186 // If y == 0, a division-by-zero run-time panic occurs.
188 // QuoRem implements T-division and modulus (like Go):
190 // q = x/y with the result truncated to zero
193 // (See Daan Leijen, ``Division and Modulus for Computer Scientists''.)
195 func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
196 z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
197 z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg // 0 has no sign
201 // Div sets z to the quotient x/y for y != 0 and returns z.
202 // If y == 0, a division-by-zero run-time panic occurs.
203 // Div implements Euclidean division (unlike Go); see DivMod for more details.
204 func (z *Int) Div(x, y *Int) *Int {
205 y_neg := y.neg // z may be an alias for y
218 // Mod sets z to the modulus x%y for y != 0 and returns z.
219 // If y == 0, a division-by-zero run-time panic occurs.
220 // Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
221 func (z *Int) Mod(x, y *Int) *Int {
223 if z == y || alias(z.abs, y.abs) {
238 // DivMod sets z to the quotient x div y and m to the modulus x mod y
239 // and returns the pair (z, m) for y != 0.
240 // If y == 0, a division-by-zero run-time panic occurs.
242 // DivMod implements Euclidean division and modulus (unlike Go):
244 // q = x div y such that
245 // m = x - y*q with 0 <= m < |q|
247 // (See Raymond T. Boute, ``The Euclidean definition of the functions
248 // div and mod''. ACM Transactions on Programming Languages and
249 // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
252 func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
254 if z == y || alias(z.abs, y.abs) {
270 // Cmp compares x and y and returns:
276 func (x *Int) Cmp(y *Int) (r int) {
277 // x cmp y == x cmp y
280 // (-x) cmp (-y) == -(x cmp y)
295 func (x *Int) String() string {
300 return "-" + x.abs.decimalString()
302 return x.abs.decimalString()
305 func charset(ch rune) string {
308 return lowercaseDigits[0:2]
310 return lowercaseDigits[0:8]
312 return lowercaseDigits[0:10]
314 return lowercaseDigits[0:16]
316 return uppercaseDigits[0:16]
318 return "" // unknown format
321 // write count copies of text to s
322 func writeMultiple(s fmt.State, text string, count int) {
325 for ; count > 0; count-- {
331 // Format is a support routine for fmt.Formatter. It accepts
332 // the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x'
333 // (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
334 // Also supported are the full suite of package fmt's format
335 // verbs for integral types, including '+', '-', and ' '
336 // for sign control, '#' for leading zero in octal and for
337 // hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X"
338 // respectively, specification of minimum digits precision,
339 // output field width, space or zero padding, and left or
340 // right justification.
342 func (x *Int) Format(s fmt.State, ch rune) {
349 fmt.Fprintf(s, "%%!%c(big.Int=%s)", ch, x.String())
352 fmt.Fprint(s, "<nil>")
356 // determine sign character
361 case s.Flag('+'): // supersedes ' ' when both specified
367 // determine prefix characters for indicating output base
373 case 'x': // hexadecimal
380 // determine digits with base set by len(cs) and digit characters from cs
381 digits := x.abs.string(cs)
383 // number of characters for the three classes of number padding
384 var left int // space characters to left of digits for right justification ("%8d")
385 var zeroes int // zero characters (actually cs[0]) as left-most digits ("%.8d")
386 var right int // space characters to right of digits for left justification ("%-8d")
388 // determine number padding from precision: the least number of digits to output
389 precision, precisionSet := s.Precision()
392 case len(digits) < precision:
393 zeroes = precision - len(digits) // count of zero padding
394 case digits == "0" && precision == 0:
395 return // print nothing if zero value (x == 0) and zero precision ("." or ".0")
399 // determine field pad from width: the least number of characters to output
400 length := len(sign) + len(prefix) + zeroes + len(digits)
401 if width, widthSet := s.Width(); widthSet && length < width { // pad as specified
402 switch d := width - length; {
404 // pad on the right with spaces; supersedes '0' when both specified
406 case s.Flag('0') && !precisionSet:
407 // pad with zeroes unless precision also specified
410 // pad on the left with spaces
415 // print number as [left pad][sign][prefix][zero pad][digits][right pad]
416 writeMultiple(s, " ", left)
417 writeMultiple(s, sign, 1)
418 writeMultiple(s, prefix, 1)
419 writeMultiple(s, "0", zeroes)
420 writeMultiple(s, digits, 1)
421 writeMultiple(s, " ", right)
424 // scan sets z to the integer value corresponding to the longest possible prefix
425 // read from r representing a signed integer number in a given conversion base.
426 // It returns z, the actual conversion base used, and an error, if any. In the
427 // error case, the value of z is undefined but the returned value is nil. The
428 // syntax follows the syntax of integer literals in Go.
430 // The base argument must be 0 or a value from 2 through MaxBase. If the base
431 // is 0, the string prefix determines the actual conversion base. A prefix of
432 // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
433 // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
435 func (z *Int) scan(r io.RuneScanner, base int) (*Int, int, error) {
437 ch, _, err := r.ReadRune()
445 case '+': // nothing to do
450 // determine mantissa
451 z.abs, base, err = z.abs.scan(r, base)
453 return nil, base, err
455 z.neg = len(z.abs) > 0 && neg // 0 has no sign
460 // Scan is a support routine for fmt.Scanner; it sets z to the value of
461 // the scanned number. It accepts the formats 'b' (binary), 'o' (octal),
462 // 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal).
463 func (z *Int) Scan(s fmt.ScanState, ch rune) error {
464 s.SkipSpace() // skip leading space characters
476 // let scan determine the base
478 return errors.New("Int.Scan: invalid verb")
480 _, _, err := z.scan(s, base)
484 // Int64 returns the int64 representation of x.
485 // If x cannot be represented in an int64, the result is undefined.
486 func (x *Int) Int64() int64 {
491 if _W == 32 && len(x.abs) > 1 {
492 v |= int64(x.abs[1]) << 32
500 // SetString sets z to the value of s, interpreted in the given base,
501 // and returns z and a boolean indicating success. If SetString fails,
502 // the value of z is undefined but the returned value is nil.
504 // The base argument must be 0 or a value from 2 through MaxBase. If the base
505 // is 0, the string prefix determines the actual conversion base. A prefix of
506 // ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a
507 // ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10.
509 func (z *Int) SetString(s string, base int) (*Int, bool) {
510 r := strings.NewReader(s)
511 _, _, err := z.scan(r, base)
515 _, _, err = r.ReadRune()
519 return z, true // err == os.EOF => scan consumed all of s
522 // SetBytes interprets buf as the bytes of a big-endian unsigned
523 // integer, sets z to that value, and returns z.
524 func (z *Int) SetBytes(buf []byte) *Int {
525 z.abs = z.abs.setBytes(buf)
530 // Bytes returns the absolute value of z as a big-endian byte slice.
531 func (z *Int) Bytes() []byte {
532 buf := make([]byte, len(z.abs)*_S)
533 return buf[z.abs.bytes(buf):]
536 // BitLen returns the length of the absolute value of z in bits.
537 // The bit length of 0 is 0.
538 func (z *Int) BitLen() int {
539 return z.abs.bitLen()
542 // Exp sets z = x**y mod m. If m is nil, z = x**y.
543 // See Knuth, volume 2, section 4.6.3.
544 func (z *Int) Exp(x, y, m *Int) *Int {
545 if y.neg || len(y.abs) == 0 {
557 z.abs = z.abs.expNN(x.abs, y.abs, mWords)
558 z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 // 0 has no sign
562 // GcdInt sets d to the greatest common divisor of a and b, which must be
564 // If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
565 // If either a or b is not positive, GcdInt sets d = x = y = 0.
566 func GcdInt(d, x, y, a, b *Int) {
582 Y := new(Int).SetInt64(1)
584 lastX := new(Int).SetInt64(1)
592 q, r = q.QuoRem(A, B, r)
620 // ProbablyPrime performs n Miller-Rabin tests to check whether z is prime.
621 // If it returns true, z is prime with probability 1 - 1/4^n.
622 // If it returns false, z is not prime.
623 func ProbablyPrime(z *Int, n int) bool {
624 return !z.neg && z.abs.probablyPrime(n)
627 // Rand sets z to a pseudo-random number in [0, n) and returns z.
628 func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
630 if n.neg == true || len(n.abs) == 0 {
634 z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
638 // ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where
639 // p is a prime) and returns z.
640 func (z *Int) ModInverse(g, p *Int) *Int {
642 GcdInt(&d, z, nil, g, p)
643 // x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking
644 // that modulo p results in g*x = 1, therefore x is the inverse element.
651 // Lsh sets z = x << n and returns z.
652 func (z *Int) Lsh(x *Int, n uint) *Int {
653 z.abs = z.abs.shl(x.abs, n)
658 // Rsh sets z = x >> n and returns z.
659 func (z *Int) Rsh(x *Int, n uint) *Int {
661 // (-x) >> s == ^(x-1) >> s == ^((x-1) >> s) == -(((x-1) >> s) + 1)
662 t := z.abs.sub(x.abs, natOne) // no underflow because |x| > 0
664 z.abs = t.add(t, natOne)
665 z.neg = true // z cannot be zero if x is negative
669 z.abs = z.abs.shr(x.abs, n)
674 // Bit returns the value of the i'th bit of z. That is, it
675 // returns (z>>i)&1. The bit index i must be >= 0.
676 func (z *Int) Bit(i int) uint {
678 panic("negative bit index")
681 t := nat{}.sub(z.abs, natOne)
682 return t.bit(uint(i)) ^ 1
685 return z.abs.bit(uint(i))
688 // SetBit sets the i'th bit of z to bit and returns z.
689 // That is, if bit is 1 SetBit sets z = x | (1 << i);
690 // if bit is 0 it sets z = x &^ (1 << i). If bit is not 0 or 1,
691 // SetBit will panic.
692 func (z *Int) SetBit(x *Int, i int, b uint) *Int {
694 panic("negative bit index")
697 t := z.abs.sub(x.abs, natOne)
698 t = t.setBit(t, uint(i), b^1)
699 z.abs = t.add(t, natOne)
700 z.neg = len(z.abs) > 0
703 z.abs = z.abs.setBit(x.abs, uint(i), b)
708 // And sets z = x & y and returns z.
709 func (z *Int) And(x, y *Int) *Int {
712 // (-x) & (-y) == ^(x-1) & ^(y-1) == ^((x-1) | (y-1)) == -(((x-1) | (y-1)) + 1)
713 x1 := nat{}.sub(x.abs, natOne)
714 y1 := nat{}.sub(y.abs, natOne)
715 z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
716 z.neg = true // z cannot be zero if x and y are negative
721 z.abs = z.abs.and(x.abs, y.abs)
728 x, y = y, x // & is symmetric
731 // x & (-y) == x & ^(y-1) == x &^ (y-1)
732 y1 := nat{}.sub(y.abs, natOne)
733 z.abs = z.abs.andNot(x.abs, y1)
738 // AndNot sets z = x &^ y and returns z.
739 func (z *Int) AndNot(x, y *Int) *Int {
742 // (-x) &^ (-y) == ^(x-1) &^ ^(y-1) == ^(x-1) & (y-1) == (y-1) &^ (x-1)
743 x1 := nat{}.sub(x.abs, natOne)
744 y1 := nat{}.sub(y.abs, natOne)
745 z.abs = z.abs.andNot(y1, x1)
751 z.abs = z.abs.andNot(x.abs, y.abs)
757 // (-x) &^ y == ^(x-1) &^ y == ^(x-1) & ^y == ^((x-1) | y) == -(((x-1) | y) + 1)
758 x1 := nat{}.sub(x.abs, natOne)
759 z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
760 z.neg = true // z cannot be zero if x is negative and y is positive
764 // x &^ (-y) == x &^ ^(y-1) == x & (y-1)
765 y1 := nat{}.add(y.abs, natOne)
766 z.abs = z.abs.and(x.abs, y1)
771 // Or sets z = x | y and returns z.
772 func (z *Int) Or(x, y *Int) *Int {
775 // (-x) | (-y) == ^(x-1) | ^(y-1) == ^((x-1) & (y-1)) == -(((x-1) & (y-1)) + 1)
776 x1 := nat{}.sub(x.abs, natOne)
777 y1 := nat{}.sub(y.abs, natOne)
778 z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
779 z.neg = true // z cannot be zero if x and y are negative
784 z.abs = z.abs.or(x.abs, y.abs)
791 x, y = y, x // | is symmetric
794 // x | (-y) == x | ^(y-1) == ^((y-1) &^ x) == -(^((y-1) &^ x) + 1)
795 y1 := nat{}.sub(y.abs, natOne)
796 z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
797 z.neg = true // z cannot be zero if one of x or y is negative
801 // Xor sets z = x ^ y and returns z.
802 func (z *Int) Xor(x, y *Int) *Int {
805 // (-x) ^ (-y) == ^(x-1) ^ ^(y-1) == (x-1) ^ (y-1)
806 x1 := nat{}.sub(x.abs, natOne)
807 y1 := nat{}.sub(y.abs, natOne)
808 z.abs = z.abs.xor(x1, y1)
814 z.abs = z.abs.xor(x.abs, y.abs)
821 x, y = y, x // ^ is symmetric
824 // x ^ (-y) == x ^ ^(y-1) == ^(x ^ (y-1)) == -((x ^ (y-1)) + 1)
825 y1 := nat{}.sub(y.abs, natOne)
826 z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
827 z.neg = true // z cannot be zero if only one of x or y is negative
831 // Not sets z = ^x and returns z.
832 func (z *Int) Not(x *Int) *Int {
834 // ^(-x) == ^(^(x-1)) == x-1
835 z.abs = z.abs.sub(x.abs, natOne)
840 // ^x == -x-1 == -(x+1)
841 z.abs = z.abs.add(x.abs, natOne)
842 z.neg = true // z cannot be zero if x is positive
846 // Gob codec version. Permits backward-compatible changes to the encoding.
847 const intGobVersion byte = 1
849 // GobEncode implements the gob.GobEncoder interface.
850 func (z *Int) GobEncode() ([]byte, error) {
851 buf := make([]byte, 1+len(z.abs)*_S) // extra byte for version and sign bit
852 i := z.abs.bytes(buf) - 1 // i >= 0
853 b := intGobVersion << 1 // make space for sign bit
861 // GobDecode implements the gob.GobDecoder interface.
862 func (z *Int) GobDecode(buf []byte) error {
864 return errors.New("Int.GobDecode: no data")
867 if b>>1 != intGobVersion {
868 return errors.New(fmt.Sprintf("Int.GobDecode: encoding version %d not supported", b>>1))
871 z.abs = z.abs.setBytes(buf[1:])