Source file
src/math/big/int.go
1
2
3
4
5
6
7 package big
8
9 import (
10 "fmt"
11 "io"
12 "math/rand"
13 "strings"
14 )
15
16
17
18
19
20
21
22
23
24
25 type Int struct {
26 neg bool
27 abs nat
28 }
29
30 var intOne = &Int{false, natOne}
31
32
33
34
35
36
37 func (x *Int) Sign() int {
38 if len(x.abs) == 0 {
39 return 0
40 }
41 if x.neg {
42 return -1
43 }
44 return 1
45 }
46
47
48 func (z *Int) SetInt64(x int64) *Int {
49 neg := false
50 if x < 0 {
51 neg = true
52 x = -x
53 }
54 z.abs = z.abs.setUint64(uint64(x))
55 z.neg = neg
56 return z
57 }
58
59
60 func (z *Int) SetUint64(x uint64) *Int {
61 z.abs = z.abs.setUint64(x)
62 z.neg = false
63 return z
64 }
65
66
67 func NewInt(x int64) *Int {
68 return new(Int).SetInt64(x)
69 }
70
71
72 func (z *Int) Set(x *Int) *Int {
73 if z != x {
74 z.abs = z.abs.set(x.abs)
75 z.neg = x.neg
76 }
77 return z
78 }
79
80
81
82
83
84
85 func (x *Int) Bits() []Word {
86 return x.abs
87 }
88
89
90
91
92
93
94 func (z *Int) SetBits(abs []Word) *Int {
95 z.abs = nat(abs).norm()
96 z.neg = false
97 return z
98 }
99
100
101 func (z *Int) Abs(x *Int) *Int {
102 z.Set(x)
103 z.neg = false
104 return z
105 }
106
107
108 func (z *Int) Neg(x *Int) *Int {
109 z.Set(x)
110 z.neg = len(z.abs) > 0 && !z.neg
111 return z
112 }
113
114
115 func (z *Int) Add(x, y *Int) *Int {
116 neg := x.neg
117 if x.neg == y.neg {
118
119
120 z.abs = z.abs.add(x.abs, y.abs)
121 } else {
122
123
124 if x.abs.cmp(y.abs) >= 0 {
125 z.abs = z.abs.sub(x.abs, y.abs)
126 } else {
127 neg = !neg
128 z.abs = z.abs.sub(y.abs, x.abs)
129 }
130 }
131 z.neg = len(z.abs) > 0 && neg
132 return z
133 }
134
135
136 func (z *Int) Sub(x, y *Int) *Int {
137 neg := x.neg
138 if x.neg != y.neg {
139
140
141 z.abs = z.abs.add(x.abs, y.abs)
142 } else {
143
144
145 if x.abs.cmp(y.abs) >= 0 {
146 z.abs = z.abs.sub(x.abs, y.abs)
147 } else {
148 neg = !neg
149 z.abs = z.abs.sub(y.abs, x.abs)
150 }
151 }
152 z.neg = len(z.abs) > 0 && neg
153 return z
154 }
155
156
157 func (z *Int) Mul(x, y *Int) *Int {
158
159
160
161
162 if x == y {
163 z.abs = z.abs.sqr(x.abs)
164 z.neg = false
165 return z
166 }
167 z.abs = z.abs.mul(x.abs, y.abs)
168 z.neg = len(z.abs) > 0 && x.neg != y.neg
169 return z
170 }
171
172
173
174
175 func (z *Int) MulRange(a, b int64) *Int {
176 switch {
177 case a > b:
178 return z.SetInt64(1)
179 case a <= 0 && b >= 0:
180 return z.SetInt64(0)
181 }
182
183
184 neg := false
185 if a < 0 {
186 neg = (b-a)&1 == 0
187 a, b = -b, -a
188 }
189
190 z.abs = z.abs.mulRange(uint64(a), uint64(b))
191 z.neg = neg
192 return z
193 }
194
195
196 func (z *Int) Binomial(n, k int64) *Int {
197
198 if n/2 < k && k <= n {
199 k = n - k
200 }
201 var a, b Int
202 a.MulRange(n-k+1, n)
203 b.MulRange(1, k)
204 return z.Quo(&a, &b)
205 }
206
207
208
209
210 func (z *Int) Quo(x, y *Int) *Int {
211 z.abs, _ = z.abs.div(nil, x.abs, y.abs)
212 z.neg = len(z.abs) > 0 && x.neg != y.neg
213 return z
214 }
215
216
217
218
219 func (z *Int) Rem(x, y *Int) *Int {
220 _, z.abs = nat(nil).div(z.abs, x.abs, y.abs)
221 z.neg = len(z.abs) > 0 && x.neg
222 return z
223 }
224
225
226
227
228
229
230
231
232
233
234
235
236 func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
237 z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
238 z.neg, r.neg = len(z.abs) > 0 && x.neg != y.neg, len(r.abs) > 0 && x.neg
239 return z, r
240 }
241
242
243
244
245 func (z *Int) Div(x, y *Int) *Int {
246 y_neg := y.neg
247 var r Int
248 z.QuoRem(x, y, &r)
249 if r.neg {
250 if y_neg {
251 z.Add(z, intOne)
252 } else {
253 z.Sub(z, intOne)
254 }
255 }
256 return z
257 }
258
259
260
261
262 func (z *Int) Mod(x, y *Int) *Int {
263 y0 := y
264 if z == y || alias(z.abs, y.abs) {
265 y0 = new(Int).Set(y)
266 }
267 var q Int
268 q.QuoRem(x, y, z)
269 if z.neg {
270 if y0.neg {
271 z.Sub(z, y0)
272 } else {
273 z.Add(z, y0)
274 }
275 }
276 return z
277 }
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293 func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
294 y0 := y
295 if z == y || alias(z.abs, y.abs) {
296 y0 = new(Int).Set(y)
297 }
298 z.QuoRem(x, y, m)
299 if m.neg {
300 if y0.neg {
301 z.Add(z, intOne)
302 m.Sub(m, y0)
303 } else {
304 z.Sub(z, intOne)
305 m.Add(m, y0)
306 }
307 }
308 return z, m
309 }
310
311
312
313
314
315
316 func (x *Int) Cmp(y *Int) (r int) {
317
318
319
320
321 switch {
322 case x == y:
323
324 case x.neg == y.neg:
325 r = x.abs.cmp(y.abs)
326 if x.neg {
327 r = -r
328 }
329 case x.neg:
330 r = -1
331 default:
332 r = 1
333 }
334 return
335 }
336
337
338
339
340
341
342 func (x *Int) CmpAbs(y *Int) int {
343 return x.abs.cmp(y.abs)
344 }
345
346
347 func low32(x nat) uint32 {
348 if len(x) == 0 {
349 return 0
350 }
351 return uint32(x[0])
352 }
353
354
355 func low64(x nat) uint64 {
356 if len(x) == 0 {
357 return 0
358 }
359 v := uint64(x[0])
360 if _W == 32 && len(x) > 1 {
361 return uint64(x[1])<<32 | v
362 }
363 return v
364 }
365
366
367
368 func (x *Int) Int64() int64 {
369 v := int64(low64(x.abs))
370 if x.neg {
371 v = -v
372 }
373 return v
374 }
375
376
377
378 func (x *Int) Uint64() uint64 {
379 return low64(x.abs)
380 }
381
382
383 func (x *Int) IsInt64() bool {
384 if len(x.abs) <= 64/_W {
385 w := int64(low64(x.abs))
386 return w >= 0 || x.neg && w == -w
387 }
388 return false
389 }
390
391
392 func (x *Int) IsUint64() bool {
393 return !x.neg && len(x.abs) <= 64/_W
394 }
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418 func (z *Int) SetString(s string, base int) (*Int, bool) {
419 return z.setFromScanner(strings.NewReader(s), base)
420 }
421
422
423
424 func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool) {
425 if _, _, err := z.scan(r, base); err != nil {
426 return nil, false
427 }
428
429 if _, err := r.ReadByte(); err != io.EOF {
430 return nil, false
431 }
432 return z, true
433 }
434
435
436
437 func (z *Int) SetBytes(buf []byte) *Int {
438 z.abs = z.abs.setBytes(buf)
439 z.neg = false
440 return z
441 }
442
443
444
445
446 func (x *Int) Bytes() []byte {
447 buf := make([]byte, len(x.abs)*_S)
448 return buf[x.abs.bytes(buf):]
449 }
450
451
452
453
454
455 func (x *Int) FillBytes(buf []byte) []byte {
456
457 for i := range buf {
458 buf[i] = 0
459 }
460 x.abs.bytes(buf)
461 return buf
462 }
463
464
465
466 func (x *Int) BitLen() int {
467 return x.abs.bitLen()
468 }
469
470
471
472 func (x *Int) TrailingZeroBits() uint {
473 return x.abs.trailingZeroBits()
474 }
475
476
477
478
479
480
481
482 func (z *Int) Exp(x, y, m *Int) *Int {
483
484 xWords := x.abs
485 if y.neg {
486 if m == nil || len(m.abs) == 0 {
487 return z.SetInt64(1)
488 }
489
490 inverse := new(Int).ModInverse(x, m)
491 if inverse == nil {
492 return nil
493 }
494 xWords = inverse.abs
495 }
496 yWords := y.abs
497
498 var mWords nat
499 if m != nil {
500 if z == m || alias(z.abs, m.abs) {
501 m = new(Int).Set(m)
502 }
503 mWords = m.abs
504 }
505
506 z.abs = z.abs.expNN(xWords, yWords, mWords)
507 z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1
508 if z.neg && len(mWords) > 0 {
509
510 z.abs = z.abs.sub(mWords, z.abs)
511 z.neg = false
512 }
513
514 return z
515 }
516
517
518
519
520
521
522
523
524
525
526
527
528 func (z *Int) GCD(x, y, a, b *Int) *Int {
529 if len(a.abs) == 0 || len(b.abs) == 0 {
530 lenA, lenB, negA, negB := len(a.abs), len(b.abs), a.neg, b.neg
531 if lenA == 0 {
532 z.Set(b)
533 } else {
534 z.Set(a)
535 }
536 z.neg = false
537 if x != nil {
538 if lenA == 0 {
539 x.SetUint64(0)
540 } else {
541 x.SetUint64(1)
542 x.neg = negA
543 }
544 }
545 if y != nil {
546 if lenB == 0 {
547 y.SetUint64(0)
548 } else {
549 y.SetUint64(1)
550 y.neg = negB
551 }
552 }
553 return z
554 }
555
556 return z.lehmerGCD(x, y, a, b)
557 }
558
559
560
561
562
563
564
565
566
567
568
569
570
571 func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool) {
572
573 var a1, a2, u2, v2 Word
574
575 m := len(B.abs)
576 n := len(A.abs)
577
578
579 h := nlz(A.abs[n-1])
580 a1 = A.abs[n-1]<<h | A.abs[n-2]>>(_W-h)
581
582 switch {
583 case n == m:
584 a2 = B.abs[n-1]<<h | B.abs[n-2]>>(_W-h)
585 case n == m+1:
586 a2 = B.abs[n-2] >> (_W - h)
587 default:
588 a2 = 0
589 }
590
591
592
593
594
595
596 even = false
597
598 u0, u1, u2 = 0, 1, 0
599 v0, v1, v2 = 0, 0, 1
600
601
602
603
604
605 for a2 >= v2 && a1-a2 >= v1+v2 {
606 q, r := a1/a2, a1%a2
607 a1, a2 = a2, r
608 u0, u1, u2 = u1, u2, u1+q*u2
609 v0, v1, v2 = v1, v2, v1+q*v2
610 even = !even
611 }
612 return
613 }
614
615
616
617
618
619
620
621
622
623
624 func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool) {
625
626 t.abs = t.abs.setWord(u0)
627 s.abs = s.abs.setWord(v0)
628 t.neg = !even
629 s.neg = even
630
631 t.Mul(A, t)
632 s.Mul(B, s)
633
634 r.abs = r.abs.setWord(u1)
635 q.abs = q.abs.setWord(v1)
636 r.neg = even
637 q.neg = !even
638
639 r.Mul(A, r)
640 q.Mul(B, q)
641
642 A.Add(t, s)
643 B.Add(r, q)
644 }
645
646
647
648 func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool) {
649 q, r = q.QuoRem(A, B, r)
650
651 *A, *B, *r = *B, *r, *A
652
653 if extended {
654
655 t.Set(Ub)
656 s.Mul(Ub, q)
657 Ub.Sub(Ua, s)
658 Ua.Set(t)
659 }
660 }
661
662
663
664
665
666
667
668
669
670
671
672 func (z *Int) lehmerGCD(x, y, a, b *Int) *Int {
673 var A, B, Ua, Ub *Int
674
675 A = new(Int).Abs(a)
676 B = new(Int).Abs(b)
677
678 extended := x != nil || y != nil
679
680 if extended {
681
682 Ua = new(Int).SetInt64(1)
683 Ub = new(Int)
684 }
685
686
687 q := new(Int)
688 r := new(Int)
689 s := new(Int)
690 t := new(Int)
691
692
693 if A.abs.cmp(B.abs) < 0 {
694 A, B = B, A
695 Ub, Ua = Ua, Ub
696 }
697
698
699 for len(B.abs) > 1 {
700
701 u0, u1, v0, v1, even := lehmerSimulate(A, B)
702
703
704 if v0 != 0 {
705
706
707
708 lehmerUpdate(A, B, q, r, s, t, u0, u1, v0, v1, even)
709
710 if extended {
711
712
713 lehmerUpdate(Ua, Ub, q, r, s, t, u0, u1, v0, v1, even)
714 }
715
716 } else {
717
718
719 euclidUpdate(A, B, Ua, Ub, q, r, s, t, extended)
720 }
721 }
722
723 if len(B.abs) > 0 {
724
725 if len(A.abs) > 1 {
726
727 euclidUpdate(A, B, Ua, Ub, q, r, s, t, extended)
728 }
729 if len(B.abs) > 0 {
730
731 aWord, bWord := A.abs[0], B.abs[0]
732 if extended {
733 var ua, ub, va, vb Word
734 ua, ub = 1, 0
735 va, vb = 0, 1
736 even := true
737 for bWord != 0 {
738 q, r := aWord/bWord, aWord%bWord
739 aWord, bWord = bWord, r
740 ua, ub = ub, ua+q*ub
741 va, vb = vb, va+q*vb
742 even = !even
743 }
744
745 t.abs = t.abs.setWord(ua)
746 s.abs = s.abs.setWord(va)
747 t.neg = !even
748 s.neg = even
749
750 t.Mul(Ua, t)
751 s.Mul(Ub, s)
752
753 Ua.Add(t, s)
754 } else {
755 for bWord != 0 {
756 aWord, bWord = bWord, aWord%bWord
757 }
758 }
759 A.abs[0] = aWord
760 }
761 }
762 negA := a.neg
763 if y != nil {
764
765 if y == b {
766 B.Set(b)
767 } else {
768 B = b
769 }
770
771 y.Mul(a, Ua)
772 if negA {
773 y.neg = !y.neg
774 }
775 y.Sub(A, y)
776 y.Div(y, B)
777 }
778
779 if x != nil {
780 *x = *Ua
781 if negA {
782 x.neg = !x.neg
783 }
784 }
785
786 *z = *A
787
788 return z
789 }
790
791
792
793
794
795 func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
796
797 if n.neg || len(n.abs) == 0 {
798 z.neg = false
799 z.abs = nil
800 return z
801 }
802 z.neg = false
803 z.abs = z.abs.random(rnd, n.abs, n.abs.bitLen())
804 return z
805 }
806
807
808
809
810
811 func (z *Int) ModInverse(g, n *Int) *Int {
812
813 if n.neg {
814 var n2 Int
815 n = n2.Neg(n)
816 }
817 if g.neg {
818 var g2 Int
819 g = g2.Mod(g, n)
820 }
821 var d, x Int
822 d.GCD(&x, nil, g, n)
823
824
825 if d.Cmp(intOne) != 0 {
826 return nil
827 }
828
829
830
831 if x.neg {
832 z.Add(&x, n)
833 } else {
834 z.Set(&x)
835 }
836 return z
837 }
838
839
840
841 func Jacobi(x, y *Int) int {
842 if len(y.abs) == 0 || y.abs[0]&1 == 0 {
843 panic(fmt.Sprintf("big: invalid 2nd argument to Int.Jacobi: need odd integer but got %s", y.String()))
844 }
845
846
847
848
849
850 var a, b, c Int
851 a.Set(x)
852 b.Set(y)
853 j := 1
854
855 if b.neg {
856 if a.neg {
857 j = -1
858 }
859 b.neg = false
860 }
861
862 for {
863 if b.Cmp(intOne) == 0 {
864 return j
865 }
866 if len(a.abs) == 0 {
867 return 0
868 }
869 a.Mod(&a, &b)
870 if len(a.abs) == 0 {
871 return 0
872 }
873
874
875
876 s := a.abs.trailingZeroBits()
877 if s&1 != 0 {
878 bmod8 := b.abs[0] & 7
879 if bmod8 == 3 || bmod8 == 5 {
880 j = -j
881 }
882 }
883 c.Rsh(&a, s)
884
885
886 if b.abs[0]&3 == 3 && c.abs[0]&3 == 3 {
887 j = -j
888 }
889 a.Set(&b)
890 b.Set(&c)
891 }
892 }
893
894
895
896
897
898
899
900
901
902 func (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int {
903 e := new(Int).Add(p, intOne)
904 e.Rsh(e, 2)
905 z.Exp(x, e, p)
906 return z
907 }
908
909
910
911
912
913
914
915
916
917 func (z *Int) modSqrt5Mod8Prime(x, p *Int) *Int {
918
919
920 e := new(Int).Rsh(p, 3)
921 tx := new(Int).Lsh(x, 1)
922 alpha := new(Int).Exp(tx, e, p)
923 beta := new(Int).Mul(alpha, alpha)
924 beta.Mod(beta, p)
925 beta.Mul(beta, tx)
926 beta.Mod(beta, p)
927 beta.Sub(beta, intOne)
928 beta.Mul(beta, x)
929 beta.Mod(beta, p)
930 beta.Mul(beta, alpha)
931 z.Mod(beta, p)
932 return z
933 }
934
935
936
937 func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int {
938
939 var s Int
940 s.Sub(p, intOne)
941 e := s.abs.trailingZeroBits()
942 s.Rsh(&s, e)
943
944
945 var n Int
946 n.SetInt64(2)
947 for Jacobi(&n, p) != -1 {
948 n.Add(&n, intOne)
949 }
950
951
952
953
954
955 var y, b, g, t Int
956 y.Add(&s, intOne)
957 y.Rsh(&y, 1)
958 y.Exp(x, &y, p)
959 b.Exp(x, &s, p)
960 g.Exp(&n, &s, p)
961 r := e
962 for {
963
964 var m uint
965 t.Set(&b)
966 for t.Cmp(intOne) != 0 {
967 t.Mul(&t, &t).Mod(&t, p)
968 m++
969 }
970
971 if m == 0 {
972 return z.Set(&y)
973 }
974
975 t.SetInt64(0).SetBit(&t, int(r-m-1), 1).Exp(&g, &t, p)
976
977 g.Mul(&t, &t).Mod(&g, p)
978 y.Mul(&y, &t).Mod(&y, p)
979 b.Mul(&b, &g).Mod(&b, p)
980 r = m
981 }
982 }
983
984
985
986
987
988 func (z *Int) ModSqrt(x, p *Int) *Int {
989 switch Jacobi(x, p) {
990 case -1:
991 return nil
992 case 0:
993 return z.SetInt64(0)
994 case 1:
995 break
996 }
997 if x.neg || x.Cmp(p) >= 0 {
998 x = new(Int).Mod(x, p)
999 }
1000
1001 switch {
1002 case p.abs[0]%4 == 3:
1003
1004 return z.modSqrt3Mod4Prime(x, p)
1005 case p.abs[0]%8 == 5:
1006
1007 return z.modSqrt5Mod8Prime(x, p)
1008 default:
1009
1010 return z.modSqrtTonelliShanks(x, p)
1011 }
1012 }
1013
1014
1015 func (z *Int) Lsh(x *Int, n uint) *Int {
1016 z.abs = z.abs.shl(x.abs, n)
1017 z.neg = x.neg
1018 return z
1019 }
1020
1021
1022 func (z *Int) Rsh(x *Int, n uint) *Int {
1023 if x.neg {
1024
1025 t := z.abs.sub(x.abs, natOne)
1026 t = t.shr(t, n)
1027 z.abs = t.add(t, natOne)
1028 z.neg = true
1029 return z
1030 }
1031
1032 z.abs = z.abs.shr(x.abs, n)
1033 z.neg = false
1034 return z
1035 }
1036
1037
1038
1039 func (x *Int) Bit(i int) uint {
1040 if i == 0 {
1041
1042 if len(x.abs) > 0 {
1043 return uint(x.abs[0] & 1)
1044 }
1045 return 0
1046 }
1047 if i < 0 {
1048 panic("negative bit index")
1049 }
1050 if x.neg {
1051 t := nat(nil).sub(x.abs, natOne)
1052 return t.bit(uint(i)) ^ 1
1053 }
1054
1055 return x.abs.bit(uint(i))
1056 }
1057
1058
1059
1060
1061
1062 func (z *Int) SetBit(x *Int, i int, b uint) *Int {
1063 if i < 0 {
1064 panic("negative bit index")
1065 }
1066 if x.neg {
1067 t := z.abs.sub(x.abs, natOne)
1068 t = t.setBit(t, uint(i), b^1)
1069 z.abs = t.add(t, natOne)
1070 z.neg = len(z.abs) > 0
1071 return z
1072 }
1073 z.abs = z.abs.setBit(x.abs, uint(i), b)
1074 z.neg = false
1075 return z
1076 }
1077
1078
1079 func (z *Int) And(x, y *Int) *Int {
1080 if x.neg == y.neg {
1081 if x.neg {
1082
1083 x1 := nat(nil).sub(x.abs, natOne)
1084 y1 := nat(nil).sub(y.abs, natOne)
1085 z.abs = z.abs.add(z.abs.or(x1, y1), natOne)
1086 z.neg = true
1087 return z
1088 }
1089
1090
1091 z.abs = z.abs.and(x.abs, y.abs)
1092 z.neg = false
1093 return z
1094 }
1095
1096
1097 if x.neg {
1098 x, y = y, x
1099 }
1100
1101
1102 y1 := nat(nil).sub(y.abs, natOne)
1103 z.abs = z.abs.andNot(x.abs, y1)
1104 z.neg = false
1105 return z
1106 }
1107
1108
1109 func (z *Int) AndNot(x, y *Int) *Int {
1110 if x.neg == y.neg {
1111 if x.neg {
1112
1113 x1 := nat(nil).sub(x.abs, natOne)
1114 y1 := nat(nil).sub(y.abs, natOne)
1115 z.abs = z.abs.andNot(y1, x1)
1116 z.neg = false
1117 return z
1118 }
1119
1120
1121 z.abs = z.abs.andNot(x.abs, y.abs)
1122 z.neg = false
1123 return z
1124 }
1125
1126 if x.neg {
1127
1128 x1 := nat(nil).sub(x.abs, natOne)
1129 z.abs = z.abs.add(z.abs.or(x1, y.abs), natOne)
1130 z.neg = true
1131 return z
1132 }
1133
1134
1135 y1 := nat(nil).sub(y.abs, natOne)
1136 z.abs = z.abs.and(x.abs, y1)
1137 z.neg = false
1138 return z
1139 }
1140
1141
1142 func (z *Int) Or(x, y *Int) *Int {
1143 if x.neg == y.neg {
1144 if x.neg {
1145
1146 x1 := nat(nil).sub(x.abs, natOne)
1147 y1 := nat(nil).sub(y.abs, natOne)
1148 z.abs = z.abs.add(z.abs.and(x1, y1), natOne)
1149 z.neg = true
1150 return z
1151 }
1152
1153
1154 z.abs = z.abs.or(x.abs, y.abs)
1155 z.neg = false
1156 return z
1157 }
1158
1159
1160 if x.neg {
1161 x, y = y, x
1162 }
1163
1164
1165 y1 := nat(nil).sub(y.abs, natOne)
1166 z.abs = z.abs.add(z.abs.andNot(y1, x.abs), natOne)
1167 z.neg = true
1168 return z
1169 }
1170
1171
1172 func (z *Int) Xor(x, y *Int) *Int {
1173 if x.neg == y.neg {
1174 if x.neg {
1175
1176 x1 := nat(nil).sub(x.abs, natOne)
1177 y1 := nat(nil).sub(y.abs, natOne)
1178 z.abs = z.abs.xor(x1, y1)
1179 z.neg = false
1180 return z
1181 }
1182
1183
1184 z.abs = z.abs.xor(x.abs, y.abs)
1185 z.neg = false
1186 return z
1187 }
1188
1189
1190 if x.neg {
1191 x, y = y, x
1192 }
1193
1194
1195 y1 := nat(nil).sub(y.abs, natOne)
1196 z.abs = z.abs.add(z.abs.xor(x.abs, y1), natOne)
1197 z.neg = true
1198 return z
1199 }
1200
1201
1202 func (z *Int) Not(x *Int) *Int {
1203 if x.neg {
1204
1205 z.abs = z.abs.sub(x.abs, natOne)
1206 z.neg = false
1207 return z
1208 }
1209
1210
1211 z.abs = z.abs.add(x.abs, natOne)
1212 z.neg = true
1213 return z
1214 }
1215
1216
1217
1218 func (z *Int) Sqrt(x *Int) *Int {
1219 if x.neg {
1220 panic("square root of negative number")
1221 }
1222 z.neg = false
1223 z.abs = z.abs.sqrt(x.abs)
1224 return z
1225 }
1226
View as plain text