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 // rndNat returns a random nat value >= 0 of (usually) n words in length.
196 // In extremely unlikely cases it may be smaller than n words if the top-
198 func rndNat(n
int) nat
{
199 return nat(rndV(n
)).norm()
202 // rndNat1 is like rndNat but the result is guaranteed to be > 0.
203 func rndNat1(n
int) nat
{
204 x
:= nat(rndV(n
)).norm()
211 func BenchmarkMul(b
*testing
.B
) {
215 for i
:= 0; i
< b
.N
; i
++ {
221 func benchmarkNatMul(b
*testing
.B
, nwords
int) {
226 for i
:= 0; i
< b
.N
; i
++ {
231 var mulBenchSizes
= []int{10, 100, 1000, 10000, 100000}
233 func BenchmarkNatMul(b
*testing
.B
) {
234 for _
, n
:= range mulBenchSizes
{
235 if isRaceBuilder
&& n
> 1e3
{
238 b
.Run(fmt
.Sprintf("%d", n
), func(b
*testing
.B
) {
239 benchmarkNatMul(b
, n
)
244 func TestNLZ(t
*testing
.T
) {
246 for i
:= 0; i
<= _W
; i
++ {
247 if int(nlz(x
)) != i
{
248 t
.Errorf("failed at %x: got %d want %d", x
, nlz(x
), i
)
254 type shiftTest
struct {
260 var leftShiftTests
= []shiftTest
{
265 {nat
{1 << (_W
- 1)}, 1, nat
{0}},
266 {nat
{1 << (_W
- 1), 0}, 1, nat
{0, 1}},
269 func TestShiftLeft(t
*testing
.T
) {
270 for i
, test
:= range leftShiftTests
{
272 z
= z
.shl(test
.in
, test
.shift
)
273 for j
, d
:= range test
.out
{
274 if j
>= len(z
) || z
[j
] != d
{
275 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
282 var rightShiftTests
= []shiftTest
{
288 {nat
{0, 1}, 1, nat
{1 << (_W
- 1)}},
289 {nat
{2, 1, 1}, 1, nat
{1<<(_W
-1) + 1, 1 << (_W
- 1)}},
292 func TestShiftRight(t
*testing
.T
) {
293 for i
, test
:= range rightShiftTests
{
295 z
= z
.shr(test
.in
, test
.shift
)
296 for j
, d
:= range test
.out
{
297 if j
>= len(z
) || z
[j
] != d
{
298 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
305 func BenchmarkZeroShifts(b
*testing
.B
) {
308 b
.Run("Shl", func(b
*testing
.B
) {
309 for i
:= 0; i
< b
.N
; i
++ {
314 b
.Run("ShlSame", func(b
*testing
.B
) {
315 for i
:= 0; i
< b
.N
; i
++ {
320 b
.Run("Shr", func(b
*testing
.B
) {
321 for i
:= 0; i
< b
.N
; i
++ {
326 b
.Run("ShrSame", func(b
*testing
.B
) {
327 for i
:= 0; i
< b
.N
; i
++ {
333 type modWTest
struct {
339 var modWTests32
= []modWTest
{
340 {"23492635982634928349238759823742", "252341", "220170"},
343 var modWTests64
= []modWTest
{
344 {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
347 func runModWTests(t
*testing
.T
, tests
[]modWTest
) {
348 for i
, test
:= range tests
{
349 in
, _
:= new(Int
).SetString(test
.in
, 10)
350 d
, _
:= new(Int
).SetString(test
.dividend
, 10)
351 out
, _
:= new(Int
).SetString(test
.out
, 10)
353 r
:= in
.abs
.modW(d
.abs
[0])
355 t
.Errorf("#%d failed: got %d want %s", i
, r
, out
)
360 func TestModW(t
*testing
.T
) {
362 runModWTests(t
, modWTests32
)
365 runModWTests(t
, modWTests64
)
369 var montgomeryTests
= []struct {
375 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
376 "0xffffffffffffffffffffffffffffffffffffffffffffffffe",
377 "0xfffffffffffffffffffffffffffffffffffffffffffffffff",
379 "0x1000000000000000000000000000000000000000000",
380 "0x10000000000000000000000000000000000",
383 "0x000000000ffffff5",
384 "0x000000000ffffff0",
385 "0x0000000010000001",
387 "0x000000000bfffff4",
388 "0x0000000003400001",
391 "0x0000000080000000",
392 "0x00000000ffffffff",
393 "0x1000000000000001",
395 "0x0800000008000001",
396 "0x0800000008000001",
399 "0x0000000080000000",
400 "0x0000000080000000",
401 "0xffffffff00000001",
403 "0xbfffffff40000001",
404 "0xbfffffff40000001",
407 "0x0000000080000000",
408 "0x0000000080000000",
409 "0x00ffffff00000001",
415 "0x0000000080000000",
416 "0x0000000080000000",
417 "0x0000ffff00000001",
423 "0x3321ffffffffffffffffffffffffffff00000000000022222623333333332bbbb888c0",
424 "0x3321ffffffffffffffffffffffffffff00000000000022222623333333332bbbb888c0",
425 "0x33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
427 "0x04eb0e11d72329dc0915f86784820fc403275bf2f6620a20e0dd344c5cd0875e50deb5",
428 "0x0d7144739a7d8e11d72329dc0915f86784820fc403275bf2f61ed96f35dd34dbb3d6a0",
431 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff00000000000022222223333333333444444444",
432 "0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffffffffffffffffffffffffffff999999999999999aaabbbbbbbbcccccccccccc",
433 "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff33377fffffffffffffffffffffffffffffffffffffffffffff0000000000022222eee1",
435 "0x5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d7a11c7772cba02c22f9711078d51a3797eb18e691295293284d988e349fa6deba46b25a4ecd9f715",
436 "0x92fcad4b5c0d52f451aec609b15da8e5e5626c4eaa88723bdeac9d25ca9b961269400410ca208a16af9c2fb07d799c32fe2f3cc5422f9711078d51a3797eb18e691295293284d8f5e69caf6decddfe1df6",
440 func TestMontgomery(t
*testing
.T
) {
442 _B
:= new(Int
).Lsh(one
, _W
)
443 for i
, test
:= range montgomeryTests
{
444 x
:= natFromString(test
.x
)
445 y
:= natFromString(test
.y
)
446 m
:= natFromString(test
.m
)
447 for len(x
) < len(m
) {
450 for len(y
) < len(m
) {
455 _
, r
:= nat(nil).div(nil, x
, m
)
456 t
.Errorf("#%d: x > m (0x%s > 0x%s; use 0x%s)", i
, x
.utoa(16), m
.utoa(16), r
.utoa(16))
459 _
, r
:= nat(nil).div(nil, x
, m
)
460 t
.Errorf("#%d: y > m (0x%s > 0x%s; use 0x%s)", i
, y
.utoa(16), m
.utoa(16), r
.utoa(16))
465 out
= natFromString(test
.out32
)
467 out
= natFromString(test
.out64
)
470 // t.Logf("#%d: len=%d\n", i, len(m))
472 // check output in table
476 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
)
477 if out
.cmp(p
.abs
.norm()) != 0 {
478 t
.Errorf("#%d: out in table=0x%s, computed=0x%s", i
, out
.utoa(16), p
.abs
.norm().utoa(16))
482 k
:= new(Int
).Mod(&Int
{abs
: m
}, _B
)
483 k
= new(Int
).Sub(_B
, k
)
484 k
= new(Int
).Mod(k
, _B
)
485 k0
:= Word(new(Int
).ModInverse(k
, _B
).Uint64())
486 if k0
!= Word(test
.k0
) {
487 t
.Errorf("#%d: k0 in table=%#x, computed=%#x\n", i
, test
.k0
, k0
)
490 // check montgomery with correct k0 produces correct output
491 z
:= nat(nil).montgomery(x
, y
, m
, k0
, len(m
))
494 t
.Errorf("#%d: got 0x%s want 0x%s", i
, z
.utoa(16), out
.utoa(16))
499 var expNNTests
= []struct {
503 {"0", "0", "0", "1"},
504 {"0", "0", "1", "0"},
505 {"1", "1", "1", "0"},
506 {"2", "1", "1", "0"},
507 {"2", "2", "1", "0"},
508 {"10", "100000000000", "1", "0"},
509 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
510 {"0x8000000000000000", "2", "6719", "4944"},
511 {"0x8000000000000000", "3", "6719", "5447"},
512 {"0x8000000000000000", "1000", "6719", "1603"},
513 {"0x8000000000000000", "1000000", "6719", "3199"},
515 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
516 "298472983472983471903246121093472394872319615612417471234712061",
517 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
518 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
521 "11521922904531591643048817447554701904414021819823889996244743037378330903763518501116638828335352811871131385129455853417360623007349090150042001944696604737499160174391019030572483602867266711107136838523916077674888297896995042968746762200926853379",
522 "426343618817810911523",
523 "444747819283133684179",
528 func TestExpNN(t
*testing
.T
) {
529 for i
, test
:= range expNNTests
{
530 x
:= natFromString(test
.x
)
531 y
:= natFromString(test
.y
)
532 out
:= natFromString(test
.out
)
536 m
= natFromString(test
.m
)
539 z
:= nat(nil).expNN(x
, y
, m
)
541 t
.Errorf("#%d got %s want %s", i
, z
.utoa(10), out
.utoa(10))
546 func BenchmarkExp3Power(b
*testing
.B
) {
548 for _
, y
:= range []Word
{
549 0x10, 0x40, 0x100, 0x400, 0x1000, 0x4000, 0x10000, 0x40000, 0x100000, 0x400000,
551 b
.Run(fmt
.Sprintf("%#x", y
), func(b
*testing
.B
) {
553 for i
:= 0; i
< b
.N
; i
++ {
560 func fibo(n
int) nat
{
570 for i
:= 1; i
< n
; i
++ {
572 f0
, f1
, f2
= f1
, f2
, f0
577 var fiboNums
= []string{
587 "2880067194370816120",
588 "354224848179261915075",
591 func TestFibo(t
*testing
.T
) {
592 for i
, want
:= range fiboNums
{
594 got
:= string(fibo(n
).utoa(10))
596 t
.Errorf("fibo(%d) failed: got %s want %s", n
, got
, want
)
601 func BenchmarkFibo(b
*testing
.B
) {
602 for i
:= 0; i
< b
.N
; i
++ {
612 var bitTests
= []struct {
627 {"0x8000000000000000", 62, 0},
628 {"0x8000000000000000", 63, 1},
629 {"0x8000000000000000", 64, 0},
631 {"0x3" + strings
.Repeat("0", 32), 127, 0},
632 {"0x3" + strings
.Repeat("0", 32), 128, 1},
633 {"0x3" + strings
.Repeat("0", 32), 129, 1},
634 {"0x3" + strings
.Repeat("0", 32), 130, 0},
637 func TestBit(t
*testing
.T
) {
638 for i
, test
:= range bitTests
{
639 x
:= natFromString(test
.x
)
640 if got
:= x
.bit(test
.i
); got
!= test
.want
{
641 t
.Errorf("#%d: %s.bit(%d) = %v; want %v", i
, test
.x
, test
.i
, got
, test
.want
)
646 var stickyTests
= []struct {
662 {"0x8000000000000000", 63, 0},
663 {"0x8000000000000000", 64, 1},
665 {"0x1" + strings
.Repeat("0", 100), 400, 0},
666 {"0x1" + strings
.Repeat("0", 100), 401, 1},
669 func TestSticky(t
*testing
.T
) {
670 for i
, test
:= range stickyTests
{
671 x
:= natFromString(test
.x
)
672 if got
:= x
.sticky(test
.i
); got
!= test
.want
{
673 t
.Errorf("#%d: %s.sticky(%d) = %v; want %v", i
, test
.x
, test
.i
, got
, test
.want
)
676 // all subsequent i's should also return 1
677 for d
:= uint(1); d
<= 3; d
++ {
678 if got
:= x
.sticky(test
.i
+ d
); got
!= 1 {
679 t
.Errorf("#%d: %s.sticky(%d) = %v; want %v", i
, test
.x
, test
.i
+d
, got
, 1)
686 func testSqr(t
*testing
.T
, x nat
) {
687 got
:= make(nat
, 2*len(x
))
688 want
:= make(nat
, 2*len(x
))
690 want
= want
.mul(x
, x
)
691 if got
.cmp(want
) != 0 {
692 t
.Errorf("basicSqr(%v), got %v, want %v", x
, got
, want
)
696 func TestSqr(t
*testing
.T
) {
697 for _
, a
:= range prodNN
{
710 func benchmarkNatSqr(b
*testing
.B
, nwords
int) {
714 for i
:= 0; i
< b
.N
; i
++ {
719 var sqrBenchSizes
= []int{
720 1, 2, 3, 5, 8, 10, 20, 30, 50, 80,
721 100, 200, 300, 500, 800,
725 func BenchmarkNatSqr(b
*testing
.B
) {
726 for _
, n
:= range sqrBenchSizes
{
727 if isRaceBuilder
&& n
> 1e3
{
730 b
.Run(fmt
.Sprintf("%d", n
), func(b
*testing
.B
) {
731 benchmarkNatSqr(b
, n
)
736 func BenchmarkNatSetBytes(b
*testing
.B
) {
737 const maxLength
= 128
742 7, 23, maxLength
- 1,
744 n
:= make(nat
, maxLength
/_W
) // ensure n doesn't need to grow during the test
745 buf
:= make([]byte, maxLength
)
746 for _
, l
:= range lengths
{
747 b
.Run(fmt
.Sprint(l
), func(b
*testing
.B
) {
748 for i
:= 0; i
< b
.N
; i
++ {
755 func TestNatDiv(t
*testing
.T
) {
757 1, 2, 5, 8, 15, 25, 40, 65, 100,
758 200, 500, 800, 1500, 2500, 4000, 6500, 10000,
760 for _
, i
:= range sizes
{
761 for _
, j
:= range sizes
{
764 // the test requires b >= 2
765 if len(b
) == 1 && b
[0] == 1 {
768 // choose a remainder c < b
770 if len(c
) == len(b
) && c
[len(c
)-1] >= b
[len(b
)-1] {
775 x
:= nat(nil).mul(a
, b
)
779 q
, r
= q
.div(r
, x
, b
)
781 t
.Fatalf("wrong quotient: got %s; want %s for %s/%s", q
.utoa(10), a
.utoa(10), x
.utoa(10), b
.utoa(10))
784 t
.Fatalf("wrong remainder: got %s; want %s for %s/%s", r
.utoa(10), c
.utoa(10), x
.utoa(10), b
.utoa(10))
790 // TestIssue37499 triggers the edge case of divBasic where
791 // the inaccurate estimate of the first word's quotient
792 // happens at the very beginning of the loop.
793 func TestIssue37499(t
*testing
.T
) {
794 // Choose u and v such that v is slightly larger than u >> N.
795 // This tricks divBasic into choosing 1 as the first word
796 // of the quotient. This works in both 32-bit and 64-bit settings.
797 u
:= natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706b39f8489c1d28e57bb5ba4ef9fd9387a3e344402c0a453381")
798 v
:= natFromString("0x2b6c385a05be027f5c22005b63c42a1165b79ff510e1706c")
800 q
:= nat(nil).make(8)
803 if s
:= string(q
.utoa(16)); s
!= "fffffffffffffffffffffffffffffffffffffffffffffffb" {
804 t
.Fatalf("incorrect quotient: %s", s
)
808 // TestIssue42552 triggers an edge case of recursive division
809 // where the first division loop is never entered, and correcting
810 // the remainder takes exactly two iterations in the final loop.
811 func TestIssue42552(t
*testing
.T
) {
812 u
:= natFromString("0xc23b166884c3869092a520eceedeced2b00847bd256c9cf3b2c5e2227c15bd5e6ee7ef8a2f49236ad0eedf2c8a3b453cf6e0706f64285c526b372c4b1321245519d430540804a50b7ca8b6f1b34a2ec05cdbc24de7599af112d3e3c8db347e8799fe70f16e43c6566ba3aeb169463a3ecc486172deb2d9b80a3699c776e44fef20036bd946f1b4d054dd88a2c1aeb986199b0b2b7e58c42288824b74934d112fe1fc06e06b4d99fe1c5e725946b23210521e209cd507cce90b5f39a523f27e861f9e232aee50c3f585208b4573dcc0b897b6177f2ba20254fd5c50a033e849dee1b3a93bd2dc44ba8ca836cab2c2ae50e50b126284524fa0187af28628ff0face68d87709200329db1392852c8b8963fbe3d05fb1efe19f0ed5ca9fadc2f96f82187c24bb2512b2e85a66333a7e176605695211e1c8e0b9b9e82813e50654964945b1e1e66a90840396c7d10e23e47f364d2d3f660fa54598e18d1ca2ea4fe4f35a40a11f69f201c80b48eaee3e2e9b0eda63decf92bec08a70f731587d4ed0f218d5929285c8b2ccbc497e20db42de73885191fa453350335990184d8df805072f958d5354debda38f5421effaaafd6cb9b721ace74be0892d77679f62a4a126697cd35797f6858193da4ba1770c06aea2e5c59ec04b8ea26749e61b72ecdde403f3bc7e5e546cd799578cc939fa676dfd5e648576d4a06cbadb028adc2c0b461f145b2321f42e5e0f3b4fb898ecd461df07a6f5154067787bf74b5cc5c03704a1ce47494961931f0263b0aac32505102595957531a2de69dd71aac51f8a49902f81f21283dbe8e21e01e5d82517868826f86acf338d935aa6b4d5a25c8d540389b277dd9d64569d68baf0f71bd03dba45b92a7fc052601d1bd011a2fc6790a23f97c6fa5caeea040ab86841f268d39ce4f7caf01069df78bba098e04366492f0c2ac24f1bf16828752765fa523c9a4d42b71109d123e6be8c7b1ab3ccf8ea03404075fe1a9596f1bba1d267f9a7879ceece514818316c9c0583469d2367831fc42b517ea028a28df7c18d783d16ea2436cee2b15d52db68b5dfdee6b4d26f0905f9b030c911a04d078923a4136afea96eed6874462a482917353264cc9bee298f167ac65a6db4e4eda88044b39cc0b33183843eaa946564a00c3a0ab661f2c915e70bf0bb65bfbb6fa2eea20aed16bf2c1a1d00ec55fb4ff2f76b8e462ea70c19efa579c9ee78194b86708fdae66a9ce6e2cf3d366037798cfb50277ba6d2fd4866361022fd788ab7735b40b8b61d55e32243e06719e53992e9ac16c9c4b6e6933635c3c47c8f7e73e17dd54d0dd8aeba5d76de46894e7b3f9d3ec25ad78ee82297ba69905ea0fa094b8667faa2b8885e2187b3da80268aa1164761d7b0d6de206b676777348152b8ae1d4afed753bc63c739a5ca8ce7afb2b241a226bd9e502baba391b5b13f5054f070b65a9cf3a67063bfaa803ba390732cd03888f664023f888741d04d564e0b5674b0a183ace81452001b3fbb4214c77d42ca75376742c471e58f67307726d56a1032bd236610cbcbcd03d0d7a452900136897dc55bb3ce959d10d4e6a10fb635006bd8c41cd9ded2d3dfdd8f2e229590324a7370cb2124210b2330f4c56155caa09a2564932ceded8d92c79664dcdeb87faad7d3da006cc2ea267ee3df41e9677789cc5a8cc3b83add6491561b3047919e0648b1b2e97d7ad6f6c2aa80cab8e9ae10e1f75b1fdd0246151af709d259a6a0ed0b26bd711024965ecad7c41387de45443defce53f66612948694a6032279131c257119ed876a8e805dfb49576ef5c563574115ee87050d92d191bc761ef51d966918e2ef925639400069e3959d8fe19f36136e947ff430bf74e71da0aa5923b00000000")
813 v
:= natFromString("0x838332321d443a3d30373d47301d47073847473a383d3030f25b3d3d3e00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002e00000000000000000041603038331c3d32f5303441e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e01c0a5459bfc7b9be9fcbb9d2383840464319434707303030f43a32f53034411c0a5459413820878787878787878787878787878787878787878787878787878787878787878787870630303a3a30334036605b923a6101f83638413943413960204337602043323801526040523241846038414143015238604060328452413841413638523c0240384141364036605b923a6101f83638413943413960204334602043323801526040523241846038414143015238604060328452413841413638523c02403841413638433030f25a8b83838383838383838383838383838383837d838383ffffffffffffffff838383838383838383000000000000000000030000007d26e27c7c8b83838383838383838383838383838383837d838383ffffffffffffffff83838383838383838383838383838383838383838383435960f535073030f3343200000000000000011881301938343030fa398383300000002300000000000000000000f11af4600c845252904141364138383c60406032414443095238010241414303364443434132305b595a15434160b042385341ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff47476043410536613603593a6005411c437405fcfcfcfcfcfcfc0000000000005a3b075815054359000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")
814 q
:= nat(nil).make(16)