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