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