1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package apd
16
17 import (
18 "bytes"
19 "encoding/gob"
20 "encoding/hex"
21 "encoding/json"
22 "encoding/xml"
23 "fmt"
24 "math"
25 "math/big"
26 "math/rand"
27 "reflect"
28 "strconv"
29 "strings"
30 "testing"
31 "testing/quick"
32 )
33
34
35
36 func TestBigIntMatchesMathBigInt(t *testing.T) {
37
38 const (
39 panicDivisionByZero = "division by zero"
40 panicJacobi = "invalid 2nd argument to Int.Jacobi: need odd integer"
41 panicNegativeBit = "negative bit index"
42 panicSquareRootOfNegativeNum = "square root of negative number"
43 )
44 catchPanic := func(fn func() string, catches ...string) (res string) {
45 defer func() {
46 if r := recover(); r != nil {
47 if rs, ok := r.(string); ok {
48 for _, catch := range catches {
49 if strings.Contains(rs, catch) {
50 res = fmt.Sprintf("caught: %s", r)
51 }
52 }
53 }
54 if res == "" {
55 panic(r)
56 }
57 }
58 }()
59 return fn()
60 }
61
62 t.Run("Abs", func(t *testing.T) {
63 apd := func(z, x number) string {
64 return z.toApd(t).Abs(x.toApd(t)).String()
65 }
66 math := func(z, x number) string {
67 return z.toMath(t).Abs(x.toMath(t)).String()
68 }
69 require(t, quick.CheckEqual(apd, math, nil))
70 })
71
72 t.Run("Add", func(t *testing.T) {
73 apd := func(z, x, y number) string {
74 return z.toApd(t).Add(x.toApd(t), y.toApd(t)).String()
75 }
76 math := func(z, x, y number) string {
77 return z.toMath(t).Add(x.toMath(t), y.toMath(t)).String()
78 }
79 require(t, quick.CheckEqual(apd, math, nil))
80 })
81
82 t.Run("And", func(t *testing.T) {
83 apd := func(z, x, y number) string {
84 return z.toApd(t).And(x.toApd(t), y.toApd(t)).String()
85 }
86 math := func(z, x, y number) string {
87 return z.toMath(t).And(x.toMath(t), y.toMath(t)).String()
88 }
89 require(t, quick.CheckEqual(apd, math, nil))
90 })
91
92 t.Run("AndNot", func(t *testing.T) {
93 apd := func(z, x, y number) string {
94 return z.toApd(t).AndNot(x.toApd(t), y.toApd(t)).String()
95 }
96 math := func(z, x, y number) string {
97 return z.toMath(t).AndNot(x.toMath(t), y.toMath(t)).String()
98 }
99 require(t, quick.CheckEqual(apd, math, nil))
100 })
101
102 t.Run("Append", func(t *testing.T) {
103 apd := func(z numberOrNil) []byte {
104 return z.toApd(t).Append(nil, 10)
105 }
106 math := func(z numberOrNil) []byte {
107 return z.toMath(t).Append(nil, 10)
108 }
109 require(t, quick.CheckEqual(apd, math, nil))
110 })
111
112 t.Run("Binomial", func(t *testing.T) {
113 t.Skip("too slow")
114 apd := func(z number, n, k int64) string {
115 return z.toApd(t).Binomial(n, k).String()
116 }
117 math := func(z number, n, k int64) string {
118 return z.toMath(t).Binomial(n, k).String()
119 }
120 require(t, quick.CheckEqual(apd, math, nil))
121 })
122
123 t.Run("Bit", func(t *testing.T) {
124 apd := func(z number, i int) string {
125 return catchPanic(func() string {
126 return strconv.FormatUint(uint64(z.toApd(t).Bit(i)), 10)
127 }, panicNegativeBit)
128 }
129 math := func(z number, i int) string {
130 return catchPanic(func() string {
131 return strconv.FormatUint(uint64(z.toMath(t).Bit(i)), 10)
132 }, panicNegativeBit)
133 }
134 require(t, quick.CheckEqual(apd, math, nil))
135 })
136
137 t.Run("BitLen", func(t *testing.T) {
138 apd := func(z number) int {
139 return z.toApd(t).BitLen()
140 }
141 math := func(z number) int {
142 return z.toMath(t).BitLen()
143 }
144 require(t, quick.CheckEqual(apd, math, nil))
145 })
146
147 t.Run("Bits", func(t *testing.T) {
148 emptyToNil := func(w []big.Word) []big.Word {
149 if len(w) == 0 {
150 return nil
151 }
152 return w
153 }
154 apd := func(z number) []big.Word {
155 return emptyToNil(z.toApd(t).Bits())
156 }
157 math := func(z number) []big.Word {
158 return emptyToNil(z.toMath(t).Bits())
159 }
160 require(t, quick.CheckEqual(apd, math, nil))
161 })
162
163 t.Run("Bytes", func(t *testing.T) {
164 apd := func(z number) []byte {
165 return z.toApd(t).Bytes()
166 }
167 math := func(z number) []byte {
168 return z.toMath(t).Bytes()
169 }
170 require(t, quick.CheckEqual(apd, math, nil))
171 })
172
173 t.Run("Cmp", func(t *testing.T) {
174 apd := func(z, y number) int {
175 return z.toApd(t).Cmp(y.toApd(t))
176 }
177 math := func(z, y number) int {
178 return z.toMath(t).Cmp(y.toMath(t))
179 }
180 require(t, quick.CheckEqual(apd, math, nil))
181 })
182
183 t.Run("CmpAbs", func(t *testing.T) {
184 apd := func(z, y number) int {
185 return z.toApd(t).CmpAbs(y.toApd(t))
186 }
187 math := func(z, y number) int {
188 return z.toMath(t).CmpAbs(y.toMath(t))
189 }
190 require(t, quick.CheckEqual(apd, math, nil))
191 })
192
193 t.Run("Div", func(t *testing.T) {
194 apd := func(z, x, y number) string {
195 return catchPanic(func() string {
196 return z.toApd(t).Div(x.toApd(t), y.toApd(t)).String()
197 }, panicDivisionByZero)
198 }
199 math := func(z, x, y number) string {
200 return catchPanic(func() string {
201 return z.toMath(t).Div(x.toMath(t), y.toMath(t)).String()
202 }, panicDivisionByZero)
203 }
204 require(t, quick.CheckEqual(apd, math, nil))
205 })
206
207 t.Run("DivMod", func(t *testing.T) {
208 apd := func(z, x, y, m number) string {
209 return catchPanic(func() string {
210 zi, mi := z.toApd(t), m.toApd(t)
211 zi.DivMod(x.toApd(t), y.toApd(t), mi)
212 return zi.String() + " | " + mi.String()
213 }, panicDivisionByZero)
214 }
215 math := func(z, x, y, m number) string {
216 return catchPanic(func() string {
217 zi, mi := z.toMath(t), m.toMath(t)
218 zi.DivMod(x.toMath(t), y.toMath(t), mi)
219 return zi.String() + " | " + mi.String()
220 }, panicDivisionByZero)
221 }
222 require(t, quick.CheckEqual(apd, math, nil))
223 })
224
225 t.Run("Exp", func(t *testing.T) {
226 t.Skip("too slow")
227 apd := func(z, x, y, m number) string {
228 return z.toApd(t).Exp(x.toApd(t), y.toApd(t), m.toApd(t)).String()
229 }
230 math := func(z, x, y, m number) string {
231 return z.toMath(t).Exp(x.toMath(t), y.toMath(t), m.toMath(t)).String()
232 }
233 require(t, quick.CheckEqual(apd, math, nil))
234 })
235
236 t.Run("Format", func(t *testing.T) {
237
238 apd := func(z numberOrNil) string {
239 return fmt.Sprint(z.toApd(t))
240 }
241 math := func(z numberOrNil) string {
242 return fmt.Sprint(z.toMath(t))
243 }
244 require(t, quick.CheckEqual(apd, math, nil))
245 })
246
247 t.Run("GCD", func(t *testing.T) {
248 apd := func(z number, x, y numberOrNil, a, b number) string {
249 return z.toApd(t).GCD(x.toApd(t), y.toApd(t), a.toApd(t), b.toApd(t)).String()
250 }
251 math := func(z number, x, y numberOrNil, a, b number) string {
252 return z.toMath(t).GCD(x.toMath(t), y.toMath(t), a.toMath(t), b.toMath(t)).String()
253 }
254 require(t, quick.CheckEqual(apd, math, nil))
255 })
256
257 t.Run("GobEncode", func(t *testing.T) {
258 apd := func(z numberOrNil) ([]byte, error) {
259 return z.toApd(t).GobEncode()
260 }
261 math := func(z numberOrNil) ([]byte, error) {
262 return z.toMath(t).GobEncode()
263 }
264 require(t, quick.CheckEqual(apd, math, nil))
265 })
266
267 t.Run("GobDecode", func(t *testing.T) {
268 apd := func(z number, buf []byte) (string, error) {
269 zi := z.toApd(t)
270 err := zi.GobDecode(buf)
271 return zi.String(), err
272 }
273 math := func(z number, buf []byte) (string, error) {
274 zi := z.toMath(t)
275 err := zi.GobDecode(buf)
276 return zi.String(), err
277 }
278 require(t, quick.CheckEqual(apd, math, nil))
279 })
280
281 t.Run("Int64", func(t *testing.T) {
282 apd := func(z number) int64 {
283 return z.toApd(t).Int64()
284 }
285 math := func(z number) int64 {
286 return z.toMath(t).Int64()
287 }
288 require(t, quick.CheckEqual(apd, math, nil))
289 })
290
291 t.Run("IsInt64", func(t *testing.T) {
292 apd := func(z number) bool {
293 return z.toApd(t).IsInt64()
294 }
295 math := func(z number) bool {
296 return z.toMath(t).IsInt64()
297 }
298 require(t, quick.CheckEqual(apd, math, nil))
299 })
300
301 t.Run("IsUint64", func(t *testing.T) {
302 apd := func(z number) bool {
303 return z.toApd(t).IsUint64()
304 }
305 math := func(z number) bool {
306 return z.toMath(t).IsUint64()
307 }
308 require(t, quick.CheckEqual(apd, math, nil))
309 })
310
311 t.Run("Lsh", func(t *testing.T) {
312 const maxShift = 1000
313 apd := func(z, x number, n uint) string {
314 if n > maxShift {
315 n = maxShift
316 }
317 return z.toApd(t).Lsh(x.toApd(t), n).String()
318 }
319 math := func(z, x number, n uint) string {
320 if n > maxShift {
321 n = maxShift
322 }
323 return z.toMath(t).Lsh(x.toMath(t), n).String()
324 }
325 require(t, quick.CheckEqual(apd, math, nil))
326 })
327
328 t.Run("MarshalJSON", func(t *testing.T) {
329 apd := func(z numberOrNil) ([]byte, error) {
330 return z.toApd(t).MarshalJSON()
331 }
332 math := func(z numberOrNil) ([]byte, error) {
333 return z.toMath(t).MarshalJSON()
334 }
335 require(t, quick.CheckEqual(apd, math, nil))
336 })
337
338 t.Run("MarshalText", func(t *testing.T) {
339 apd := func(z numberOrNil) ([]byte, error) {
340 return z.toApd(t).MarshalText()
341 }
342 math := func(z numberOrNil) ([]byte, error) {
343 return z.toMath(t).MarshalText()
344 }
345 require(t, quick.CheckEqual(apd, math, nil))
346 })
347
348 t.Run("Mod", func(t *testing.T) {
349 apd := func(z, x, y number) string {
350 return catchPanic(func() string {
351 return z.toApd(t).Mod(x.toApd(t), y.toApd(t)).String()
352 }, panicDivisionByZero, panicJacobi)
353 }
354 math := func(z, x, y number) string {
355 return catchPanic(func() string {
356 return z.toMath(t).Mod(x.toMath(t), y.toMath(t)).String()
357 }, panicDivisionByZero, panicJacobi)
358 }
359 require(t, quick.CheckEqual(apd, math, nil))
360 })
361
362 t.Run("ModInverse", func(t *testing.T) {
363 apd := func(z, x, y number) string {
364 return catchPanic(func() string {
365 return z.toApd(t).ModInverse(x.toApd(t), y.toApd(t)).String()
366 }, panicDivisionByZero)
367 }
368 math := func(z, x, y number) string {
369 return catchPanic(func() string {
370 return z.toMath(t).ModInverse(x.toMath(t), y.toMath(t)).String()
371 }, panicDivisionByZero)
372 }
373 require(t, quick.CheckEqual(apd, math, nil))
374 })
375
376 t.Run("ModSqrt", func(t *testing.T) {
377 t.Skip("too slow")
378 apd := func(z, x, y number) string {
379 return catchPanic(func() string {
380 return z.toApd(t).ModSqrt(x.toApd(t), y.toApd(t)).String()
381 }, panicJacobi)
382 }
383 math := func(z, x, y number) string {
384 return catchPanic(func() string {
385 return z.toMath(t).ModSqrt(x.toMath(t), y.toMath(t)).String()
386 }, panicJacobi)
387 }
388 require(t, quick.CheckEqual(apd, math, nil))
389 })
390
391 t.Run("Mul", func(t *testing.T) {
392 apd := func(z, x, y number) string {
393 return z.toApd(t).Mul(x.toApd(t), y.toApd(t)).String()
394 }
395 math := func(z, x, y number) string {
396 return z.toMath(t).Mul(x.toMath(t), y.toMath(t)).String()
397 }
398 require(t, quick.CheckEqual(apd, math, nil))
399 })
400
401 t.Run("MulRange", func(t *testing.T) {
402 t.Skip("too slow")
403 apd := func(z number, x, y int64) string {
404 return z.toApd(t).MulRange(x, y).String()
405 }
406 math := func(z number, x, y int64) string {
407 return z.toMath(t).MulRange(x, y).String()
408 }
409 require(t, quick.CheckEqual(apd, math, nil))
410 })
411
412 t.Run("Neg", func(t *testing.T) {
413 apd := func(z, x number) string {
414 return z.toApd(t).Neg(x.toApd(t)).String()
415 }
416 math := func(z, x number) string {
417 return z.toMath(t).Neg(x.toMath(t)).String()
418 }
419 require(t, quick.CheckEqual(apd, math, nil))
420 })
421
422 t.Run("Not", func(t *testing.T) {
423 apd := func(z, x number) string {
424 return z.toApd(t).Not(x.toApd(t)).String()
425 }
426 math := func(z, x number) string {
427 return z.toMath(t).Not(x.toMath(t)).String()
428 }
429 require(t, quick.CheckEqual(apd, math, nil))
430 })
431
432 t.Run("Or", func(t *testing.T) {
433 apd := func(z, x, y number) string {
434 return z.toApd(t).Or(x.toApd(t), y.toApd(t)).String()
435 }
436 math := func(z, x, y number) string {
437 return z.toMath(t).Or(x.toMath(t), y.toMath(t)).String()
438 }
439 require(t, quick.CheckEqual(apd, math, nil))
440 })
441
442 t.Run("ProbablyPrime", func(t *testing.T) {
443 apd := func(z number) bool {
444 return z.toApd(t).ProbablyPrime(64)
445 }
446 math := func(z number) bool {
447 return z.toMath(t).ProbablyPrime(64)
448 }
449 require(t, quick.CheckEqual(apd, math, nil))
450 })
451
452 t.Run("Quo", func(t *testing.T) {
453 apd := func(z, x, y number) string {
454 return catchPanic(func() string {
455 return z.toApd(t).Quo(x.toApd(t), y.toApd(t)).String()
456 }, panicDivisionByZero)
457 }
458 math := func(z, x, y number) string {
459 return catchPanic(func() string {
460 return z.toMath(t).Quo(x.toMath(t), y.toMath(t)).String()
461 }, panicDivisionByZero)
462 }
463 require(t, quick.CheckEqual(apd, math, nil))
464 })
465
466 t.Run("QuoRem", func(t *testing.T) {
467 apd := func(z, x, y, r number) string {
468 return catchPanic(func() string {
469 zi, ri := z.toApd(t), r.toApd(t)
470 zi.QuoRem(x.toApd(t), y.toApd(t), ri)
471 return zi.String() + " | " + ri.String()
472 }, panicDivisionByZero)
473 }
474 math := func(z, x, y, r number) string {
475 return catchPanic(func() string {
476 zi, ri := z.toMath(t), r.toMath(t)
477 zi.QuoRem(x.toMath(t), y.toMath(t), ri)
478 return zi.String() + " | " + ri.String()
479 }, panicDivisionByZero)
480 }
481 require(t, quick.CheckEqual(apd, math, nil))
482 })
483
484 t.Run("Rand", func(t *testing.T) {
485 apd := func(z, n number, seed int64) string {
486 rng := rand.New(rand.NewSource(seed))
487 return z.toApd(t).Rand(rng, n.toApd(t)).String()
488 }
489 math := func(z, n number, seed int64) string {
490 rng := rand.New(rand.NewSource(seed))
491 return z.toMath(t).Rand(rng, n.toMath(t)).String()
492 }
493 require(t, quick.CheckEqual(apd, math, nil))
494 })
495
496 t.Run("Rem", func(t *testing.T) {
497 apd := func(z, x, y number) string {
498 return catchPanic(func() string {
499 return z.toApd(t).Rem(x.toApd(t), y.toApd(t)).String()
500 }, panicDivisionByZero)
501 }
502 math := func(z, x, y number) string {
503 return catchPanic(func() string {
504 return z.toMath(t).Rem(x.toMath(t), y.toMath(t)).String()
505 }, panicDivisionByZero)
506 }
507 require(t, quick.CheckEqual(apd, math, nil))
508 })
509
510 t.Run("Rsh", func(t *testing.T) {
511 const maxShift = 1000
512 apd := func(z, x number, n uint) string {
513 if n > maxShift {
514 n = maxShift
515 }
516 return z.toApd(t).Rsh(x.toApd(t), n).String()
517 }
518 math := func(z, x number, n uint) string {
519 if n > maxShift {
520 n = maxShift
521 }
522 return z.toMath(t).Rsh(x.toMath(t), n).String()
523 }
524 require(t, quick.CheckEqual(apd, math, nil))
525 })
526
527 t.Run("Scan", func(t *testing.T) {
528
529 apd := func(z, src number) (string, error) {
530 zi := z.toApd(t)
531 _, err := fmt.Sscan(string(src), zi)
532 return zi.String(), err
533 }
534 math := func(z, src number) (string, error) {
535 zi := z.toMath(t)
536 _, err := fmt.Sscan(string(src), zi)
537 return zi.String(), err
538 }
539 require(t, quick.CheckEqual(apd, math, nil))
540 })
541
542 t.Run("Set", func(t *testing.T) {
543 apd := func(z, x number) string {
544 return z.toApd(t).Set(x.toApd(t)).String()
545 }
546 math := func(z, x number) string {
547 return z.toMath(t).Set(x.toMath(t)).String()
548 }
549 require(t, quick.CheckEqual(apd, math, nil))
550 })
551
552 t.Run("SetBit", func(t *testing.T) {
553 const maxBit = 1000
554 apd := func(z, x number, i int, b bool) string {
555 if i > maxBit {
556 i = maxBit
557 }
558 bi := uint(0)
559 if b {
560 bi = 1
561 }
562 return catchPanic(func() string {
563 return z.toApd(t).SetBit(x.toApd(t), i, bi).String()
564 }, panicNegativeBit)
565 }
566 math := func(z, x number, i int, b bool) string {
567 if i > maxBit {
568 i = maxBit
569 }
570 bi := uint(0)
571 if b {
572 bi = 1
573 }
574 return catchPanic(func() string {
575 return z.toMath(t).SetBit(x.toMath(t), i, bi).String()
576 }, panicNegativeBit)
577 }
578 require(t, quick.CheckEqual(apd, math, nil))
579 })
580
581 t.Run("SetBits", func(t *testing.T) {
582 apd := func(z number, abs []big.Word) string {
583 return z.toApd(t).SetBits(abs).String()
584 }
585 math := func(z number, abs []big.Word) string {
586 return z.toMath(t).SetBits(abs).String()
587 }
588 require(t, quick.CheckEqual(apd, math, nil))
589 })
590
591 t.Run("SetBytes", func(t *testing.T) {
592 apd := func(z number, buf []byte) string {
593 return z.toApd(t).SetBytes(buf).String()
594 }
595 math := func(z number, buf []byte) string {
596 return z.toMath(t).SetBytes(buf).String()
597 }
598 require(t, quick.CheckEqual(apd, math, nil))
599 })
600
601 t.Run("SetInt64", func(t *testing.T) {
602 apd := func(z number, x int64) string {
603 return z.toApd(t).SetInt64(x).String()
604 }
605 math := func(z number, x int64) string {
606 return z.toMath(t).SetInt64(x).String()
607 }
608 require(t, quick.CheckEqual(apd, math, nil))
609 })
610
611 t.Run("SetString", func(t *testing.T) {
612 apd := func(z, x number) (string, bool) {
613 zi, ok := z.toApd(t).SetString(string(x), 10)
614 return zi.String(), ok
615 }
616 math := func(z, x number) (string, bool) {
617 zi, ok := z.toMath(t).SetString(string(x), 10)
618 return zi.String(), ok
619 }
620 require(t, quick.CheckEqual(apd, math, nil))
621 })
622
623 t.Run("SetUint64", func(t *testing.T) {
624 apd := func(z number, x uint64) string {
625 return z.toApd(t).SetUint64(x).String()
626 }
627 math := func(z number, x uint64) string {
628 return z.toMath(t).SetUint64(x).String()
629 }
630 require(t, quick.CheckEqual(apd, math, nil))
631 })
632
633 t.Run("Sign", func(t *testing.T) {
634 apd := func(z number) int {
635 return z.toApd(t).Sign()
636 }
637 math := func(z number) int {
638 return z.toMath(t).Sign()
639 }
640 require(t, quick.CheckEqual(apd, math, nil))
641 })
642
643 t.Run("Sqrt", func(t *testing.T) {
644 apd := func(z, x number) string {
645 return catchPanic(func() string {
646 return z.toApd(t).Sqrt(x.toApd(t)).String()
647 }, panicSquareRootOfNegativeNum)
648 }
649 math := func(z, x number) string {
650 return catchPanic(func() string {
651 return z.toMath(t).Sqrt(x.toMath(t)).String()
652 }, panicSquareRootOfNegativeNum)
653 }
654 require(t, quick.CheckEqual(apd, math, nil))
655 })
656
657 t.Run("String", func(t *testing.T) {
658 apd := func(z numberOrNil) string {
659 return z.toApd(t).String()
660 }
661 math := func(z numberOrNil) string {
662 return z.toMath(t).String()
663 }
664 require(t, quick.CheckEqual(apd, math, nil))
665 })
666
667 t.Run("Sub", func(t *testing.T) {
668 apd := func(z, x, y number) string {
669 return z.toApd(t).Sub(x.toApd(t), y.toApd(t)).String()
670 }
671 math := func(z, x, y number) string {
672 return z.toMath(t).Sub(x.toMath(t), y.toMath(t)).String()
673 }
674 require(t, quick.CheckEqual(apd, math, nil))
675 })
676
677 t.Run("Text", func(t *testing.T) {
678 apd := func(z numberOrNil) string {
679 return z.toApd(t).Text(10)
680 }
681 math := func(z numberOrNil) string {
682 return z.toMath(t).Text(10)
683 }
684 require(t, quick.CheckEqual(apd, math, nil))
685 })
686
687 t.Run("TrailingZeroBits", func(t *testing.T) {
688 apd := func(z number) uint {
689 return z.toApd(t).TrailingZeroBits()
690 }
691 math := func(z number) uint {
692 return z.toMath(t).TrailingZeroBits()
693 }
694 require(t, quick.CheckEqual(apd, math, nil))
695 })
696
697 t.Run("Uint64", func(t *testing.T) {
698 apd := func(z number) uint64 {
699 return z.toApd(t).Uint64()
700 }
701 math := func(z number) uint64 {
702 return z.toMath(t).Uint64()
703 }
704 require(t, quick.CheckEqual(apd, math, nil))
705 })
706
707 t.Run("UnmarshalJSON", func(t *testing.T) {
708 apd := func(z number, text []byte) (string, error) {
709 zi := z.toApd(t)
710 if err := zi.UnmarshalJSON(text); err != nil {
711 return "", err
712 }
713 return zi.String(), nil
714 }
715 math := func(z number, text []byte) (string, error) {
716 zi := z.toMath(t)
717 if err := zi.UnmarshalJSON(text); err != nil {
718 return "", err
719 }
720 return zi.String(), nil
721 }
722 require(t, quick.CheckEqual(apd, math, nil))
723 })
724
725 t.Run("UnmarshalText", func(t *testing.T) {
726 apd := func(z number, text []byte) (string, error) {
727 zi := z.toApd(t)
728 if err := zi.UnmarshalText(text); err != nil {
729 return "", err
730 }
731 return zi.String(), nil
732 }
733 math := func(z number, text []byte) (string, error) {
734 zi := z.toMath(t)
735 if err := zi.UnmarshalText(text); err != nil {
736 return "", err
737 }
738 return zi.String(), nil
739 }
740 require(t, quick.CheckEqual(apd, math, nil))
741 })
742
743 t.Run("Xor", func(t *testing.T) {
744 apd := func(z, x, y number) string {
745 return z.toApd(t).Xor(x.toApd(t), y.toApd(t)).String()
746 }
747 math := func(z, x, y number) string {
748 return z.toMath(t).Xor(x.toMath(t), y.toMath(t)).String()
749 }
750 require(t, quick.CheckEqual(apd, math, nil))
751 })
752 }
753
754
755
756 func TestBigIntMathBigIntRoundTrip(t *testing.T) {
757 t.Run("apd->math->apd", func(t *testing.T) {
758 base := func(z number) string {
759 return z.toApd(t).String()
760 }
761 roundtrip := func(z number) string {
762 bi := z.toApd(t).MathBigInt()
763 return new(BigInt).SetMathBigInt(bi).String()
764 }
765 require(t, quick.CheckEqual(base, roundtrip, nil))
766 })
767
768 t.Run("math->apd->math", func(t *testing.T) {
769 base := func(z number) string {
770 return z.toMath(t).String()
771 }
772 roundtrip := func(z number) string {
773 bi := new(BigInt).SetMathBigInt(z.toMath(t))
774 return bi.MathBigInt().String()
775 }
776 require(t, quick.CheckEqual(base, roundtrip, nil))
777 })
778 }
779
780
781 type number string
782
783 func (n number) Generate(r *rand.Rand, size int) reflect.Value {
784 var s string
785 if r.Intn(2) != 0 {
786 s = n.generateInterestingNumber(r)
787 } else {
788 s = n.generateRandomNumber(r, size)
789 }
790 return reflect.ValueOf(number(s))
791 }
792
793 func (z *BigInt) incr() *BigInt { return z.Add(z, bigOne) }
794 func (z *BigInt) decr() *BigInt { return z.Sub(z, bigOne) }
795
796 var interestingNumbers = [...]*BigInt{
797 new(BigInt).SetInt64(math.MinInt64).decr(),
798 new(BigInt).SetInt64(math.MinInt64),
799 new(BigInt).SetInt64(math.MinInt64).incr(),
800 new(BigInt).SetInt64(math.MinInt32),
801 new(BigInt).SetInt64(math.MinInt16),
802 new(BigInt).SetInt64(math.MinInt8),
803 new(BigInt).SetInt64(0),
804 new(BigInt).SetInt64(math.MaxInt8),
805 new(BigInt).SetInt64(math.MaxUint8),
806 new(BigInt).SetInt64(math.MaxInt16),
807 new(BigInt).SetInt64(math.MaxUint16),
808 new(BigInt).SetInt64(math.MaxInt32),
809 new(BigInt).SetInt64(math.MaxUint32),
810 new(BigInt).SetInt64(math.MaxInt64).decr(),
811 new(BigInt).SetInt64(math.MaxInt64),
812 new(BigInt).SetInt64(math.MaxInt64).incr(),
813 new(BigInt).SetUint64(math.MaxUint64).decr(),
814 new(BigInt).SetUint64(math.MaxUint64),
815 new(BigInt).SetUint64(math.MaxUint64).incr(),
816 }
817
818 func (number) generateInterestingNumber(r *rand.Rand) string {
819 return interestingNumbers[r.Intn(len(interestingNumbers))].String()
820 }
821
822 var numbers = [...]byte{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}
823
824 func (number) generateRandomNumber(r *rand.Rand, size int) string {
825 var s strings.Builder
826 if r.Intn(2) != 0 {
827 s.WriteByte('-')
828 }
829 digits := r.Intn(size) + 1
830 for i := 0; i < digits; i++ {
831 s.WriteByte(numbers[r.Intn(len(numbers))])
832 }
833 return s.String()
834 }
835
836 func (n number) toApd(t *testing.T) *BigInt {
837 var x BigInt
838 if _, ok := x.SetString(string(n), 10); !ok {
839 t.Fatalf("failed to SetString(%q)", n)
840 }
841 return &x
842 }
843
844 func (n number) toMath(t *testing.T) *big.Int {
845 var x big.Int
846 if _, ok := x.SetString(string(n), 10); !ok {
847 t.Fatalf("failed to SetString(%q)", n)
848 }
849 return &x
850 }
851
852 type numberOrNil struct {
853 Num number
854 Nil bool
855 }
856
857 func (n numberOrNil) toApd(t *testing.T) *BigInt {
858 if n.Nil {
859 return nil
860 }
861 return n.Num.toApd(t)
862 }
863
864 func (n numberOrNil) toMath(t *testing.T) *big.Int {
865 if n.Nil {
866 return nil
867 }
868 return n.Num.toMath(t)
869 }
870
871
872 func require(t *testing.T, err error) {
873 if err != nil {
874 t.Error(err)
875 }
876 }
877
878
879
880
881
882
883
884
885
886 type funZZ func(z, x, y *BigInt) *BigInt
887 type argZZ struct {
888 z, x, y *BigInt
889 }
890
891 var sumZZ = []argZZ{
892 {NewBigInt(0), NewBigInt(0), NewBigInt(0)},
893 {NewBigInt(1), NewBigInt(1), NewBigInt(0)},
894 {NewBigInt(1111111110), NewBigInt(123456789), NewBigInt(987654321)},
895 {NewBigInt(-1), NewBigInt(-1), NewBigInt(0)},
896 {NewBigInt(864197532), NewBigInt(-123456789), NewBigInt(987654321)},
897 {NewBigInt(-1111111110), NewBigInt(-123456789), NewBigInt(-987654321)},
898 }
899
900 var prodZZ = []argZZ{
901 {NewBigInt(0), NewBigInt(0), NewBigInt(0)},
902 {NewBigInt(0), NewBigInt(1), NewBigInt(0)},
903 {NewBigInt(1), NewBigInt(1), NewBigInt(1)},
904 {NewBigInt(-991 * 991), NewBigInt(991), NewBigInt(-991)},
905
906 }
907
908 func TestBigIntSignZ(t *testing.T) {
909 var zero BigInt
910 for _, a := range sumZZ {
911 s := a.z.Sign()
912 e := a.z.Cmp(&zero)
913 if s != e {
914 t.Errorf("got %d; want %d for z = %v", s, e, a.z)
915 }
916 }
917 }
918
919 func TestBigIntSetZ(t *testing.T) {
920 for _, a := range sumZZ {
921 var z BigInt
922 z.Set(a.z)
923 if (&z).Cmp(a.z) != 0 {
924 t.Errorf("got z = %v; want %v", &z, a.z)
925 }
926 }
927 }
928
929 func TestBigIntAbsZ(t *testing.T) {
930 var zero BigInt
931 for _, a := range sumZZ {
932 var z BigInt
933 z.Abs(a.z)
934 var e BigInt
935 e.Set(a.z)
936 if e.Cmp(&zero) < 0 {
937 e.Sub(&zero, &e)
938 }
939 if z.Cmp(&e) != 0 {
940 t.Errorf("got z = %v; want %v", &z, &e)
941 }
942 }
943 }
944
945 func testFunZZ(t *testing.T, msg string, f funZZ, a argZZ) {
946 var z BigInt
947 f(&z, a.x, a.y)
948 if (&z).Cmp(a.z) != 0 {
949 t.Errorf("%s%+v\n\tgot z = %v; want %v", msg, a, &z, a.z)
950 }
951 }
952
953 func TestBigIntSumZZ(t *testing.T) {
954 AddZZ := func(z, x, y *BigInt) *BigInt { return z.Add(x, y) }
955 SubZZ := func(z, x, y *BigInt) *BigInt { return z.Sub(x, y) }
956 for _, a := range sumZZ {
957 arg := a
958 testFunZZ(t, "AddZZ", AddZZ, arg)
959
960 arg = argZZ{a.z, a.y, a.x}
961 testFunZZ(t, "AddZZ symmetric", AddZZ, arg)
962
963 arg = argZZ{a.x, a.z, a.y}
964 testFunZZ(t, "SubZZ", SubZZ, arg)
965
966 arg = argZZ{a.y, a.z, a.x}
967 testFunZZ(t, "SubZZ symmetric", SubZZ, arg)
968 }
969 }
970
971 func TestBigIntProdZZ(t *testing.T) {
972 MulZZ := func(z, x, y *BigInt) *BigInt { return z.Mul(x, y) }
973 for _, a := range prodZZ {
974 arg := a
975 testFunZZ(t, "MulZZ", MulZZ, arg)
976
977 arg = argZZ{a.z, a.y, a.x}
978 testFunZZ(t, "MulZZ symmetric", MulZZ, arg)
979 }
980 }
981
982
983
984
985 func mulBytes(x, y []byte) []byte {
986 z := make([]byte, len(x)+len(y))
987
988
989 k0 := len(z) - 1
990 for j := len(y) - 1; j >= 0; j-- {
991 d := int(y[j])
992 if d != 0 {
993 k := k0
994 carry := 0
995 for i := len(x) - 1; i >= 0; i-- {
996 t := int(z[k]) + int(x[i])*d + carry
997 z[k], carry = byte(t), t>>8
998 k--
999 }
1000 z[k] = byte(carry)
1001 }
1002 k0--
1003 }
1004
1005
1006 i := 0
1007 for i < len(z) && z[i] == 0 {
1008 i++
1009 }
1010
1011 return z[i:]
1012 }
1013
1014 func checkMul(a, b []byte) bool {
1015 var x, y, z1 BigInt
1016 x.SetBytes(a)
1017 y.SetBytes(b)
1018 z1.Mul(&x, &y)
1019
1020 var z2 BigInt
1021 z2.SetBytes(mulBytes(a, b))
1022
1023 return z1.Cmp(&z2) == 0
1024 }
1025
1026 func TestBigIntMul(t *testing.T) {
1027 if err := quick.Check(checkMul, nil); err != nil {
1028 t.Error(err)
1029 }
1030 }
1031
1032 var mulRangesN = []struct {
1033 a, b uint64
1034 prod string
1035 }{
1036 {0, 0, "0"},
1037 {1, 1, "1"},
1038 {1, 2, "2"},
1039 {1, 3, "6"},
1040 {10, 10, "10"},
1041 {0, 100, "0"},
1042 {0, 1e9, "0"},
1043 {1, 0, "1"},
1044 {100, 1, "1"},
1045 {1, 10, "3628800"},
1046 {1, 20, "2432902008176640000"},
1047 {1, 100,
1048 "933262154439441526816992388562667004907159682643816214685929" +
1049 "638952175999932299156089414639761565182862536979208272237582" +
1050 "51185210916864000000000000000000000000",
1051 },
1052 }
1053
1054 var mulRangesZ = []struct {
1055 a, b int64
1056 prod string
1057 }{
1058
1059 {-1, 1, "0"},
1060 {-2, -1, "2"},
1061 {-3, -2, "6"},
1062 {-3, -1, "-6"},
1063 {1, 3, "6"},
1064 {-10, -10, "-10"},
1065 {0, -1, "1"},
1066 {-1, -100, "1"},
1067 {-1, 1, "0"},
1068 {-1e9, 0, "0"},
1069 {-1e9, 1e9, "0"},
1070 {-10, -1, "3628800"},
1071 {-20, -2, "-2432902008176640000"},
1072 {-99, -1,
1073 "-933262154439441526816992388562667004907159682643816214685929" +
1074 "638952175999932299156089414639761565182862536979208272237582" +
1075 "511852109168640000000000000000000000",
1076 },
1077 }
1078
1079 func TestBigIntMulRangeZ(t *testing.T) {
1080 var tmp BigInt
1081
1082 for i, r := range mulRangesN {
1083 prod := tmp.MulRange(int64(r.a), int64(r.b)).String()
1084 if prod != r.prod {
1085 t.Errorf("#%da: got %s; want %s", i, prod, r.prod)
1086 }
1087 }
1088
1089 for i, r := range mulRangesZ {
1090 prod := tmp.MulRange(r.a, r.b).String()
1091 if prod != r.prod {
1092 t.Errorf("#%db: got %s; want %s", i, prod, r.prod)
1093 }
1094 }
1095 }
1096
1097 func TestBigIntBinomial(t *testing.T) {
1098 var z BigInt
1099 for _, test := range []struct {
1100 n, k int64
1101 want string
1102 }{
1103 {0, 0, "1"},
1104 {0, 1, "0"},
1105 {1, 0, "1"},
1106 {1, 1, "1"},
1107 {1, 10, "0"},
1108 {4, 0, "1"},
1109 {4, 1, "4"},
1110 {4, 2, "6"},
1111 {4, 3, "4"},
1112 {4, 4, "1"},
1113 {10, 1, "10"},
1114 {10, 9, "10"},
1115 {10, 5, "252"},
1116 {11, 5, "462"},
1117 {11, 6, "462"},
1118 {100, 10, "17310309456440"},
1119 {100, 90, "17310309456440"},
1120 {1000, 10, "263409560461970212832400"},
1121 {1000, 990, "263409560461970212832400"},
1122 } {
1123 if got := z.Binomial(test.n, test.k).String(); got != test.want {
1124 t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
1125 }
1126 }
1127 }
1128
1129
1130 var divisionSignsTests = []struct {
1131 x, y int64
1132 q, r int64
1133 d, m int64
1134 }{
1135 {5, 3, 1, 2, 1, 2},
1136 {-5, 3, -1, -2, -2, 1},
1137 {5, -3, -1, 2, -1, 2},
1138 {-5, -3, 1, -2, 2, 1},
1139 {1, 2, 0, 1, 0, 1},
1140 {8, 4, 2, 0, 2, 0},
1141 }
1142
1143 func TestBigIntDivisionSigns(t *testing.T) {
1144 for i, test := range divisionSignsTests {
1145 x := NewBigInt(test.x)
1146 y := NewBigInt(test.y)
1147 q := NewBigInt(test.q)
1148 r := NewBigInt(test.r)
1149 d := NewBigInt(test.d)
1150 m := NewBigInt(test.m)
1151
1152 q1 := new(BigInt).Quo(x, y)
1153 r1 := new(BigInt).Rem(x, y)
1154 if q1.Cmp(q) != 0 || r1.Cmp(r) != 0 {
1155 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q1, r1, q, r)
1156 }
1157
1158 q2, r2 := new(BigInt).QuoRem(x, y, new(BigInt))
1159 if q2.Cmp(q) != 0 || r2.Cmp(r) != 0 {
1160 t.Errorf("#%d QuoRem: got (%s, %s), want (%s, %s)", i, q2, r2, q, r)
1161 }
1162
1163 d1 := new(BigInt).Div(x, y)
1164 m1 := new(BigInt).Mod(x, y)
1165 if d1.Cmp(d) != 0 || m1.Cmp(m) != 0 {
1166 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d1, m1, d, m)
1167 }
1168
1169 d2, m2 := new(BigInt).DivMod(x, y, new(BigInt))
1170 if d2.Cmp(d) != 0 || m2.Cmp(m) != 0 {
1171 t.Errorf("#%d DivMod: got (%s, %s), want (%s, %s)", i, d2, m2, d, m)
1172 }
1173 }
1174 }
1175
1176 func checkSetBytes(b []byte) bool {
1177 hex1 := hex.EncodeToString(new(BigInt).SetBytes(b).Bytes())
1178 hex2 := hex.EncodeToString(b)
1179
1180 for len(hex1) < len(hex2) {
1181 hex1 = "0" + hex1
1182 }
1183
1184 for len(hex1) > len(hex2) {
1185 hex2 = "0" + hex2
1186 }
1187
1188 return hex1 == hex2
1189 }
1190
1191 func TestBigIntSetBytes(t *testing.T) {
1192 if err := quick.Check(checkSetBytes, nil); err != nil {
1193 t.Error(err)
1194 }
1195 }
1196
1197 func checkBytes(b []byte) bool {
1198
1199
1200 for len(b) > 0 && b[0] == 0 {
1201 b = b[1:]
1202 }
1203 b2 := new(BigInt).SetBytes(b).Bytes()
1204 return bytes.Equal(b, b2)
1205 }
1206
1207 func TestBigIntBytes(t *testing.T) {
1208 if err := quick.Check(checkBytes, nil); err != nil {
1209 t.Error(err)
1210 }
1211 }
1212
1213 func checkQuo(x, y []byte) bool {
1214 u := new(BigInt).SetBytes(x)
1215 v := new(BigInt).SetBytes(y)
1216
1217 var tmp1 big.Int
1218 if len(v.inner(&tmp1).Bits()) == 0 {
1219 return true
1220 }
1221
1222 r := new(BigInt)
1223 q, r := new(BigInt).QuoRem(u, v, r)
1224
1225 if r.Cmp(v) >= 0 {
1226 return false
1227 }
1228
1229 uprime := new(BigInt).Set(q)
1230 uprime.Mul(uprime, v)
1231 uprime.Add(uprime, r)
1232
1233 return uprime.Cmp(u) == 0
1234 }
1235
1236 var quoTests = []struct {
1237 x, y string
1238 q, r string
1239 }{
1240 {
1241 "476217953993950760840509444250624797097991362735329973741718102894495832294430498335824897858659711275234906400899559094370964723884706254265559534144986498357",
1242 "9353930466774385905609975137998169297361893554149986716853295022578535724979483772383667534691121982974895531435241089241440253066816724367338287092081996",
1243 "50911",
1244 "1",
1245 },
1246 {
1247 "11510768301994997771168",
1248 "1328165573307167369775",
1249 "8",
1250 "885443715537658812968",
1251 },
1252 }
1253
1254 func TestBigIntQuo(t *testing.T) {
1255 if err := quick.Check(checkQuo, nil); err != nil {
1256 t.Error(err)
1257 }
1258
1259 for i, test := range quoTests {
1260 x, _ := new(BigInt).SetString(test.x, 10)
1261 y, _ := new(BigInt).SetString(test.y, 10)
1262 expectedQ, _ := new(BigInt).SetString(test.q, 10)
1263 expectedR, _ := new(BigInt).SetString(test.r, 10)
1264
1265 r := new(BigInt)
1266 q, r := new(BigInt).QuoRem(x, y, r)
1267
1268 if q.Cmp(expectedQ) != 0 || r.Cmp(expectedR) != 0 {
1269 t.Errorf("#%d got (%s, %s) want (%s, %s)", i, q, r, expectedQ, expectedR)
1270 }
1271 }
1272 }
1273
1274 var bitLenTests = []struct {
1275 in string
1276 out int
1277 }{
1278 {"-1", 1},
1279 {"0", 0},
1280 {"1", 1},
1281 {"2", 2},
1282 {"4", 3},
1283 {"0xabc", 12},
1284 {"0x8000", 16},
1285 {"0x80000000", 32},
1286 {"0x800000000000", 48},
1287 {"0x8000000000000000", 64},
1288 {"0x80000000000000000000", 80},
1289 {"-0x4000000000000000000000", 87},
1290 }
1291
1292 func TestBigIntBitLen(t *testing.T) {
1293 for i, test := range bitLenTests {
1294 x, ok := new(BigInt).SetString(test.in, 0)
1295 if !ok {
1296 t.Errorf("#%d test input invalid: %s", i, test.in)
1297 continue
1298 }
1299
1300 if n := x.BitLen(); n != test.out {
1301 t.Errorf("#%d got %d want %d", i, n, test.out)
1302 }
1303 }
1304 }
1305
1306 var expTests = []struct {
1307 x, y, m string
1308 out string
1309 }{
1310
1311 {"0", "0", "", "1"},
1312 {"1", "0", "", "1"},
1313 {"-10", "0", "", "1"},
1314 {"1234", "-1", "", "1"},
1315 {"1234", "-1", "0", "1"},
1316 {"17", "-100", "1234", "865"},
1317 {"2", "-100", "1234", ""},
1318
1319
1320 {"0", "0", "1", "0"},
1321 {"1", "0", "1", "0"},
1322 {"-10", "0", "1", "0"},
1323 {"1234", "-1", "1", "0"},
1324
1325
1326 {"5", "1", "3", "2"},
1327 {"5", "-7", "", "1"},
1328 {"-5", "-7", "", "1"},
1329 {"5", "0", "", "1"},
1330 {"-5", "0", "", "1"},
1331 {"5", "1", "", "5"},
1332 {"-5", "1", "", "-5"},
1333 {"-5", "1", "7", "2"},
1334 {"-2", "3", "2", "0"},
1335 {"5", "2", "", "25"},
1336 {"1", "65537", "2", "1"},
1337 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
1338 {"0x8000000000000000", "2", "6719", "4944"},
1339 {"0x8000000000000000", "3", "6719", "5447"},
1340 {"0x8000000000000000", "1000", "6719", "1603"},
1341 {"0x8000000000000000", "1000000", "6719", "3199"},
1342 {"0x8000000000000000", "-1000000", "6719", "3663"},
1343
1344 {"0xffffffffffffffffffffffffffffffff", "0x12345678123456781234567812345678123456789", "0x01112222333344445555666677778889", "0x36168FA1DB3AAE6C8CE647E137F97A"},
1345
1346 {
1347 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
1348 "298472983472983471903246121093472394872319615612417471234712061",
1349 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
1350 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
1351 },
1352
1353 {
1354 "11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865",
1355 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
1356 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
1357 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
1358 },
1359 {
1360 "-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B74DBD18FEC316AEF73985CF0475663208EB46B4F17DD9DA55367B03323E5491A70997B90C059FB34809E6EE55BCFBD5F2F52233BFE62E6AA9E4E26A1D4C2439883D14F2633D55D8AA66A1ACD5595E778AC3A280517F1157989E70C1A437B849F1877B779CC3CDDEDE2DAA6594A6C66D181A00A5F777EE60596D8773998F6E988DEAE4CCA60E4DDCF9590543C89F74F603259FCAD71660D30294FBBE6490300F78A9D63FA660DC9417B8B9DDA28BEB3977B621B988E23D4D954F322C3540541BC649ABD504C50FADFD9F0987D58A2BF689313A285E773FF02899A6EF887D1D4A0D2",
1361 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
1362 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
1363 "21484252197776302499639938883777710321993113097987201050501182909581359357618579566746556372589385361683610524730509041328855066514963385522570894839035884713051640171474186548713546686476761306436434146475140156284389181808675016576845833340494848283681088886584219750554408060556769486628029028720727393293111678826356480455433909233520504112074401376133077150471237549474149190242010469539006449596611576612573955754349042329130631128234637924786466585703488460540228477440853493392086251021228087076124706778899179648655221663765993962724699135217212118535057766739392069738618682722216712319320435674779146070442",
1364 },
1365
1366
1367 {"0xffffffff00000001", "0xffffffff00000001", "0xffffffff00000001", "0"},
1368 {"0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0xffffffffffffffff00000001", "0"},
1369 {"0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffff00000001", "0"},
1370 {"0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0xffffffffffffffffffffffffffffffff00000001", "0"},
1371
1372 {
1373 "2",
1374 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
1375 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73",
1376 "0x6AADD3E3E424D5B713FCAA8D8945B1E055166132038C57BBD2D51C833F0C5EA2007A2324CE514F8E8C2F008A2F36F44005A4039CB55830986F734C93DAF0EB4BAB54A6A8C7081864F44346E9BC6F0A3EB9F2C0146A00C6A05187D0C101E1F2D038CDB70CB5E9E05A2D188AB6CBB46286624D4415E7D4DBFAD3BCC6009D915C406EED38F468B940F41E6BEDC0430DD78E6F19A7DA3A27498A4181E24D738B0072D8F6ADB8C9809A5B033A09785814FD9919F6EF9F83EEA519BEC593855C4C10CBEEC582D4AE0792158823B0275E6AEC35242740468FAF3D5C60FD1E376362B6322F78B7ED0CA1C5BBCD2B49734A56C0967A1D01A100932C837B91D592CE08ABFF",
1377 },
1378 {
1379 "2",
1380 "0xB08FFB20760FFED58FADA86DFEF71AD72AA0FA763219618FE022C197E54708BB1191C66470250FCE8879487507CEE41381CA4D932F81C2B3F1AB20B539D50DCD",
1381 "0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72",
1382 "0x7858794B5897C29F4ED0B40913416AB6C48588484E6A45F2ED3E26C941D878E923575AAC434EE2750E6439A6976F9BB4D64CEDB2A53CE8D04DD48CADCDF8E46F22747C6B81C6CEA86C0D873FBF7CEF262BAAC43A522BD7F32F3CDAC52B9337C77B3DCFB3DB3EDD80476331E82F4B1DF8EFDC1220C92656DFC9197BDC1877804E28D928A2A284B8DED506CBA304435C9D0133C246C98A7D890D1DE60CBC53A024361DA83A9B8775019083D22AC6820ED7C3C68F8E801DD4EC779EE0A05C6EB682EF9840D285B838369BA7E148FA27691D524FAEAF7C6ECE2A4B99A294B9F2C241857B5B90CC8BFFCFCF18DFA7D676131D5CD3855A5A3E8EBFA0CDFADB4D198B4A",
1383 },
1384 }
1385
1386 func TestBigIntExp(t *testing.T) {
1387 for i, test := range expTests {
1388 x, ok1 := new(BigInt).SetString(test.x, 0)
1389 y, ok2 := new(BigInt).SetString(test.y, 0)
1390
1391 var ok3, ok4 bool
1392 var out, m *BigInt
1393
1394 if len(test.out) == 0 {
1395 out, ok3 = nil, true
1396 } else {
1397 out, ok3 = new(BigInt).SetString(test.out, 0)
1398 }
1399
1400 if len(test.m) == 0 {
1401 m, ok4 = nil, true
1402 } else {
1403 m, ok4 = new(BigInt).SetString(test.m, 0)
1404 }
1405
1406 if !ok1 || !ok2 || !ok3 || !ok4 {
1407 t.Errorf("#%d: error in input", i)
1408 continue
1409 }
1410
1411 z1 := new(BigInt).Exp(x, y, m)
1412 if !(z1 == nil && out == nil || z1.Cmp(out) == 0) {
1413 t.Errorf("#%d: got %x want %x", i, z1, out)
1414 }
1415
1416 if m == nil {
1417
1418
1419 m = new(BigInt)
1420 z2 := new(BigInt).Exp(x, y, m)
1421 if z2.Cmp(z1) != 0 {
1422 t.Errorf("#%d: got %x want %x", i, z2, z1)
1423 }
1424 }
1425 }
1426 }
1427
1428 type intShiftTest struct {
1429 in string
1430 shift uint
1431 out string
1432 }
1433
1434 var rshTests = []intShiftTest{
1435 {"0", 0, "0"},
1436 {"-0", 0, "0"},
1437 {"0", 1, "0"},
1438 {"0", 2, "0"},
1439 {"1", 0, "1"},
1440 {"1", 1, "0"},
1441 {"1", 2, "0"},
1442 {"2", 0, "2"},
1443 {"2", 1, "1"},
1444 {"-1", 0, "-1"},
1445 {"-1", 1, "-1"},
1446 {"-1", 10, "-1"},
1447 {"-100", 2, "-25"},
1448 {"-100", 3, "-13"},
1449 {"-100", 100, "-1"},
1450 {"4294967296", 0, "4294967296"},
1451 {"4294967296", 1, "2147483648"},
1452 {"4294967296", 2, "1073741824"},
1453 {"18446744073709551616", 0, "18446744073709551616"},
1454 {"18446744073709551616", 1, "9223372036854775808"},
1455 {"18446744073709551616", 2, "4611686018427387904"},
1456 {"18446744073709551616", 64, "1"},
1457 {"340282366920938463463374607431768211456", 64, "18446744073709551616"},
1458 {"340282366920938463463374607431768211456", 128, "1"},
1459 }
1460
1461 func TestBigIntRsh(t *testing.T) {
1462 for i, test := range rshTests {
1463 in, _ := new(BigInt).SetString(test.in, 10)
1464 expected, _ := new(BigInt).SetString(test.out, 10)
1465 out := new(BigInt).Rsh(in, test.shift)
1466
1467 if out.Cmp(expected) != 0 {
1468 t.Errorf("#%d: got %s want %s", i, out, expected)
1469 }
1470 }
1471 }
1472
1473 func TestBigIntRshSelf(t *testing.T) {
1474 for i, test := range rshTests {
1475 z, _ := new(BigInt).SetString(test.in, 10)
1476 expected, _ := new(BigInt).SetString(test.out, 10)
1477 z.Rsh(z, test.shift)
1478
1479 if z.Cmp(expected) != 0 {
1480 t.Errorf("#%d: got %s want %s", i, z, expected)
1481 }
1482 }
1483 }
1484
1485 var lshTests = []intShiftTest{
1486 {"0", 0, "0"},
1487 {"0", 1, "0"},
1488 {"0", 2, "0"},
1489 {"1", 0, "1"},
1490 {"1", 1, "2"},
1491 {"1", 2, "4"},
1492 {"2", 0, "2"},
1493 {"2", 1, "4"},
1494 {"2", 2, "8"},
1495 {"-87", 1, "-174"},
1496 {"4294967296", 0, "4294967296"},
1497 {"4294967296", 1, "8589934592"},
1498 {"4294967296", 2, "17179869184"},
1499 {"18446744073709551616", 0, "18446744073709551616"},
1500 {"9223372036854775808", 1, "18446744073709551616"},
1501 {"4611686018427387904", 2, "18446744073709551616"},
1502 {"1", 64, "18446744073709551616"},
1503 {"18446744073709551616", 64, "340282366920938463463374607431768211456"},
1504 {"1", 128, "340282366920938463463374607431768211456"},
1505 }
1506
1507 func TestBigIntLsh(t *testing.T) {
1508 for i, test := range lshTests {
1509 in, _ := new(BigInt).SetString(test.in, 10)
1510 expected, _ := new(BigInt).SetString(test.out, 10)
1511 out := new(BigInt).Lsh(in, test.shift)
1512
1513 if out.Cmp(expected) != 0 {
1514 t.Errorf("#%d: got %s want %s", i, out, expected)
1515 }
1516 }
1517 }
1518
1519 func TestBigIntLshSelf(t *testing.T) {
1520 for i, test := range lshTests {
1521 z, _ := new(BigInt).SetString(test.in, 10)
1522 expected, _ := new(BigInt).SetString(test.out, 10)
1523 z.Lsh(z, test.shift)
1524
1525 if z.Cmp(expected) != 0 {
1526 t.Errorf("#%d: got %s want %s", i, z, expected)
1527 }
1528 }
1529 }
1530
1531 func TestBigIntLshRsh(t *testing.T) {
1532 for i, test := range rshTests {
1533 in, _ := new(BigInt).SetString(test.in, 10)
1534 out := new(BigInt).Lsh(in, test.shift)
1535 out = out.Rsh(out, test.shift)
1536
1537 if in.Cmp(out) != 0 {
1538 t.Errorf("#%d: got %s want %s", i, out, in)
1539 }
1540 }
1541 for i, test := range lshTests {
1542 in, _ := new(BigInt).SetString(test.in, 10)
1543 out := new(BigInt).Lsh(in, test.shift)
1544 out.Rsh(out, test.shift)
1545
1546 if in.Cmp(out) != 0 {
1547 t.Errorf("#%d: got %s want %s", i, out, in)
1548 }
1549 }
1550 }
1551
1552
1553 var cmpAbsTests = []string{
1554 "0",
1555 "1",
1556 "2",
1557 "10",
1558 "10000000",
1559 "2783678367462374683678456387645876387564783686583485",
1560 "2783678367462374683678456387645876387564783686583486",
1561 "32957394867987420967976567076075976570670947609750670956097509670576075067076027578341538",
1562 }
1563
1564 func TestBigIntCmpAbs(t *testing.T) {
1565 values := make([]*BigInt, len(cmpAbsTests))
1566 var prev *BigInt
1567 for i, s := range cmpAbsTests {
1568 x, ok := new(BigInt).SetString(s, 0)
1569 if !ok {
1570 t.Fatalf("SetString(%s, 0) failed", s)
1571 }
1572 if prev != nil && prev.Cmp(x) >= 0 {
1573 t.Fatal("cmpAbsTests entries not sorted in ascending order")
1574 }
1575 values[i] = x
1576 prev = x
1577 }
1578
1579 for i, x := range values {
1580 for j, y := range values {
1581
1582 for k := 0; k < 4; k++ {
1583 var a, b BigInt
1584 a.Set(x)
1585 b.Set(y)
1586 if k&1 != 0 {
1587 a.Neg(&a)
1588 }
1589 if k&2 != 0 {
1590 b.Neg(&b)
1591 }
1592
1593 got := a.CmpAbs(&b)
1594 want := 0
1595 switch {
1596 case i > j:
1597 want = 1
1598 case i < j:
1599 want = -1
1600 }
1601 if got != want {
1602 t.Errorf("absCmp |%s|, |%s|: got %d; want %d", &a, &b, got, want)
1603 }
1604 }
1605 }
1606 }
1607 }
1608
1609 func TestBigIntCmpSelf(t *testing.T) {
1610 for _, s := range cmpAbsTests {
1611 x, ok := new(BigInt).SetString(s, 0)
1612 if !ok {
1613 t.Fatalf("SetString(%s, 0) failed", s)
1614 }
1615 got := x.Cmp(x)
1616 want := 0
1617 if got != want {
1618 t.Errorf("x = %s: x.Cmp(x): got %d; want %d", x, got, want)
1619 }
1620 }
1621 }
1622
1623 var int64Tests = []string{
1624
1625 "0",
1626 "1",
1627 "-1",
1628 "4294967295",
1629 "-4294967295",
1630 "4294967296",
1631 "-4294967296",
1632 "9223372036854775807",
1633 "-9223372036854775807",
1634 "-9223372036854775808",
1635
1636
1637 "0x8000000000000000",
1638 "-0x8000000000000001",
1639 "38579843757496759476987459679745",
1640 "-38579843757496759476987459679745",
1641 }
1642
1643 func TestBigInt64(t *testing.T) {
1644 for _, s := range int64Tests {
1645 var x BigInt
1646 _, ok := x.SetString(s, 0)
1647 if !ok {
1648 t.Errorf("SetString(%s, 0) failed", s)
1649 continue
1650 }
1651
1652 want, err := strconv.ParseInt(s, 0, 64)
1653 if err != nil {
1654 if err.(*strconv.NumError).Err == strconv.ErrRange {
1655 if x.IsInt64() {
1656 t.Errorf("IsInt64(%s) succeeded unexpectedly", s)
1657 }
1658 } else {
1659 t.Errorf("ParseInt(%s) failed", s)
1660 }
1661 continue
1662 }
1663
1664 if !x.IsInt64() {
1665 t.Errorf("IsInt64(%s) failed unexpectedly", s)
1666 }
1667
1668 got := x.Int64()
1669 if got != want {
1670 t.Errorf("Int64(%s) = %d; want %d", s, got, want)
1671 }
1672 }
1673 }
1674
1675 var uint64Tests = []string{
1676
1677 "0",
1678 "1",
1679 "4294967295",
1680 "4294967296",
1681 "8589934591",
1682 "8589934592",
1683 "9223372036854775807",
1684 "9223372036854775808",
1685 "0x08000000000000000",
1686
1687
1688 "0x10000000000000000",
1689 "-0x08000000000000000",
1690 "-1",
1691 }
1692
1693 func TestBigIntUint64(t *testing.T) {
1694 for _, s := range uint64Tests {
1695 var x BigInt
1696 _, ok := x.SetString(s, 0)
1697 if !ok {
1698 t.Errorf("SetString(%s, 0) failed", s)
1699 continue
1700 }
1701
1702 want, err := strconv.ParseUint(s, 0, 64)
1703 if err != nil {
1704
1705 if s[0] == '-' || err.(*strconv.NumError).Err == strconv.ErrRange {
1706 if x.IsUint64() {
1707 t.Errorf("IsUint64(%s) succeeded unexpectedly", s)
1708 }
1709 } else {
1710 t.Errorf("ParseUint(%s) failed", s)
1711 }
1712 continue
1713 }
1714
1715 if !x.IsUint64() {
1716 t.Errorf("IsUint64(%s) failed unexpectedly", s)
1717 }
1718
1719 got := x.Uint64()
1720 if got != want {
1721 t.Errorf("Uint64(%s) = %d; want %d", s, got, want)
1722 }
1723 }
1724 }
1725
1726 var bitwiseTests = []struct {
1727 x, y string
1728 and, or, xor, andNot string
1729 }{
1730 {"0x00", "0x00", "0x00", "0x00", "0x00", "0x00"},
1731 {"0x00", "0x01", "0x00", "0x01", "0x01", "0x00"},
1732 {"0x01", "0x00", "0x00", "0x01", "0x01", "0x01"},
1733 {"-0x01", "0x00", "0x00", "-0x01", "-0x01", "-0x01"},
1734 {"-0xaf", "-0x50", "-0xf0", "-0x0f", "0xe1", "0x41"},
1735 {"0x00", "-0x01", "0x00", "-0x01", "-0x01", "0x00"},
1736 {"0x01", "0x01", "0x01", "0x01", "0x00", "0x00"},
1737 {"-0x01", "-0x01", "-0x01", "-0x01", "0x00", "0x00"},
1738 {"0x07", "0x08", "0x00", "0x0f", "0x0f", "0x07"},
1739 {"0x05", "0x0f", "0x05", "0x0f", "0x0a", "0x00"},
1740 {"0xff", "-0x0a", "0xf6", "-0x01", "-0xf7", "0x09"},
1741 {"0x013ff6", "0x9a4e", "0x1a46", "0x01bffe", "0x01a5b8", "0x0125b0"},
1742 {"-0x013ff6", "0x9a4e", "0x800a", "-0x0125b2", "-0x01a5bc", "-0x01c000"},
1743 {"-0x013ff6", "-0x9a4e", "-0x01bffe", "-0x1a46", "0x01a5b8", "0x8008"},
1744 {
1745 "0x1000009dc6e3d9822cba04129bcbe3401",
1746 "0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1747 "0x1000001186210100001000009048c2001",
1748 "0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1749 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1750 "0x8c40c2d8822caa04120b8321400",
1751 },
1752 {
1753 "0x1000009dc6e3d9822cba04129bcbe3401",
1754 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1755 "0x8c40c2d8822caa04120b8321401",
1756 "-0xb9bd7d543685789d57ca918e82229142459020483cd2014001fd",
1757 "-0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fe",
1758 "0x1000001186210100001000009048c2000",
1759 },
1760 {
1761 "-0x1000009dc6e3d9822cba04129bcbe3401",
1762 "-0xb9bd7d543685789d57cb918e833af352559021483cdb05cc21fd",
1763 "-0xb9bd7d543685789d57cb918e8bfeff7fddb2ebe87dfbbdfe35fd",
1764 "-0x1000001186210100001000009048c2001",
1765 "0xb9bd7d543685789d57ca918e8ae69d6fcdb2eae87df2b97215fc",
1766 "0xb9bd7d543685789d57ca918e82229142459020483cd2014001fc",
1767 },
1768 }
1769
1770 type bitFun func(z, x, y *BigInt) *BigInt
1771
1772 func testBitFun(t *testing.T, msg string, f bitFun, x, y *BigInt, exp string) {
1773 expected := new(BigInt)
1774 expected.SetString(exp, 0)
1775
1776 out := f(new(BigInt), x, y)
1777 if out.Cmp(expected) != 0 {
1778 t.Errorf("%s: got %s want %s", msg, out, expected)
1779 }
1780 }
1781
1782 func testBitFunSelf(t *testing.T, msg string, f bitFun, x, y *BigInt, exp string) {
1783 self := new(BigInt)
1784 self.Set(x)
1785 expected := new(BigInt)
1786 expected.SetString(exp, 0)
1787
1788 self = f(self, self, y)
1789 if self.Cmp(expected) != 0 {
1790 t.Errorf("%s: got %s want %s", msg, self, expected)
1791 }
1792 }
1793
1794 func altBit(x *BigInt, i int) uint {
1795 z := new(BigInt).Rsh(x, uint(i))
1796 z = z.And(z, NewBigInt(1))
1797 if z.Cmp(new(BigInt)) != 0 {
1798 return 1
1799 }
1800 return 0
1801 }
1802
1803 func altSetBit(z *BigInt, x *BigInt, i int, b uint) *BigInt {
1804 one := NewBigInt(1)
1805 m := one.Lsh(one, uint(i))
1806 switch b {
1807 case 1:
1808 return z.Or(x, m)
1809 case 0:
1810 return z.AndNot(x, m)
1811 }
1812 panic("set bit is not 0 or 1")
1813 }
1814
1815 func testBitset(t *testing.T, x *BigInt) {
1816 n := x.BitLen()
1817 z := new(BigInt).Set(x)
1818 z1 := new(BigInt).Set(x)
1819 for i := 0; i < n+10; i++ {
1820 old := z.Bit(i)
1821 old1 := altBit(z1, i)
1822 if old != old1 {
1823 t.Errorf("bitset: inconsistent value for Bit(%s, %d), got %v want %v", z1, i, old, old1)
1824 }
1825 z := new(BigInt).SetBit(z, i, 1)
1826 z1 := altSetBit(new(BigInt), z1, i, 1)
1827 if z.Bit(i) == 0 {
1828 t.Errorf("bitset: bit %d of %s got 0 want 1", i, x)
1829 }
1830 if z.Cmp(z1) != 0 {
1831 t.Errorf("bitset: inconsistent value after SetBit 1, got %s want %s", z, z1)
1832 }
1833 z.SetBit(z, i, 0)
1834 altSetBit(z1, z1, i, 0)
1835 if z.Bit(i) != 0 {
1836 t.Errorf("bitset: bit %d of %s got 1 want 0", i, x)
1837 }
1838 if z.Cmp(z1) != 0 {
1839 t.Errorf("bitset: inconsistent value after SetBit 0, got %s want %s", z, z1)
1840 }
1841 altSetBit(z1, z1, i, old)
1842 z.SetBit(z, i, old)
1843 if z.Cmp(z1) != 0 {
1844 t.Errorf("bitset: inconsistent value after SetBit old, got %s want %s", z, z1)
1845 }
1846 }
1847 if z.Cmp(x) != 0 {
1848 t.Errorf("bitset: got %s want %s", z, x)
1849 }
1850 }
1851
1852 var bitsetTests = []struct {
1853 x string
1854 i int
1855 b uint
1856 }{
1857 {"0", 0, 0},
1858 {"0", 200, 0},
1859 {"1", 0, 1},
1860 {"1", 1, 0},
1861 {"-1", 0, 1},
1862 {"-1", 200, 1},
1863 {"0x2000000000000000000000000000", 108, 0},
1864 {"0x2000000000000000000000000000", 109, 1},
1865 {"0x2000000000000000000000000000", 110, 0},
1866 {"-0x2000000000000000000000000001", 108, 1},
1867 {"-0x2000000000000000000000000001", 109, 0},
1868 {"-0x2000000000000000000000000001", 110, 1},
1869 }
1870
1871 func TestBigIntBitSet(t *testing.T) {
1872 for _, test := range bitwiseTests {
1873 x := new(BigInt)
1874 x.SetString(test.x, 0)
1875 testBitset(t, x)
1876 x = new(BigInt)
1877 x.SetString(test.y, 0)
1878 testBitset(t, x)
1879 }
1880 for i, test := range bitsetTests {
1881 x := new(BigInt)
1882 x.SetString(test.x, 0)
1883 b := x.Bit(test.i)
1884 if b != test.b {
1885 t.Errorf("#%d got %v want %v", i, b, test.b)
1886 }
1887 }
1888 z := NewBigInt(1)
1889 z.SetBit(NewBigInt(0), 2, 1)
1890 if z.Cmp(NewBigInt(4)) != 0 {
1891 t.Errorf("destination leaked into result; got %s want 4", z)
1892 }
1893 }
1894
1895 var tzbTests = []struct {
1896 in string
1897 out uint
1898 }{
1899 {"0", 0},
1900 {"1", 0},
1901 {"-1", 0},
1902 {"4", 2},
1903 {"-8", 3},
1904 {"0x4000000000000000000", 74},
1905 {"-0x8000000000000000000", 75},
1906 }
1907
1908 func TestBigIntTrailingZeroBits(t *testing.T) {
1909 for i, test := range tzbTests {
1910 in, _ := new(BigInt).SetString(test.in, 0)
1911 want := test.out
1912 got := in.TrailingZeroBits()
1913
1914 if got != want {
1915 t.Errorf("#%d: got %v want %v", i, got, want)
1916 }
1917 }
1918 }
1919
1920 func TestBigIntBitwise(t *testing.T) {
1921 x := new(BigInt)
1922 y := new(BigInt)
1923 for _, test := range bitwiseTests {
1924 x.SetString(test.x, 0)
1925 y.SetString(test.y, 0)
1926
1927 testBitFun(t, "and", (*BigInt).And, x, y, test.and)
1928 testBitFunSelf(t, "and", (*BigInt).And, x, y, test.and)
1929 testBitFun(t, "andNot", (*BigInt).AndNot, x, y, test.andNot)
1930 testBitFunSelf(t, "andNot", (*BigInt).AndNot, x, y, test.andNot)
1931 testBitFun(t, "or", (*BigInt).Or, x, y, test.or)
1932 testBitFunSelf(t, "or", (*BigInt).Or, x, y, test.or)
1933 testBitFun(t, "xor", (*BigInt).Xor, x, y, test.xor)
1934 testBitFunSelf(t, "xor", (*BigInt).Xor, x, y, test.xor)
1935 }
1936 }
1937
1938 var notTests = []struct {
1939 in string
1940 out string
1941 }{
1942 {"0", "-1"},
1943 {"1", "-2"},
1944 {"7", "-8"},
1945 {"0", "-1"},
1946 {"-81910", "81909"},
1947 {
1948 "298472983472983471903246121093472394872319615612417471234712061",
1949 "-298472983472983471903246121093472394872319615612417471234712062",
1950 },
1951 }
1952
1953 func TestBigIntNot(t *testing.T) {
1954 in := new(BigInt)
1955 out := new(BigInt)
1956 expected := new(BigInt)
1957 for i, test := range notTests {
1958 in.SetString(test.in, 10)
1959 expected.SetString(test.out, 10)
1960 out = out.Not(in)
1961 if out.Cmp(expected) != 0 {
1962 t.Errorf("#%d: got %s want %s", i, out, expected)
1963 }
1964 out = out.Not(out)
1965 if out.Cmp(in) != 0 {
1966 t.Errorf("#%d: got %s want %s", i, out, in)
1967 }
1968 }
1969 }
1970
1971 var modInverseTests = []struct {
1972 element string
1973 modulus string
1974 }{
1975 {"1234567", "458948883992"},
1976 {"239487239847", "2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919"},
1977 {"-10", "13"},
1978 {"10", "-13"},
1979 {"-17", "-13"},
1980 }
1981
1982 func TestBigIntModInverse(t *testing.T) {
1983 var element, modulus, gcd, inverse BigInt
1984 one := NewBigInt(1)
1985 for _, test := range modInverseTests {
1986 (&element).SetString(test.element, 10)
1987 (&modulus).SetString(test.modulus, 10)
1988 (&inverse).ModInverse(&element, &modulus)
1989 (&inverse).Mul(&inverse, &element)
1990 (&inverse).Mod(&inverse, &modulus)
1991 if (&inverse).Cmp(one) != 0 {
1992 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
1993 }
1994 }
1995
1996 for n := 2; n < 100; n++ {
1997 (&modulus).SetInt64(int64(n))
1998 for x := 1; x < n; x++ {
1999 (&element).SetInt64(int64(x))
2000 (&gcd).GCD(nil, nil, &element, &modulus)
2001 if (&gcd).Cmp(one) != 0 {
2002 continue
2003 }
2004 (&inverse).ModInverse(&element, &modulus)
2005 (&inverse).Mul(&inverse, &element)
2006 (&inverse).Mod(&inverse, &modulus)
2007 if (&inverse).Cmp(one) != 0 {
2008 t.Errorf("ModInverse(%d,%d)*%d%%%d=%d, not 1", &element, &modulus, &element, &modulus, &inverse)
2009 }
2010 }
2011 }
2012 }
2013
2014
2015
2016 func testModSqrt(t *testing.T, elt, mod, sq, sqrt *BigInt) bool {
2017 var sqChk, sqrtChk, sqrtsq BigInt
2018 sq.Mul(elt, elt)
2019 sq.Mod(sq, mod)
2020 z := sqrt.ModSqrt(sq, mod)
2021 if z != sqrt {
2022 t.Errorf("ModSqrt returned wrong value %s", z)
2023 }
2024
2025
2026 sqChk.Add(sq, mod)
2027 z = sqrtChk.ModSqrt(&sqChk, mod)
2028 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
2029 t.Errorf("ModSqrt returned inconsistent value %s", z)
2030 }
2031 sqChk.Sub(sq, mod)
2032 z = sqrtChk.ModSqrt(&sqChk, mod)
2033 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
2034 t.Errorf("ModSqrt returned inconsistent value %s", z)
2035 }
2036
2037
2038 z = sqrtChk.ModSqrt(sqrtChk.Set(sq), mod)
2039 if z != &sqrtChk || z.Cmp(sqrt) != 0 {
2040 t.Errorf("ModSqrt returned inconsistent value %s", z)
2041 }
2042
2043
2044 if sqrt.Cmp(elt) == 0 {
2045 return true
2046 }
2047 sqrtsq.Mul(sqrt, sqrt)
2048 sqrtsq.Mod(&sqrtsq, mod)
2049 return sq.Cmp(&sqrtsq) == 0
2050 }
2051
2052 var primes = []string{
2053 "2",
2054 "3",
2055 "5",
2056 "7",
2057 "11",
2058
2059 "13756265695458089029",
2060 "13496181268022124907",
2061 "10953742525620032441",
2062 "17908251027575790097",
2063
2064
2065 "18699199384836356663",
2066
2067 "98920366548084643601728869055592650835572950932266967461790948584315647051443",
2068 "94560208308847015747498523884063394671606671904944666360068158221458669711639",
2069
2070
2071 "449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163",
2072 "230975859993204150666423538988557839555560243929065415434980904258310530753006723857139742334640122533598517597674807096648905501653461687601339782814316124971547968912893214002992086353183070342498989426570593",
2073 "5521712099665906221540423207019333379125265462121169655563495403888449493493629943498064604536961775110765377745550377067893607246020694972959780839151452457728855382113555867743022746090187341871655890805971735385789993",
2074 "203956878356401977405765866929034577280193993314348263094772646453283062722701277632936616063144088173312372882677123879538709400158306567338328279154499698366071906766440037074217117805690872792848149112022286332144876183376326512083574821647933992961249917319836219304274280243803104015000563790123",
2075
2076
2077 "3618502788666131106986593281521497120414687020801267626233049500247285301239",
2078 "57896044618658097711785492504343953926634992332820282019728792003956564819949",
2079 "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599",
2080 "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367",
2081 "6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151",
2082 }
2083
2084 func TestBigIntModSqrt(t *testing.T) {
2085 var elt, mod, modx4, sq, sqrt BigInt
2086 r := rand.New(rand.NewSource(9))
2087 for i, s := range primes[1:] {
2088 mod.SetString(s, 10)
2089 modx4.Lsh(&mod, 2)
2090
2091
2092 for x := 1; x < 5; x++ {
2093 elt.Rand(r, &modx4)
2094 elt.Sub(&elt, &mod)
2095 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
2096 t.Errorf("#%d: failed (sqrt(e) = %s)", i, &sqrt)
2097 }
2098 }
2099
2100 if testing.Short() && i > 2 {
2101 break
2102 }
2103 }
2104
2105 if testing.Short() {
2106 return
2107 }
2108
2109
2110 for n := 3; n < 100; n++ {
2111 mod.SetInt64(int64(n))
2112 if !mod.ProbablyPrime(10) {
2113 continue
2114 }
2115 isSquare := make([]bool, n)
2116
2117
2118 for x := 1; x < n; x++ {
2119 elt.SetInt64(int64(x))
2120 if !testModSqrt(t, &elt, &mod, &sq, &sqrt) {
2121 t.Errorf("#%d: failed (sqrt(%d,%d) = %s)", x, &elt, &mod, &sqrt)
2122 }
2123 isSquare[sq.Uint64()] = true
2124 }
2125
2126
2127 for x := 1; x < n; x++ {
2128 sq.SetInt64(int64(x))
2129 z := sqrt.ModSqrt(&sq, &mod)
2130 if !isSquare[x] && z != nil {
2131 t.Errorf("#%d: failed (sqrt(%d,%d) = nil)", x, &sqrt, &mod)
2132 }
2133 }
2134 }
2135 }
2136
2137 func TestBigIntIssue2607(t *testing.T) {
2138
2139 n := NewBigInt(10)
2140 n.Rand(rand.New(rand.NewSource(9)), n)
2141 }
2142
2143 func TestBigIntSqrt(t *testing.T) {
2144 root := 0
2145 r := new(BigInt)
2146 for i := 0; i < 10000; i++ {
2147 if (root+1)*(root+1) <= i {
2148 root++
2149 }
2150 n := NewBigInt(int64(i))
2151 r.SetInt64(-2)
2152 r.Sqrt(n)
2153 if r.Cmp(NewBigInt(int64(root))) != 0 {
2154 t.Errorf("Sqrt(%v) = %v, want %v", n, r, root)
2155 }
2156 }
2157
2158 for i := 0; i < 1000; i += 10 {
2159 n, _ := new(BigInt).SetString("1"+strings.Repeat("0", i), 10)
2160 r := new(BigInt).Sqrt(n)
2161 root, _ := new(BigInt).SetString("1"+strings.Repeat("0", i/2), 10)
2162 if r.Cmp(root) != 0 {
2163 t.Errorf("Sqrt(1e%d) = %v, want 1e%d", i, r, i/2)
2164 }
2165 }
2166
2167
2168 r.SetInt64(100)
2169 r.Sqrt(r)
2170 if r.Int64() != 10 {
2171 t.Errorf("Sqrt(100) = %v, want 10 (aliased output)", r.Int64())
2172 }
2173 }
2174
2175
2176
2177 func TestBigIntIssue22830(t *testing.T) {
2178 one := new(BigInt).SetInt64(1)
2179 base, _ := new(BigInt).SetString("84555555300000000000", 10)
2180 mod, _ := new(BigInt).SetString("66666670001111111111", 10)
2181 want, _ := new(BigInt).SetString("17888885298888888889", 10)
2182
2183 var tests = []int64{
2184 0, 1, -1,
2185 }
2186
2187 for _, n := range tests {
2188 m := NewBigInt(n)
2189 if got := m.Exp(base, one, mod); got.Cmp(want) != 0 {
2190 t.Errorf("(%v).Exp(%s, 1, %s) = %s, want %s", n, base, mod, got, want)
2191 }
2192 }
2193 }
2194
2195
2196
2197
2198
2199 var stringTests = []struct {
2200 in string
2201 out string
2202 base int
2203 val int64
2204 ok bool
2205 }{
2206
2207 {in: ""},
2208 {in: "a"},
2209 {in: "z"},
2210 {in: "+"},
2211 {in: "-"},
2212 {in: "0b"},
2213 {in: "0o"},
2214 {in: "0x"},
2215 {in: "0y"},
2216 {in: "2", base: 2},
2217 {in: "0b2", base: 0},
2218 {in: "08"},
2219 {in: "8", base: 8},
2220 {in: "0xg", base: 0},
2221 {in: "g", base: 16},
2222
2223
2224
2225 {in: "_"},
2226 {in: "0_"},
2227 {in: "_0"},
2228 {in: "-1__0"},
2229 {in: "0x10_"},
2230 {in: "1_000", base: 10},
2231 {in: "d_e_a_d", base: 16},
2232
2233
2234 {"0", "0", 0, 0, true},
2235 {"0", "0", 10, 0, true},
2236 {"0", "0", 16, 0, true},
2237 {"+0", "0", 0, 0, true},
2238 {"-0", "0", 0, 0, true},
2239 {"10", "10", 0, 10, true},
2240 {"10", "10", 10, 10, true},
2241 {"10", "10", 16, 16, true},
2242 {"-10", "-10", 16, -16, true},
2243 {"+10", "10", 16, 16, true},
2244 {"0b10", "2", 0, 2, true},
2245 {"0o10", "8", 0, 8, true},
2246 {"0x10", "16", 0, 16, true},
2247 {in: "0x10", base: 16},
2248 {"-0x10", "-16", 0, -16, true},
2249 {"+0x10", "16", 0, 16, true},
2250 {"00", "0", 0, 0, true},
2251 {"0", "0", 8, 0, true},
2252 {"07", "7", 0, 7, true},
2253 {"7", "7", 8, 7, true},
2254 {"023", "19", 0, 19, true},
2255 {"23", "23", 8, 19, true},
2256 {"cafebabe", "cafebabe", 16, 0xcafebabe, true},
2257 {"0b0", "0", 0, 0, true},
2258 {"-111", "-111", 2, -7, true},
2259 {"-0b111", "-7", 0, -7, true},
2260 {"0b1001010111", "599", 0, 0x257, true},
2261 {"1001010111", "1001010111", 2, 0x257, true},
2262 {"A", "a", 36, 10, true},
2263 {"A", "A", 37, 36, true},
2264 {"ABCXYZ", "abcxyz", 36, 623741435, true},
2265 {"ABCXYZ", "ABCXYZ", 62, 33536793425, true},
2266
2267
2268
2269 {"1_000", "1000", 0, 1000, true},
2270 {"0b_1010", "10", 0, 10, true},
2271 {"+0o_660", "432", 0, 0660, true},
2272 {"-0xF00D_1E", "-15731998", 0, -0xf00d1e, true},
2273 }
2274
2275 func TestBigIntText(t *testing.T) {
2276 z := new(BigInt)
2277 for _, test := range stringTests {
2278 if !test.ok {
2279 continue
2280 }
2281
2282 _, ok := z.SetString(test.in, test.base)
2283 if !ok {
2284 t.Errorf("%v: failed to parse", test)
2285 continue
2286 }
2287
2288 base := test.base
2289 if base == 0 {
2290 base = 10
2291 }
2292
2293 if got := z.Text(base); got != test.out {
2294 t.Errorf("%v: got %s; want %s", test, got, test.out)
2295 }
2296 }
2297 }
2298
2299 func TestBigIntAppendText(t *testing.T) {
2300 z := new(BigInt)
2301 var buf []byte
2302 for _, test := range stringTests {
2303 if !test.ok {
2304 continue
2305 }
2306
2307 _, ok := z.SetString(test.in, test.base)
2308 if !ok {
2309 t.Errorf("%v: failed to parse", test)
2310 continue
2311 }
2312
2313 base := test.base
2314 if base == 0 {
2315 base = 10
2316 }
2317
2318 i := len(buf)
2319 buf = z.Append(buf, base)
2320 if got := string(buf[i:]); got != test.out {
2321 t.Errorf("%v: got %s; want %s", test, got, test.out)
2322 }
2323 }
2324 }
2325
2326 func TestBigIntGetString(t *testing.T) {
2327 format := func(base int) string {
2328 switch base {
2329 case 2:
2330 return "%b"
2331 case 8:
2332 return "%o"
2333 case 16:
2334 return "%x"
2335 }
2336 return "%d"
2337 }
2338
2339 z := new(BigInt)
2340 for i, test := range stringTests {
2341 if !test.ok {
2342 continue
2343 }
2344 z.SetInt64(test.val)
2345
2346 if test.base == 10 {
2347 if got := z.String(); got != test.out {
2348 t.Errorf("#%da got %s; want %s", i, got, test.out)
2349 }
2350 }
2351
2352 f := format(test.base)
2353 got := fmt.Sprintf(f, z)
2354 if f == "%d" {
2355 if got != fmt.Sprintf("%d", test.val) {
2356 t.Errorf("#%db got %s; want %d", i, got, test.val)
2357 }
2358 } else {
2359 if got != test.out {
2360 t.Errorf("#%dc got %s; want %s", i, got, test.out)
2361 }
2362 }
2363 }
2364 }
2365
2366 func TestBigIntSetString(t *testing.T) {
2367 tmp := new(BigInt)
2368 for i, test := range stringTests {
2369
2370
2371 tmp.SetInt64(1234567890)
2372 n1, ok1 := new(BigInt).SetString(test.in, test.base)
2373 n2, ok2 := tmp.SetString(test.in, test.base)
2374 expected := NewBigInt(test.val)
2375 if ok1 != test.ok || ok2 != test.ok {
2376 t.Errorf("#%d (input '%s') ok incorrect (should be %t)", i, test.in, test.ok)
2377 continue
2378 }
2379 if !ok1 {
2380 if n1 != nil {
2381 t.Errorf("#%d (input '%s') n1 != nil", i, test.in)
2382 }
2383 continue
2384 }
2385 if !ok2 {
2386 if n2 != nil {
2387 t.Errorf("#%d (input '%s') n2 != nil", i, test.in)
2388 }
2389 continue
2390 }
2391
2392 if n1.Cmp(expected) != 0 {
2393 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n1, test.val)
2394 }
2395 if n2.Cmp(expected) != 0 {
2396 t.Errorf("#%d (input '%s') got: %s want: %d", i, test.in, n2, test.val)
2397 }
2398 }
2399 }
2400
2401 var formatTests = []struct {
2402 input string
2403 format string
2404 output string
2405 }{
2406 {"<nil>", "%x", "<nil>"},
2407 {"<nil>", "%#x", "<nil>"},
2408 {"<nil>", "%#y", "%!y(big.Int=<nil>)"},
2409
2410 {"10", "%b", "1010"},
2411 {"10", "%o", "12"},
2412 {"10", "%d", "10"},
2413 {"10", "%v", "10"},
2414 {"10", "%x", "a"},
2415 {"10", "%X", "A"},
2416 {"-10", "%X", "-A"},
2417 {"10", "%y", "%!y(big.Int=10)"},
2418 {"-10", "%y", "%!y(big.Int=-10)"},
2419
2420 {"10", "%#b", "0b1010"},
2421 {"10", "%#o", "012"},
2422 {"10", "%O", "0o12"},
2423 {"-10", "%#b", "-0b1010"},
2424 {"-10", "%#o", "-012"},
2425 {"-10", "%O", "-0o12"},
2426 {"10", "%#d", "10"},
2427 {"10", "%#v", "10"},
2428 {"10", "%#x", "0xa"},
2429 {"10", "%#X", "0XA"},
2430 {"-10", "%#X", "-0XA"},
2431 {"10", "%#y", "%!y(big.Int=10)"},
2432 {"-10", "%#y", "%!y(big.Int=-10)"},
2433
2434 {"1234", "%d", "1234"},
2435 {"1234", "%3d", "1234"},
2436 {"1234", "%4d", "1234"},
2437 {"-1234", "%d", "-1234"},
2438 {"1234", "% 5d", " 1234"},
2439 {"1234", "%+5d", "+1234"},
2440 {"1234", "%-5d", "1234 "},
2441 {"1234", "%x", "4d2"},
2442 {"1234", "%X", "4D2"},
2443 {"-1234", "%3x", "-4d2"},
2444 {"-1234", "%4x", "-4d2"},
2445 {"-1234", "%5x", " -4d2"},
2446 {"-1234", "%-5x", "-4d2 "},
2447 {"1234", "%03d", "1234"},
2448 {"1234", "%04d", "1234"},
2449 {"1234", "%05d", "01234"},
2450 {"1234", "%06d", "001234"},
2451 {"-1234", "%06d", "-01234"},
2452 {"1234", "%+06d", "+01234"},
2453 {"1234", "% 06d", " 01234"},
2454 {"1234", "%-6d", "1234 "},
2455 {"1234", "%-06d", "1234 "},
2456 {"-1234", "%-06d", "-1234 "},
2457
2458 {"1234", "%.3d", "1234"},
2459 {"1234", "%.4d", "1234"},
2460 {"1234", "%.5d", "01234"},
2461 {"1234", "%.6d", "001234"},
2462 {"-1234", "%.3d", "-1234"},
2463 {"-1234", "%.4d", "-1234"},
2464 {"-1234", "%.5d", "-01234"},
2465 {"-1234", "%.6d", "-001234"},
2466
2467 {"1234", "%8.3d", " 1234"},
2468 {"1234", "%8.4d", " 1234"},
2469 {"1234", "%8.5d", " 01234"},
2470 {"1234", "%8.6d", " 001234"},
2471 {"-1234", "%8.3d", " -1234"},
2472 {"-1234", "%8.4d", " -1234"},
2473 {"-1234", "%8.5d", " -01234"},
2474 {"-1234", "%8.6d", " -001234"},
2475
2476 {"1234", "%+8.3d", " +1234"},
2477 {"1234", "%+8.4d", " +1234"},
2478 {"1234", "%+8.5d", " +01234"},
2479 {"1234", "%+8.6d", " +001234"},
2480 {"-1234", "%+8.3d", " -1234"},
2481 {"-1234", "%+8.4d", " -1234"},
2482 {"-1234", "%+8.5d", " -01234"},
2483 {"-1234", "%+8.6d", " -001234"},
2484
2485 {"1234", "% 8.3d", " 1234"},
2486 {"1234", "% 8.4d", " 1234"},
2487 {"1234", "% 8.5d", " 01234"},
2488 {"1234", "% 8.6d", " 001234"},
2489 {"-1234", "% 8.3d", " -1234"},
2490 {"-1234", "% 8.4d", " -1234"},
2491 {"-1234", "% 8.5d", " -01234"},
2492 {"-1234", "% 8.6d", " -001234"},
2493
2494 {"1234", "%.3x", "4d2"},
2495 {"1234", "%.4x", "04d2"},
2496 {"1234", "%.5x", "004d2"},
2497 {"1234", "%.6x", "0004d2"},
2498 {"-1234", "%.3x", "-4d2"},
2499 {"-1234", "%.4x", "-04d2"},
2500 {"-1234", "%.5x", "-004d2"},
2501 {"-1234", "%.6x", "-0004d2"},
2502
2503 {"1234", "%8.3x", " 4d2"},
2504 {"1234", "%8.4x", " 04d2"},
2505 {"1234", "%8.5x", " 004d2"},
2506 {"1234", "%8.6x", " 0004d2"},
2507 {"-1234", "%8.3x", " -4d2"},
2508 {"-1234", "%8.4x", " -04d2"},
2509 {"-1234", "%8.5x", " -004d2"},
2510 {"-1234", "%8.6x", " -0004d2"},
2511
2512 {"1234", "%+8.3x", " +4d2"},
2513 {"1234", "%+8.4x", " +04d2"},
2514 {"1234", "%+8.5x", " +004d2"},
2515 {"1234", "%+8.6x", " +0004d2"},
2516 {"-1234", "%+8.3x", " -4d2"},
2517 {"-1234", "%+8.4x", " -04d2"},
2518 {"-1234", "%+8.5x", " -004d2"},
2519 {"-1234", "%+8.6x", " -0004d2"},
2520
2521 {"1234", "% 8.3x", " 4d2"},
2522 {"1234", "% 8.4x", " 04d2"},
2523 {"1234", "% 8.5x", " 004d2"},
2524 {"1234", "% 8.6x", " 0004d2"},
2525 {"1234", "% 8.7x", " 00004d2"},
2526 {"1234", "% 8.8x", " 000004d2"},
2527 {"-1234", "% 8.3x", " -4d2"},
2528 {"-1234", "% 8.4x", " -04d2"},
2529 {"-1234", "% 8.5x", " -004d2"},
2530 {"-1234", "% 8.6x", " -0004d2"},
2531 {"-1234", "% 8.7x", "-00004d2"},
2532 {"-1234", "% 8.8x", "-000004d2"},
2533
2534 {"1234", "%-8.3d", "1234 "},
2535 {"1234", "%-8.4d", "1234 "},
2536 {"1234", "%-8.5d", "01234 "},
2537 {"1234", "%-8.6d", "001234 "},
2538 {"1234", "%-8.7d", "0001234 "},
2539 {"1234", "%-8.8d", "00001234"},
2540 {"-1234", "%-8.3d", "-1234 "},
2541 {"-1234", "%-8.4d", "-1234 "},
2542 {"-1234", "%-8.5d", "-01234 "},
2543 {"-1234", "%-8.6d", "-001234 "},
2544 {"-1234", "%-8.7d", "-0001234"},
2545 {"-1234", "%-8.8d", "-00001234"},
2546
2547 {"16777215", "%b", "111111111111111111111111"},
2548
2549 {"0", "%.d", ""},
2550 {"0", "%.0d", ""},
2551 {"0", "%3.d", ""},
2552 }
2553
2554 func TestBigIntFormat(t *testing.T) {
2555 for i, test := range formatTests {
2556 var x *BigInt
2557 if test.input != "<nil>" {
2558 var ok bool
2559 x, ok = new(BigInt).SetString(test.input, 0)
2560 if !ok {
2561 t.Errorf("#%d failed reading input %s", i, test.input)
2562 }
2563 }
2564 output := fmt.Sprintf(test.format, x)
2565 if output != test.output {
2566 t.Errorf("#%d got %q; want %q, {%q, %q, %q}", i, output, test.output, test.input, test.format, test.output)
2567 }
2568 }
2569 }
2570
2571 var scanTests = []struct {
2572 input string
2573 format string
2574 output string
2575 remaining int
2576 }{
2577 {"1010", "%b", "10", 0},
2578 {"0b1010", "%v", "10", 0},
2579 {"12", "%o", "10", 0},
2580 {"012", "%v", "10", 0},
2581 {"10", "%d", "10", 0},
2582 {"10", "%v", "10", 0},
2583 {"a", "%x", "10", 0},
2584 {"0xa", "%v", "10", 0},
2585 {"A", "%X", "10", 0},
2586 {"-A", "%X", "-10", 0},
2587 {"+0b1011001", "%v", "89", 0},
2588 {"0xA", "%v", "10", 0},
2589 {"0 ", "%v", "0", 1},
2590 {"2+3", "%v", "2", 2},
2591 {"0XABC 12", "%v", "2748", 3},
2592 }
2593
2594 func TestBigIntScan(t *testing.T) {
2595 var buf bytes.Buffer
2596 for i, test := range scanTests {
2597 x := new(BigInt)
2598 buf.Reset()
2599 buf.WriteString(test.input)
2600 if _, err := fmt.Fscanf(&buf, test.format, x); err != nil {
2601 t.Errorf("#%d error: %s", i, err)
2602 }
2603 if x.String() != test.output {
2604 t.Errorf("#%d got %s; want %s", i, x.String(), test.output)
2605 }
2606 if buf.Len() != test.remaining {
2607 t.Errorf("#%d got %d bytes remaining; want %d", i, buf.Len(), test.remaining)
2608 }
2609 }
2610 }
2611
2612
2613
2614
2615
2616 var encodingTests = []string{
2617 "0",
2618 "1",
2619 "2",
2620 "10",
2621 "1000",
2622 "1234567890",
2623 "298472983472983471903246121093472394872319615612417471234712061",
2624 }
2625
2626 func TestBigIntGobEncoding(t *testing.T) {
2627 var medium bytes.Buffer
2628 enc := gob.NewEncoder(&medium)
2629 dec := gob.NewDecoder(&medium)
2630 for _, test := range encodingTests {
2631 for _, sign := range []string{"", "+", "-"} {
2632 x := sign + test
2633 medium.Reset()
2634 var tx BigInt
2635 tx.SetString(x, 10)
2636 if err := enc.Encode(&tx); err != nil {
2637 t.Errorf("encoding of %s failed: %s", &tx, err)
2638 continue
2639 }
2640 var rx BigInt
2641 if err := dec.Decode(&rx); err != nil {
2642 t.Errorf("decoding of %s failed: %s", &tx, err)
2643 continue
2644 }
2645 if rx.Cmp(&tx) != 0 {
2646 t.Errorf("transmission of %s failed: got %s want %s", &tx, &rx, &tx)
2647 }
2648 }
2649 }
2650 }
2651
2652
2653 func TestBigIntGobEncodingNilIntInSlice(t *testing.T) {
2654 buf := new(bytes.Buffer)
2655 enc := gob.NewEncoder(buf)
2656 dec := gob.NewDecoder(buf)
2657
2658 var in = make([]*BigInt, 1)
2659 err := enc.Encode(&in)
2660 if err != nil {
2661 t.Errorf("gob encode failed: %q", err)
2662 }
2663 var out []*BigInt
2664 err = dec.Decode(&out)
2665 if err != nil {
2666 t.Fatalf("gob decode failed: %q", err)
2667 }
2668 if len(out) != 1 {
2669 t.Fatalf("wrong len; want 1 got %d", len(out))
2670 }
2671 var zero BigInt
2672 if out[0].Cmp(&zero) != 0 {
2673 t.Fatalf("transmission of (*BigInt)(nil) failed: got %s want 0", out)
2674 }
2675 }
2676
2677 func TestBigIntJSONEncoding(t *testing.T) {
2678 for _, test := range encodingTests {
2679 for _, sign := range []string{"", "+", "-"} {
2680 x := sign + test
2681 var tx BigInt
2682 tx.SetString(x, 10)
2683 b, err := json.Marshal(&tx)
2684 if err != nil {
2685 t.Errorf("marshaling of %s failed: %s", &tx, err)
2686 continue
2687 }
2688 var rx BigInt
2689 if err := json.Unmarshal(b, &rx); err != nil {
2690 t.Errorf("unmarshaling of %s failed: %s", &tx, err)
2691 continue
2692 }
2693 if rx.Cmp(&tx) != 0 {
2694 t.Errorf("JSON encoding of %s failed: got %s want %s", &tx, &rx, &tx)
2695 }
2696 }
2697 }
2698 }
2699
2700 func TestBigIntXMLEncoding(t *testing.T) {
2701 for _, test := range encodingTests {
2702 for _, sign := range []string{"", "+", "-"} {
2703 x := sign + test
2704 var tx BigInt
2705 tx.SetString(x, 0)
2706 b, err := xml.Marshal(&tx)
2707 if err != nil {
2708 t.Errorf("marshaling of %s failed: %s", &tx, err)
2709 continue
2710 }
2711 var rx BigInt
2712 if err := xml.Unmarshal(b, &rx); err != nil {
2713 t.Errorf("unmarshaling of %s failed: %s", &tx, err)
2714 continue
2715 }
2716 if rx.Cmp(&tx) != 0 {
2717 t.Errorf("XML encoding of %s failed: got %s want %s", &tx, &rx, &tx)
2718 }
2719 }
2720 }
2721 }
2722
2723
2724
2725
2726
2727 func BenchmarkBigIntBinomial(b *testing.B) {
2728 var z BigInt
2729 for i := b.N - 1; i >= 0; i-- {
2730 z.Binomial(1000, 990)
2731 }
2732 }
2733
2734 func BenchmarkBigIntQuoRem(b *testing.B) {
2735 x, _ := new(BigInt).SetString("153980389784927331788354528594524332344709972855165340650588877572729725338415474372475094155672066328274535240275856844648695200875763869073572078279316458648124537905600131008790701752441155668003033945258023841165089852359980273279085783159654751552359397986180318708491098942831252291841441726305535546071", 0)
2736 y, _ := new(BigInt).SetString("7746362281539803897849273317883545285945243323447099728551653406505888775727297253384154743724750941556720663282745352402758568446486952008757638690735720782793164586481245379056001310087907017524411556680030339452580238411650898523599802732790857831596547515523593979861803187084910989428312522918414417263055355460715745539358014631136245887418412633787074173796862711588221766398229333338511838891484974940633857861775630560092874987828057333663969469797013996401149696897591265769095952887917296740109742927689053276850469671231961384715398038978492733178835452859452433234470997285516534065058887757272972533841547437247509415567206632827453524027585684464869520087576386907357207827931645864812453790560013100879070175244115566800303394525802384116508985235998027327908578315965475155235939798618031870849109894283125229184144172630553554607112725169432413343763989564437170644270643461665184965150423819594083121075825", 0)
2737 q := new(BigInt)
2738 r := new(BigInt)
2739
2740 b.ResetTimer()
2741 for i := 0; i < b.N; i++ {
2742 q.QuoRem(y, x, r)
2743 }
2744 }
2745
2746 func BenchmarkBigIntExp(b *testing.B) {
2747 x, _ := new(BigInt).SetString("11001289118363089646017359372117963499250546375269047542777928006103246876688756735760905680604646624353196869572752623285140408755420374049317646428185270079555372763503115646054602867593662923894140940837479507194934267532831694565516466765025434902348314525627418515646588160955862839022051353653052947073136084780742729727874803457643848197499548297570026926927502505634297079527299004267769780768565695459945235586892627059178884998772989397505061206395455591503771677500931269477503508150175717121828518985901959919560700853226255420793148986854391552859459511723547532575574664944815966793196961286234040892865", 0)
2748 y, _ := new(BigInt).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
2749 n, _ := new(BigInt).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
2750 out := new(BigInt)
2751 for i := 0; i < b.N; i++ {
2752 out.Exp(x, y, n)
2753 }
2754 }
2755
2756 func BenchmarkBigIntExp2(b *testing.B) {
2757 x, _ := new(BigInt).SetString("2", 0)
2758 y, _ := new(BigInt).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF72", 0)
2759 n, _ := new(BigInt).SetString("0xAC6BDB41324A9A9BF166DE5E1389582FAF72B6651987EE07FC3192943DB56050A37329CBB4A099ED8193E0757767A13DD52312AB4B03310DCD7F48A9DA04FD50E8083969EDB767B0CF6095179A163AB3661A05FBD5FAAAE82918A9962F0B93B855F97993EC975EEAA80D740ADBF4FF747359D041D5C33EA71D281E446B14773BCA97B43A23FB801676BD207A436C6481F1D2B9078717461A5B9D32E688F87748544523B524B0D57D5EA77A2775D2ECFA032CFBDBF52FB3786160279004E57AE6AF874E7303CE53299CCC041C7BC308D82A5698F3A8D0C38271AE35F8E9DBFBB694B5C803D89F7AE435DE236D525F54759B65E372FCD68EF20FA7111F9E4AFF73", 0)
2760 out := new(BigInt)
2761 for i := 0; i < b.N; i++ {
2762 out.Exp(x, y, n)
2763 }
2764 }
2765
2766 func BenchmarkBigIntBitset(b *testing.B) {
2767 z := new(BigInt)
2768 z.SetBit(z, 512, 1)
2769 b.ResetTimer()
2770 b.StartTimer()
2771 for i := b.N - 1; i >= 0; i-- {
2772 z.SetBit(z, i&512, 1)
2773 }
2774 }
2775
2776 func BenchmarkBigIntBitsetNeg(b *testing.B) {
2777 z := NewBigInt(-1)
2778 z.SetBit(z, 512, 0)
2779 b.ResetTimer()
2780 b.StartTimer()
2781 for i := b.N - 1; i >= 0; i-- {
2782 z.SetBit(z, i&512, 0)
2783 }
2784 }
2785
2786 func BenchmarkBigIntBitsetOrig(b *testing.B) {
2787 z := new(BigInt)
2788 altSetBit(z, z, 512, 1)
2789 b.ResetTimer()
2790 b.StartTimer()
2791 for i := b.N - 1; i >= 0; i-- {
2792 altSetBit(z, z, i&512, 1)
2793 }
2794 }
2795
2796 func BenchmarkBigIntBitsetNegOrig(b *testing.B) {
2797 z := NewBigInt(-1)
2798 altSetBit(z, z, 512, 0)
2799 b.ResetTimer()
2800 b.StartTimer()
2801 for i := b.N - 1; i >= 0; i-- {
2802 altSetBit(z, z, i&512, 0)
2803 }
2804 }
2805
2806 func BenchmarkBigIntModInverse(b *testing.B) {
2807 p := new(BigInt).SetInt64(1)
2808 p.Lsh(p, 1279)
2809 p.Sub(p, bigOne)
2810 x := new(BigInt).Sub(p, bigOne)
2811 z := new(BigInt)
2812 for i := 0; i < b.N; i++ {
2813 z.ModInverse(x, p)
2814 }
2815 }
2816
2817 func BenchmarkBigIntSqrt(b *testing.B) {
2818 n, _ := new(BigInt).SetString("1"+strings.Repeat("0", 1001), 10)
2819 b.ResetTimer()
2820 t := new(BigInt)
2821 for i := 0; i < b.N; i++ {
2822 t.Sqrt(n)
2823 }
2824 }
2825
2826
2827 func randBigInt(r *rand.Rand, size uint) *BigInt {
2828 n := new(BigInt).Lsh(bigOne, size-1)
2829 x := new(BigInt).Rand(r, n)
2830 return x.Add(x, n)
2831 }
2832
2833 func benchmarkBigIntDiv(b *testing.B, aSize, bSize int) {
2834 var r = rand.New(rand.NewSource(1234))
2835 aa := randBigInt(r, uint(aSize))
2836 bb := randBigInt(r, uint(bSize))
2837 if aa.Cmp(bb) < 0 {
2838 aa, bb = bb, aa
2839 }
2840 x := new(BigInt)
2841 y := new(BigInt)
2842
2843 b.ResetTimer()
2844 for i := 0; i < b.N; i++ {
2845 x.DivMod(aa, bb, y)
2846 }
2847 }
2848
2849 func BenchmarkBigIntDiv(b *testing.B) {
2850 sizes := []int{
2851 10, 20, 50, 100, 200, 500, 1000,
2852 1e4, 1e5, 1e6, 1e7,
2853 }
2854 for _, i := range sizes {
2855 j := 2 * i
2856 b.Run(fmt.Sprintf("%d/%d", j, i), func(b *testing.B) {
2857 benchmarkBigIntDiv(b, j, i)
2858 })
2859 }
2860 }
2861
View as plain text