1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
14 var cmpTests
= []struct {
21 {nat(nil), nat(nil), 0},
26 {nat
{0, _M
}, nat
{1}, 1},
27 {nat
{1}, nat
{0, _M
}, -1},
28 {nat
{1, _M
}, nat
{0, _M
}, 1},
29 {nat
{0, _M
}, nat
{1, _M
}, -1},
30 {nat
{16, 571956, 8794, 68}, nat
{837, 9146, 1, 754489}, -1},
31 {nat
{34986, 41, 105, 1957}, nat
{56, 7458, 104, 1957}, 1},
34 func TestCmp(t
*testing
.T
) {
35 for i
, a
:= range cmpTests
{
38 t
.Errorf("#%d got r = %v; want %v", i
, r
, a
.r
)
43 type funNN
func(z
, x
, y nat
) nat
50 {nat
{1}, nil, nat
{1}},
51 {nat
{1111111110}, nat
{123456789}, nat
{987654321}},
52 {nat
{0, 0, 0, 1}, nil, nat
{0, 0, 0, 1}},
53 {nat
{0, 0, 0, 1111111110}, nat
{0, 0, 0, 123456789}, nat
{0, 0, 0, 987654321}},
54 {nat
{0, 0, 0, 1}, nat
{0, 0, _M
}, nat
{0, 0, 1}},
61 {nat
{991}, nat
{991}, nat
{1}},
62 {nat
{991 * 991}, nat
{991}, nat
{991}},
63 {nat
{0, 0, 991 * 991}, nat
{0, 991}, nat
{0, 991}},
64 {nat
{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat
{1, 2, 3, 4}, nat
{991}},
65 {nat
{4, 11, 20, 30, 20, 11, 4}, nat
{1, 2, 3, 4}, nat
{4, 3, 2, 1}},
66 // 3^100 * 3^28 = 3^128
68 natFromString("11790184577738583171520872861412518665678211592275841109096961"),
69 natFromString("515377520732011331036461129765621272702107522001"),
70 natFromString("22876792454961"),
72 // z = 111....1 (70000 digits)
73 // x = 10^(99*700) + ... + 10^1400 + 10^700 + 1
74 // y = 111....1 (700 digits, larger than Karatsuba threshold on 32-bit and 64-bit)
76 natFromString(strings
.Repeat("1", 70000)),
77 natFromString("1" + strings
.Repeat(strings
.Repeat("0", 699)+"1", 99)),
78 natFromString(strings
.Repeat("1", 700)),
80 // z = 111....1 (20000 digits)
82 // y = 111....1 (10000 digits)
84 natFromString(strings
.Repeat("1", 20000)),
85 natFromString("1" + strings
.Repeat("0", 9999) + "1"),
86 natFromString(strings
.Repeat("1", 10000)),
90 func natFromString(s
string) nat
{
91 x
, _
, _
, err
:= nat(nil).scan(strings
.NewReader(s
), 0, false)
98 func TestSet(t
*testing
.T
) {
99 for _
, a
:= range sumNN
{
100 z
:= nat(nil).set(a
.z
)
102 t
.Errorf("got z = %v; want %v", z
, a
.z
)
107 func testFunNN(t
*testing
.T
, msg
string, f funNN
, a argNN
) {
108 z
:= f(nil, a
.x
, a
.y
)
110 t
.Errorf("%s%+v\n\tgot z = %v; want %v", msg
, a
, z
, a
.z
)
114 func TestFunNN(t
*testing
.T
) {
115 for _
, a
:= range sumNN
{
117 testFunNN(t
, "add", nat
.add
, arg
)
119 arg
= argNN
{a
.z
, a
.y
, a
.x
}
120 testFunNN(t
, "add symmetric", nat
.add
, arg
)
122 arg
= argNN
{a
.x
, a
.z
, a
.y
}
123 testFunNN(t
, "sub", nat
.sub
, arg
)
125 arg
= argNN
{a
.y
, a
.z
, a
.x
}
126 testFunNN(t
, "sub symmetric", nat
.sub
, arg
)
129 for _
, a
:= range prodNN
{
131 testFunNN(t
, "mul", nat
.mul
, arg
)
133 arg
= argNN
{a
.z
, a
.y
, a
.x
}
134 testFunNN(t
, "mul symmetric", nat
.mul
, arg
)
138 var mulRangesN
= []struct {
149 {1, 0, "1"}, // empty range
150 {100, 1, "1"}, // empty range
151 {1, 10, "3628800"}, // 10!
152 {1, 20, "2432902008176640000"}, // 20!
154 "933262154439441526816992388562667004907159682643816214685929" +
155 "638952175999932299156089414639761565182862536979208272237582" +
156 "51185210916864000000000000000000000000", // 100!
160 func TestMulRangeN(t
*testing
.T
) {
161 for i
, r
:= range mulRangesN
{
162 prod
:= string(nat(nil).mulRange(r
.a
, r
.b
).utoa(10))
164 t
.Errorf("#%d: got %s; want %s", i
, prod
, r
.prod
)
169 // allocBytes returns the number of bytes allocated by invoking f.
170 func allocBytes(f
func()) uint64 {
171 var stats runtime
.MemStats
172 runtime
.ReadMemStats(&stats
)
173 t
:= stats
.TotalAlloc
175 runtime
.ReadMemStats(&stats
)
176 return stats
.TotalAlloc
- t
179 // TestMulUnbalanced tests that multiplying numbers of different lengths
180 // does not cause deep recursion and in turn allocate too much memory.
181 // Test case for issue 3807.
182 func TestMulUnbalanced(t
*testing
.T
) {
183 defer runtime
.GOMAXPROCS(runtime
.GOMAXPROCS(1))
186 allocSize
:= allocBytes(func() {
189 inputSize
:= uint64(len(x
)+len(y
)) * _S
190 if ratio
:= allocSize
/ uint64(inputSize
); ratio
> 10 {
191 t
.Errorf("multiplication uses too much memory (%d > %d times the size of inputs)", allocSize
, ratio
)
195 func rndNat(n
int) nat
{
196 return nat(rndV(n
)).norm()
199 func BenchmarkMul(b
*testing
.B
) {
203 for i
:= 0; i
< b
.N
; i
++ {
209 func TestNLZ(t
*testing
.T
) {
211 for i
:= 0; i
<= _W
; i
++ {
212 if int(nlz(x
)) != i
{
213 t
.Errorf("failed at %x: got %d want %d", x
, nlz(x
), i
)
219 type shiftTest
struct {
225 var leftShiftTests
= []shiftTest
{
230 {nat
{1 << (_W
- 1)}, 1, nat
{0}},
231 {nat
{1 << (_W
- 1), 0}, 1, nat
{0, 1}},
234 func TestShiftLeft(t
*testing
.T
) {
235 for i
, test
:= range leftShiftTests
{
237 z
= z
.shl(test
.in
, test
.shift
)
238 for j
, d
:= range test
.out
{
239 if j
>= len(z
) || z
[j
] != d
{
240 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
247 var rightShiftTests
= []shiftTest
{
253 {nat
{0, 1}, 1, nat
{1 << (_W
- 1)}},
254 {nat
{2, 1, 1}, 1, nat
{1<<(_W
-1) + 1, 1 << (_W
- 1)}},
257 func TestShiftRight(t
*testing
.T
) {
258 for i
, test
:= range rightShiftTests
{
260 z
= z
.shr(test
.in
, test
.shift
)
261 for j
, d
:= range test
.out
{
262 if j
>= len(z
) || z
[j
] != d
{
263 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
270 func BenchmarkZeroShifts(b
*testing
.B
) {
273 b
.Run("Shl", func(b
*testing
.B
) {
274 for i
:= 0; i
< b
.N
; i
++ {
279 b
.Run("ShlSame", func(b
*testing
.B
) {
280 for i
:= 0; i
< b
.N
; i
++ {
285 b
.Run("Shr", func(b
*testing
.B
) {
286 for i
:= 0; i
< b
.N
; i
++ {
291 b
.Run("ShrSame", func(b
*testing
.B
) {
292 for i
:= 0; i
< b
.N
; i
++ {
298 type modWTest
struct {
304 var modWTests32
= []modWTest
{
305 {"23492635982634928349238759823742", "252341", "220170"},
308 var modWTests64
= []modWTest
{
309 {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
312 func runModWTests(t
*testing
.T
, tests
[]modWTest
) {
313 for i
, test
:= range tests
{
314 in
, _
:= new(Int
).SetString(test
.in
, 10)
315 d
, _
:= new(Int
).SetString(test
.dividend
, 10)
316 out
, _
:= new(Int
).SetString(test
.out
, 10)
318 r
:= in
.abs
.modW(d
.abs
[0])
320 t
.Errorf("#%d failed: got %d want %s", i
, r
, out
)
325 func TestModW(t
*testing
.T
) {
327 runModWTests(t
, modWTests32
)
330 runModWTests(t
, modWTests64
)
334 var montgomeryTests
= []struct {
340 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
341 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
342 "0xfffffffffffffffffffffffffffffffffffffffffffffffff",
344 "0x1000000000000000000000000000000000000000000",
345 "0x10000000000000000000000000000000000",
348 "0x000000000ffffff5",
349 "0x000000000ffffff0",
350 "0x0000000010000001",
352 "0x000000000bfffff4",
353 "0x0000000003400001",
356 "0x0000000080000000",
357 "0x00000000ffffffff",
358 "0x1000000000000001",
360 "0x0800000008000001",
361 "0x0800000008000001",
364 "0x0000000080000000",
365 "0x0000000080000000",
366 "0xffffffff00000001",
368 "0xbfffffff40000001",
369 "0xbfffffff40000001",
372 "0x0000000080000000",
373 "0x0000000080000000",
374 "0x00ffffff00000001",
380 "0x0000000080000000",
381 "0x0000000080000000",
382 "0x0000ffff00000001",
388 "0x3321ffffffffffffffffffffffffffff00000000000022222623333333332bbbb888c0",
389 "0x3321ffffffffffffffffffffffffffff00000000000022222623333333332bbbb888c0",
390 "0x33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
392 "0x04eb0e11d72329dc0915f86784820fc403275bf2f6620a20e0dd344c5cd0875e50deb5",
393 "0x0d7144739a7d8e11d72329dc0915f86784820fc403275bf2f61ed96f35dd34dbb3d6a0",
396 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000022222223333333333444444444",
397 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff999999999999999aaabbbbbbbbcccccccccccc",
398 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
400 "0x5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d7a11c7772cba02c22f9711078d51a3797eb18e691295293284d988e349fa6deba46b25a4ecd9f715",
401 "0x92fcad4b5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d799c32fe2f3cc5422f9711078d51a3797eb18e691295293284d8f5e69caf6decddfe1df6",
405 func TestMontgomery(t
*testing
.T
) {
407 _B
:= new(Int
).Lsh(one
, _W
)
408 for i
, test
:= range montgomeryTests
{
409 x
:= natFromString(test
.x
)
410 y
:= natFromString(test
.y
)
411 m
:= natFromString(test
.m
)
412 for len(x
) < len(m
) {
415 for len(y
) < len(m
) {
420 _
, r
:= nat(nil).div(nil, x
, m
)
421 t
.Errorf("#%d: x > m (0x%s > 0x%s; use 0x%s)", i
, x
.utoa(16), m
.utoa(16), r
.utoa(16))
424 _
, r
:= nat(nil).div(nil, x
, m
)
425 t
.Errorf("#%d: y > m (0x%s > 0x%s; use 0x%s)", i
, y
.utoa(16), m
.utoa(16), r
.utoa(16))
430 out
= natFromString(test
.out32
)
432 out
= natFromString(test
.out64
)
435 // t.Logf("#%d: len=%d\n", i, len(m))
437 // check output in table
441 p
:= new(Int
).Mod(new(Int
).Mul(xi
, new(Int
).Mul(yi
, new(Int
).ModInverse(new(Int
).Lsh(one
, uint(len(m
))*_W
), mi
))), mi
)
442 if out
.cmp(p
.abs
.norm()) != 0 {
443 t
.Errorf("#%d: out in table=0x%s, computed=0x%s", i
, out
.utoa(16), p
.abs
.norm().utoa(16))
447 k
:= new(Int
).Mod(&Int
{abs
: m
}, _B
)
448 k
= new(Int
).Sub(_B
, k
)
449 k
= new(Int
).Mod(k
, _B
)
450 k0
:= Word(new(Int
).ModInverse(k
, _B
).Uint64())
451 if k0
!= Word(test
.k0
) {
452 t
.Errorf("#%d: k0 in table=%#x, computed=%#x\n", i
, test
.k0
, k0
)
455 // check montgomery with correct k0 produces correct output
456 z
:= nat(nil).montgomery(x
, y
, m
, k0
, len(m
))
459 t
.Errorf("#%d: got 0x%s want 0x%s", i
, z
.utoa(16), out
.utoa(16))
464 var expNNTests
= []struct {
468 {"0", "0", "0", "1"},
469 {"0", "0", "1", "0"},
470 {"1", "1", "1", "0"},
471 {"2", "1", "1", "0"},
472 {"2", "2", "1", "0"},
473 {"10", "100000000000", "1", "0"},
474 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
475 {"0x8000000000000000", "2", "6719", "4944"},
476 {"0x8000000000000000", "3", "6719", "5447"},
477 {"0x8000000000000000", "1000", "6719", "1603"},
478 {"0x8000000000000000", "1000000", "6719", "3199"},
480 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
481 "298472983472983471903246121093472394872319615612417471234712061",
482 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
483 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
486 "11521922904531591643048817447554701904414021819823889996244743037378330903763518501116638828335352811871131385129455853417360623007349090150042001944696604737499160174391019030572483602867266711107136838523916077674888297896995042968746762200926853379",
487 "426343618817810911523",
488 "444747819283133684179",
493 func TestExpNN(t
*testing
.T
) {
494 for i
, test
:= range expNNTests
{
495 x
:= natFromString(test
.x
)
496 y
:= natFromString(test
.y
)
497 out
:= natFromString(test
.out
)
501 m
= natFromString(test
.m
)
504 z
:= nat(nil).expNN(x
, y
, m
)
506 t
.Errorf("#%d got %s want %s", i
, z
.utoa(10), out
.utoa(10))
511 func BenchmarkExp3Power(b
*testing
.B
) {
513 for _
, y
:= range []Word
{
514 0x10, 0x40, 0x100, 0x400, 0x1000, 0x4000, 0x10000, 0x40000, 0x100000, 0x400000,
516 b
.Run(fmt
.Sprintf("%#x", y
), func(b
*testing
.B
) {
518 for i
:= 0; i
< b
.N
; i
++ {
525 func fibo(n
int) nat
{
535 for i
:= 1; i
< n
; i
++ {
537 f0
, f1
, f2
= f1
, f2
, f0
542 var fiboNums
= []string{
552 "2880067194370816120",
553 "354224848179261915075",
556 func TestFibo(t
*testing
.T
) {
557 for i
, want
:= range fiboNums
{
559 got
:= string(fibo(n
).utoa(10))
561 t
.Errorf("fibo(%d) failed: got %s want %s", n
, got
, want
)
566 func BenchmarkFibo(b
*testing
.B
) {
567 for i
:= 0; i
< b
.N
; i
++ {
577 var bitTests
= []struct {
592 {"0x8000000000000000", 62, 0},
593 {"0x8000000000000000", 63, 1},
594 {"0x8000000000000000", 64, 0},
596 {"0x3" + strings
.Repeat("0", 32), 127, 0},
597 {"0x3" + strings
.Repeat("0", 32), 128, 1},
598 {"0x3" + strings
.Repeat("0", 32), 129, 1},
599 {"0x3" + strings
.Repeat("0", 32), 130, 0},
602 func TestBit(t
*testing
.T
) {
603 for i
, test
:= range bitTests
{
604 x
:= natFromString(test
.x
)
605 if got
:= x
.bit(test
.i
); got
!= test
.want
{
606 t
.Errorf("#%d: %s.bit(%d) = %v; want %v", i
, test
.x
, test
.i
, got
, test
.want
)
611 var stickyTests
= []struct {
627 {"0x8000000000000000", 63, 0},
628 {"0x8000000000000000", 64, 1},
630 {"0x1" + strings
.Repeat("0", 100), 400, 0},
631 {"0x1" + strings
.Repeat("0", 100), 401, 1},
634 func TestSticky(t
*testing
.T
) {
635 for i
, test
:= range stickyTests
{
636 x
:= natFromString(test
.x
)
637 if got
:= x
.sticky(test
.i
); got
!= test
.want
{
638 t
.Errorf("#%d: %s.sticky(%d) = %v; want %v", i
, test
.x
, test
.i
, got
, test
.want
)
641 // all subsequent i's should also return 1
642 for d
:= uint(1); d
<= 3; d
++ {
643 if got
:= x
.sticky(test
.i
+ d
); got
!= 1 {
644 t
.Errorf("#%d: %s.sticky(%d) = %v; want %v", i
, test
.x
, test
.i
+d
, got
, 1)
651 func testSqr(t
*testing
.T
, x nat
) {
652 got
:= make(nat
, 2*len(x
))
653 want
:= make(nat
, 2*len(x
))
655 want
= want
.mul(x
, x
)
656 if got
.cmp(want
) != 0 {
657 t
.Errorf("basicSqr(%v), got %v, want %v", x
, got
, want
)
661 func TestSqr(t
*testing
.T
) {
662 for _
, a
:= range prodNN
{
675 func benchmarkNatSqr(b
*testing
.B
, nwords
int) {
679 for i
:= 0; i
< b
.N
; i
++ {
684 var sqrBenchSizes
= []int{1, 2, 3, 5, 8, 10, 20, 30, 50, 80, 100, 200, 300, 500, 800, 1000}
686 func BenchmarkNatSqr(b
*testing
.B
) {
687 for _
, n
:= range sqrBenchSizes
{
688 if isRaceBuilder
&& n
> 1e3
{
691 b
.Run(fmt
.Sprintf("%d", n
), func(b
*testing
.B
) {
692 benchmarkNatSqr(b
, n
)
697 func BenchmarkNatSetBytes(b
*testing
.B
) {
698 const maxLength
= 128
703 7, 23, maxLength
- 1,
705 n
:= make(nat
, maxLength
/_W
) // ensure n doesn't need to grow during the test
706 buf
:= make([]byte, maxLength
)
707 for _
, l
:= range lengths
{
708 b
.Run(fmt
.Sprint(l
), func(b
*testing
.B
) {
709 for i
:= 0; i
< b
.N
; i
++ {