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)
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
:= nat(nil).mulRange(r
.a
, r
.b
).decimalString()
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 toString(x nat
, charset
string) string {
215 panic("illegal base")
217 return string(charset
[0])
220 // allocate buffer for conversion
221 i
:= x
.bitLen()/log2(Word(base
)) + 1 // +1: round up
231 q
, r
= q
.divW(q
, Word(base
))
238 var strTests
= []struct {
239 x nat
// nat value to be converted
240 c
string // conversion charset
241 s
string // expected result
245 {nat
{0xc5}, "01", "11000101"},
246 {nat
{03271}, lowercaseDigits
[0:8], "3271"},
247 {nat
{10}, lowercaseDigits
[0:10], "10"},
248 {nat
{1234567890}, uppercaseDigits
[0:10], "1234567890"},
249 {nat
{0xdeadbeef}, lowercaseDigits
[0:16], "deadbeef"},
250 {nat
{0xdeadbeef}, uppercaseDigits
[0:16], "DEADBEEF"},
251 {nat
{0x229be7}, lowercaseDigits
[0:17], "1a2b3c"},
252 {nat
{0x309663e6}, uppercaseDigits
[0:32], "O9COV6"},
255 func TestString(t
*testing
.T
) {
256 for _
, a
:= range strTests
{
259 t
.Errorf("string%+v\n\tgot s = %s; want %s", a
, s
, a
.s
)
262 x
, b
, err
:= nat(nil).scan(strings
.NewReader(a
.s
), len(a
.c
))
264 t
.Errorf("scan%+v\n\tgot z = %v; want %v", a
, x
, a
.x
)
267 t
.Errorf("scan%+v\n\tgot b = %d; want %d", a
, b
, len(a
.c
))
270 t
.Errorf("scan%+v\n\tgot error = %s", a
, err
)
275 var natScanTests
= []struct {
276 s
string // string to be scanned
277 base
int // input base
278 x nat
// expected nat
279 b
int // expected base
280 ok
bool // expected success
281 next rune
// next character (or 0, if at EOF)
283 // error: illegal base
288 // error: no mantissa
298 {"0", 0, nil, 10, true, 0},
299 {"0", 10, nil, 10, true, 0},
300 {"0", 36, nil, 36, true, 0},
301 {"1", 0, nat
{1}, 10, true, 0},
302 {"1", 10, nat
{1}, 10, true, 0},
303 {"0 ", 0, nil, 10, true, ' '},
304 {"08", 0, nil, 10, true, '8'},
305 {"018", 0, nat
{1}, 8, true, '8'},
306 {"0b1", 0, nat
{1}, 2, true, 0},
307 {"0b11000101", 0, nat
{0xc5}, 2, true, 0},
308 {"03271", 0, nat
{03271}, 8, true, 0},
309 {"10ab", 0, nat
{10}, 10, true, 'a'},
310 {"1234567890", 0, nat
{1234567890}, 10, true, 0},
311 {"xyz", 36, nat
{(33*36+34)*36 + 35}, 36, true, 0},
312 {"xyz?", 36, nat
{(33*36+34)*36 + 35}, 36, true, '?'},
313 {"0x", 16, nil, 16, true, 'x'},
314 {"0xdeadbeef", 0, nat
{0xdeadbeef}, 16, true, 0},
315 {"0XDEADBEEF", 0, nat
{0xdeadbeef}, 16, true, 0},
318 func TestScanBase(t
*testing
.T
) {
319 for _
, a
:= range natScanTests
{
320 r
:= strings
.NewReader(a
.s
)
321 x
, b
, err
:= nat(nil).scan(r
, a
.base
)
322 if err
== nil && !a
.ok
{
323 t
.Errorf("scan%+v\n\texpected error", a
)
327 t
.Errorf("scan%+v\n\tgot error = %s", a
, err
)
332 t
.Errorf("scan%+v\n\tgot z = %v; want %v", a
, x
, a
.x
)
335 t
.Errorf("scan%+v\n\tgot b = %d; want %d", a
, b
, a
.base
)
337 next
, _
, err
:= r
.ReadRune()
342 if err
== nil && next
!= a
.next
{
343 t
.Errorf("scan%+v\n\tgot next = %q; want %q", a
, next
, a
.next
)
349 "14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" +
350 "32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" +
351 "28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" +
352 "96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" +
353 "31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" +
354 "60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" +
355 "22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" +
356 "29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" +
357 "81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" +
358 "21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" +
359 "55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" +
360 "63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" +
361 "75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" +
362 "45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" +
363 "34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" +
364 "16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" +
365 "04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" +
366 "26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" +
367 "99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" +
368 "53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" +
369 "68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" +
370 "13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" +
371 "88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" +
372 "79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" +
373 "68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" +
374 "21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" +
375 "06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" +
376 "14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" +
377 "21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" +
378 "05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" +
379 "23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" +
380 "90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" +
381 "31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" +
382 "20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" +
383 "97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" +
384 "44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" +
385 "44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" +
386 "85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" +
387 "58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" +
388 "27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" +
389 "09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" +
390 "79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" +
391 "06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" +
392 "91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" +
393 "94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" +
394 "78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" +
395 "24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" +
396 "59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" +
397 "34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" +
398 "88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" +
399 "94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337"
401 // Test case for BenchmarkScanPi.
402 func TestScanPi(t
*testing
.T
) {
404 z
, _
, err
:= x
.scan(strings
.NewReader(pi
), 10)
406 t
.Errorf("scanning pi: %s", err
)
408 if s
:= z
.decimalString(); s
!= pi
{
409 t
.Errorf("scanning pi: got %s", s
)
413 func TestScanPiParallel(t
*testing
.T
) {
416 for i
:= 0; i
< n
; i
++ {
422 for i
:= 0; i
< n
; i
++ {
427 func BenchmarkScanPi(b
*testing
.B
) {
428 for i
:= 0; i
< b
.N
; i
++ {
430 x
.scan(strings
.NewReader(pi
), 10)
434 func BenchmarkStringPiParallel(b
*testing
.B
) {
436 x
, _
, _
= x
.scan(strings
.NewReader(pi
), 0)
437 if x
.decimalString() != pi
{
438 panic("benchmark incorrect: conversion failed")
440 n
:= runtime
.GOMAXPROCS(0)
441 m
:= b
.N
/ n
// n*m <= b.N due to flooring, but the error is neglibible (n is not very large)
442 c
:= make(chan int, n
)
443 for i
:= 0; i
< n
; i
++ {
445 for j
:= 0; j
< m
; j
++ {
451 for i
:= 0; i
< n
; i
++ {
456 func BenchmarkScan10Base2(b
*testing
.B
) { ScanHelper(b
, 2, 10, 10) }
457 func BenchmarkScan100Base2(b
*testing
.B
) { ScanHelper(b
, 2, 10, 100) }
458 func BenchmarkScan1000Base2(b
*testing
.B
) { ScanHelper(b
, 2, 10, 1000) }
459 func BenchmarkScan10000Base2(b
*testing
.B
) { ScanHelper(b
, 2, 10, 10000) }
460 func BenchmarkScan100000Base2(b
*testing
.B
) { ScanHelper(b
, 2, 10, 100000) }
462 func BenchmarkScan10Base8(b
*testing
.B
) { ScanHelper(b
, 8, 10, 10) }
463 func BenchmarkScan100Base8(b
*testing
.B
) { ScanHelper(b
, 8, 10, 100) }
464 func BenchmarkScan1000Base8(b
*testing
.B
) { ScanHelper(b
, 8, 10, 1000) }
465 func BenchmarkScan10000Base8(b
*testing
.B
) { ScanHelper(b
, 8, 10, 10000) }
466 func BenchmarkScan100000Base8(b
*testing
.B
) { ScanHelper(b
, 8, 10, 100000) }
468 func BenchmarkScan10Base10(b
*testing
.B
) { ScanHelper(b
, 10, 10, 10) }
469 func BenchmarkScan100Base10(b
*testing
.B
) { ScanHelper(b
, 10, 10, 100) }
470 func BenchmarkScan1000Base10(b
*testing
.B
) { ScanHelper(b
, 10, 10, 1000) }
471 func BenchmarkScan10000Base10(b
*testing
.B
) { ScanHelper(b
, 10, 10, 10000) }
472 func BenchmarkScan100000Base10(b
*testing
.B
) { ScanHelper(b
, 10, 10, 100000) }
474 func BenchmarkScan10Base16(b
*testing
.B
) { ScanHelper(b
, 16, 10, 10) }
475 func BenchmarkScan100Base16(b
*testing
.B
) { ScanHelper(b
, 16, 10, 100) }
476 func BenchmarkScan1000Base16(b
*testing
.B
) { ScanHelper(b
, 16, 10, 1000) }
477 func BenchmarkScan10000Base16(b
*testing
.B
) { ScanHelper(b
, 16, 10, 10000) }
478 func BenchmarkScan100000Base16(b
*testing
.B
) { ScanHelper(b
, 16, 10, 100000) }
480 func ScanHelper(b
*testing
.B
, base
int, x
, y Word
) {
486 s
= z
.string(lowercaseDigits
[0:base
])
487 if t
:= toString(z
, lowercaseDigits
[0:base
]); t
!= s
{
488 b
.Fatalf("scanning: got %s; want %s", s
, t
)
492 for i
:= 0; i
< b
.N
; i
++ {
493 z
.scan(strings
.NewReader(s
), base
)
497 func BenchmarkString10Base2(b
*testing
.B
) { StringHelper(b
, 2, 10, 10) }
498 func BenchmarkString100Base2(b
*testing
.B
) { StringHelper(b
, 2, 10, 100) }
499 func BenchmarkString1000Base2(b
*testing
.B
) { StringHelper(b
, 2, 10, 1000) }
500 func BenchmarkString10000Base2(b
*testing
.B
) { StringHelper(b
, 2, 10, 10000) }
501 func BenchmarkString100000Base2(b
*testing
.B
) { StringHelper(b
, 2, 10, 100000) }
503 func BenchmarkString10Base8(b
*testing
.B
) { StringHelper(b
, 8, 10, 10) }
504 func BenchmarkString100Base8(b
*testing
.B
) { StringHelper(b
, 8, 10, 100) }
505 func BenchmarkString1000Base8(b
*testing
.B
) { StringHelper(b
, 8, 10, 1000) }
506 func BenchmarkString10000Base8(b
*testing
.B
) { StringHelper(b
, 8, 10, 10000) }
507 func BenchmarkString100000Base8(b
*testing
.B
) { StringHelper(b
, 8, 10, 100000) }
509 func BenchmarkString10Base10(b
*testing
.B
) { StringHelper(b
, 10, 10, 10) }
510 func BenchmarkString100Base10(b
*testing
.B
) { StringHelper(b
, 10, 10, 100) }
511 func BenchmarkString1000Base10(b
*testing
.B
) { StringHelper(b
, 10, 10, 1000) }
512 func BenchmarkString10000Base10(b
*testing
.B
) { StringHelper(b
, 10, 10, 10000) }
513 func BenchmarkString100000Base10(b
*testing
.B
) { StringHelper(b
, 10, 10, 100000) }
515 func BenchmarkString10Base16(b
*testing
.B
) { StringHelper(b
, 16, 10, 10) }
516 func BenchmarkString100Base16(b
*testing
.B
) { StringHelper(b
, 16, 10, 100) }
517 func BenchmarkString1000Base16(b
*testing
.B
) { StringHelper(b
, 16, 10, 1000) }
518 func BenchmarkString10000Base16(b
*testing
.B
) { StringHelper(b
, 16, 10, 10000) }
519 func BenchmarkString100000Base16(b
*testing
.B
) { StringHelper(b
, 16, 10, 100000) }
521 func StringHelper(b
*testing
.B
, base
int, x
, y Word
) {
525 z
.string(lowercaseDigits
[0:base
]) // warm divisor cache
528 for i
:= 0; i
< b
.N
; i
++ {
529 _
= z
.string(lowercaseDigits
[0:base
])
533 func BenchmarkLeafSize0(b
*testing
.B
) { LeafSizeHelper(b
, 10, 0) } // test without splitting
534 func BenchmarkLeafSize1(b
*testing
.B
) { LeafSizeHelper(b
, 10, 1) }
535 func BenchmarkLeafSize2(b
*testing
.B
) { LeafSizeHelper(b
, 10, 2) }
536 func BenchmarkLeafSize3(b
*testing
.B
) { LeafSizeHelper(b
, 10, 3) }
537 func BenchmarkLeafSize4(b
*testing
.B
) { LeafSizeHelper(b
, 10, 4) }
538 func BenchmarkLeafSize5(b
*testing
.B
) { LeafSizeHelper(b
, 10, 5) }
539 func BenchmarkLeafSize6(b
*testing
.B
) { LeafSizeHelper(b
, 10, 6) }
540 func BenchmarkLeafSize7(b
*testing
.B
) { LeafSizeHelper(b
, 10, 7) }
541 func BenchmarkLeafSize8(b
*testing
.B
) { LeafSizeHelper(b
, 10, 8) }
542 func BenchmarkLeafSize9(b
*testing
.B
) { LeafSizeHelper(b
, 10, 9) }
543 func BenchmarkLeafSize10(b
*testing
.B
) { LeafSizeHelper(b
, 10, 10) }
544 func BenchmarkLeafSize11(b
*testing
.B
) { LeafSizeHelper(b
, 10, 11) }
545 func BenchmarkLeafSize12(b
*testing
.B
) { LeafSizeHelper(b
, 10, 12) }
546 func BenchmarkLeafSize13(b
*testing
.B
) { LeafSizeHelper(b
, 10, 13) }
547 func BenchmarkLeafSize14(b
*testing
.B
) { LeafSizeHelper(b
, 10, 14) }
548 func BenchmarkLeafSize15(b
*testing
.B
) { LeafSizeHelper(b
, 10, 15) }
549 func BenchmarkLeafSize16(b
*testing
.B
) { LeafSizeHelper(b
, 10, 16) }
550 func BenchmarkLeafSize32(b
*testing
.B
) { LeafSizeHelper(b
, 10, 32) } // try some large lengths
551 func BenchmarkLeafSize64(b
*testing
.B
) { LeafSizeHelper(b
, 10, 64) }
553 func LeafSizeHelper(b
*testing
.B
, base Word
, size
int) {
555 originalLeafSize
:= leafSize
556 resetTable(cacheBase10
.table
[:])
560 for d
:= 1; d
<= 10000; d
*= 10 {
563 z
= z
.expWW(base
, Word(d
)) // build target number
564 _
= z
.string(lowercaseDigits
[0:base
]) // warm divisor cache
567 for i
:= 0; i
< b
.N
; i
++ {
568 _
= z
.string(lowercaseDigits
[0:base
])
573 resetTable(cacheBase10
.table
[:])
574 leafSize
= originalLeafSize
578 func resetTable(table
[]divisor
) {
579 if table
!= nil && table
[0].bbb
!= nil {
580 for i
:= 0; i
< len(table
); i
++ {
588 func TestStringPowers(t
*testing
.T
) {
590 for b
= 2; b
<= 16; b
++ {
591 for p
= 0; p
<= 512; p
++ {
592 x
:= nat(nil).expWW(b
, p
)
593 xs
:= x
.string(lowercaseDigits
[0:b
])
594 xs2
:= toString(x
, lowercaseDigits
[0:b
])
596 t
.Errorf("failed at %d ** %d in base %d: %s != %s", b
, p
, b
, xs
, xs2
)
599 if b
>= 3 && testing
.Short() {
605 func TestLeadingZeros(t
*testing
.T
) {
607 for i
:= 0; i
<= _W
; i
++ {
608 if int(leadingZeros(x
)) != i
{
609 t
.Errorf("failed at %x: got %d want %d", x
, leadingZeros(x
), i
)
615 type shiftTest
struct {
621 var leftShiftTests
= []shiftTest
{
626 {nat
{1 << (_W
- 1)}, 1, nat
{0}},
627 {nat
{1 << (_W
- 1), 0}, 1, nat
{0, 1}},
630 func TestShiftLeft(t
*testing
.T
) {
631 for i
, test
:= range leftShiftTests
{
633 z
= z
.shl(test
.in
, test
.shift
)
634 for j
, d
:= range test
.out
{
635 if j
>= len(z
) || z
[j
] != d
{
636 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
643 var rightShiftTests
= []shiftTest
{
649 {nat
{0, 1}, 1, nat
{1 << (_W
- 1)}},
650 {nat
{2, 1, 1}, 1, nat
{1<<(_W
-1) + 1, 1 << (_W
- 1)}},
653 func TestShiftRight(t
*testing
.T
) {
654 for i
, test
:= range rightShiftTests
{
656 z
= z
.shr(test
.in
, test
.shift
)
657 for j
, d
:= range test
.out
{
658 if j
>= len(z
) || z
[j
] != d
{
659 t
.Errorf("#%d: got: %v want: %v", i
, z
, test
.out
)
666 type modWTest
struct {
672 var modWTests32
= []modWTest
{
673 {"23492635982634928349238759823742", "252341", "220170"},
676 var modWTests64
= []modWTest
{
677 {"6527895462947293856291561095690465243862946", "524326975699234", "375066989628668"},
680 func runModWTests(t
*testing
.T
, tests
[]modWTest
) {
681 for i
, test
:= range tests
{
682 in
, _
:= new(Int
).SetString(test
.in
, 10)
683 d
, _
:= new(Int
).SetString(test
.dividend
, 10)
684 out
, _
:= new(Int
).SetString(test
.out
, 10)
686 r
:= in
.abs
.modW(d
.abs
[0])
688 t
.Errorf("#%d failed: got %d want %s", i
, r
, out
)
693 func TestModW(t
*testing
.T
) {
695 runModWTests(t
, modWTests32
)
698 runModWTests(t
, modWTests64
)
702 func TestTrailingZeroBits(t
*testing
.T
) {
704 for i
:= uint(0); i
<= _W
; i
++ {
705 n
:= trailingZeroBits(x
)
707 t
.Errorf("got trailingZeroBits(%#x) = %d; want %d", x
, n
, i%_W
)
712 y
:= nat(nil).set(natOne
)
713 for i
:= uint(0); i
<= 3*_W
; i
++ {
714 n
:= y
.trailingZeroBits()
716 t
.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y
.string(lowercaseDigits
[0:16]), n
, i
)
722 var expNNTests
= []struct {
726 {"0x8000000000000000", "2", "", "0x40000000000000000000000000000000"},
727 {"0x8000000000000000", "2", "6719", "4944"},
728 {"0x8000000000000000", "3", "6719", "5447"},
729 {"0x8000000000000000", "1000", "6719", "1603"},
730 {"0x8000000000000000", "1000000", "6719", "3199"},
732 "2938462938472983472983659726349017249287491026512746239764525612965293865296239471239874193284792387498274256129746192347",
733 "298472983472983471903246121093472394872319615612417471234712061",
734 "29834729834729834729347290846729561262544958723956495615629569234729836259263598127342374289365912465901365498236492183464",
735 "23537740700184054162508175125554701713153216681790245129157191391322321508055833908509185839069455749219131480588829346291",
739 func TestExpNN(t
*testing
.T
) {
740 for i
, test
:= range expNNTests
{
741 x
, _
, _
:= nat(nil).scan(strings
.NewReader(test
.x
), 0)
742 y
, _
, _
:= nat(nil).scan(strings
.NewReader(test
.y
), 0)
743 out
, _
, _
:= nat(nil).scan(strings
.NewReader(test
.out
), 0)
748 m
, _
, _
= nat(nil).scan(strings
.NewReader(test
.m
), 0)
751 z
:= nat(nil).expNN(x
, y
, m
)
753 t
.Errorf("#%d got %v want %v", i
, z
, out
)
758 func ExpHelper(b
*testing
.B
, x
, y Word
) {
760 for i
:= 0; i
< b
.N
; i
++ {
765 func BenchmarkExp3Power0x10(b
*testing
.B
) { ExpHelper(b
, 3, 0x10) }
766 func BenchmarkExp3Power0x40(b
*testing
.B
) { ExpHelper(b
, 3, 0x40) }
767 func BenchmarkExp3Power0x100(b
*testing
.B
) { ExpHelper(b
, 3, 0x100) }
768 func BenchmarkExp3Power0x400(b
*testing
.B
) { ExpHelper(b
, 3, 0x400) }
769 func BenchmarkExp3Power0x1000(b
*testing
.B
) { ExpHelper(b
, 3, 0x1000) }
770 func BenchmarkExp3Power0x4000(b
*testing
.B
) { ExpHelper(b
, 3, 0x4000) }
771 func BenchmarkExp3Power0x10000(b
*testing
.B
) { ExpHelper(b
, 3, 0x10000) }
772 func BenchmarkExp3Power0x40000(b
*testing
.B
) { ExpHelper(b
, 3, 0x40000) }
773 func BenchmarkExp3Power0x100000(b
*testing
.B
) { ExpHelper(b
, 3, 0x100000) }
774 func BenchmarkExp3Power0x400000(b
*testing
.B
) { ExpHelper(b
, 3, 0x400000) }