Home | History | Annotate | Download | only in big 
      1 // Copyright 2015 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.
      4 
      5 package big
      6 
      7 import (
      8 	"bytes"
      9 	"fmt"
     10 	"io"
     11 	"strings"
     12 	"testing"
     13 )
     14 
     15 func itoa(x nat, base int) []byte {
     16 	// special cases
     17 	switch {
     18 	case base < 2:
     19 		panic("illegal base")
     20 	case len(x) == 0:
     21 		return []byte("0")
     22 	}
     23 
     24 	// allocate buffer for conversion
     25 	i := x.bitLen()/log2(Word(base)) + 1 // +1: round up
     26 	s := make([]byte, i)
     27 
     28 	// don't destroy x
     29 	q := nat(nil).set(x)
     30 
     31 	// convert
     32 	for len(q) > 0 {
     33 		i--
     34 		var r Word
     35 		q, r = q.divW(q, Word(base))
     36 		s[i] = digits[r]
     37 	}
     38 
     39 	return s[i:]
     40 }
     41 
     42 var strTests = []struct {
     43 	x nat    // nat value to be converted
     44 	b int    // conversion base
     45 	s string // expected result
     46 }{
     47 	{nil, 2, "0"},
     48 	{nat{1}, 2, "1"},
     49 	{nat{0xc5}, 2, "11000101"},
     50 	{nat{03271}, 8, "3271"},
     51 	{nat{10}, 10, "10"},
     52 	{nat{1234567890}, 10, "1234567890"},
     53 	{nat{0xdeadbeef}, 16, "deadbeef"},
     54 	{nat{0x229be7}, 17, "1a2b3c"},
     55 	{nat{0x309663e6}, 32, "o9cov6"},
     56 }
     57 
     58 func TestString(t *testing.T) {
     59 	// test invalid base explicitly
     60 	var panicStr string
     61 	func() {
     62 		defer func() {
     63 			panicStr = recover().(string)
     64 		}()
     65 		natOne.utoa(1)
     66 	}()
     67 	if panicStr != "invalid base" {
     68 		t.Errorf("expected panic for invalid base")
     69 	}
     70 
     71 	for _, a := range strTests {
     72 		s := string(a.x.utoa(a.b))
     73 		if s != a.s {
     74 			t.Errorf("string%+v\n\tgot s = %s; want %s", a, s, a.s)
     75 		}
     76 
     77 		x, b, _, err := nat(nil).scan(strings.NewReader(a.s), a.b, false)
     78 		if x.cmp(a.x) != 0 {
     79 			t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
     80 		}
     81 		if b != a.b {
     82 			t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.b)
     83 		}
     84 		if err != nil {
     85 			t.Errorf("scan%+v\n\tgot error = %s", a, err)
     86 		}
     87 	}
     88 }
     89 
     90 var natScanTests = []struct {
     91 	s     string // string to be scanned
     92 	base  int    // input base
     93 	frac  bool   // fraction ok
     94 	x     nat    // expected nat
     95 	b     int    // expected base
     96 	count int    // expected digit count
     97 	ok    bool   // expected success
     98 	next  rune   // next character (or 0, if at EOF)
     99 }{
    100 	// error: no mantissa
    101 	{},
    102 	{s: "?"},
    103 	{base: 10},
    104 	{base: 36},
    105 	{s: "?", base: 10},
    106 	{s: "0x"},
    107 	{s: "345", base: 2},
    108 
    109 	// error: incorrect use of decimal point
    110 	{s: ".0"},
    111 	{s: ".0", base: 10},
    112 	{s: ".", base: 0},
    113 	{s: "0x.0"},
    114 
    115 	// no errors
    116 	{"0", 0, false, nil, 10, 1, true, 0},
    117 	{"0", 10, false, nil, 10, 1, true, 0},
    118 	{"0", 36, false, nil, 36, 1, true, 0},
    119 	{"1", 0, false, nat{1}, 10, 1, true, 0},
    120 	{"1", 10, false, nat{1}, 10, 1, true, 0},
    121 	{"0 ", 0, false, nil, 10, 1, true, ' '},
    122 	{"08", 0, false, nil, 10, 1, true, '8'},
    123 	{"08", 10, false, nat{8}, 10, 2, true, 0},
    124 	{"018", 0, false, nat{1}, 8, 1, true, '8'},
    125 	{"0b1", 0, false, nat{1}, 2, 1, true, 0},
    126 	{"0b11000101", 0, false, nat{0xc5}, 2, 8, true, 0},
    127 	{"03271", 0, false, nat{03271}, 8, 4, true, 0},
    128 	{"10ab", 0, false, nat{10}, 10, 2, true, 'a'},
    129 	{"1234567890", 0, false, nat{1234567890}, 10, 10, true, 0},
    130 	{"xyz", 36, false, nat{(33*36+34)*36 + 35}, 36, 3, true, 0},
    131 	{"xyz?", 36, false, nat{(33*36+34)*36 + 35}, 36, 3, true, '?'},
    132 	{"0x", 16, false, nil, 16, 1, true, 'x'},
    133 	{"0xdeadbeef", 0, false, nat{0xdeadbeef}, 16, 8, true, 0},
    134 	{"0XDEADBEEF", 0, false, nat{0xdeadbeef}, 16, 8, true, 0},
    135 
    136 	// no errors, decimal point
    137 	{"0.", 0, false, nil, 10, 1, true, '.'},
    138 	{"0.", 10, true, nil, 10, 0, true, 0},
    139 	{"0.1.2", 10, true, nat{1}, 10, -1, true, '.'},
    140 	{".000", 10, true, nil, 10, -3, true, 0},
    141 	{"12.3", 10, true, nat{123}, 10, -1, true, 0},
    142 	{"012.345", 10, true, nat{12345}, 10, -3, true, 0},
    143 }
    144 
    145 func TestScanBase(t *testing.T) {
    146 	for _, a := range natScanTests {
    147 		r := strings.NewReader(a.s)
    148 		x, b, count, err := nat(nil).scan(r, a.base, a.frac)
    149 		if err == nil && !a.ok {
    150 			t.Errorf("scan%+v\n\texpected error", a)
    151 		}
    152 		if err != nil {
    153 			if a.ok {
    154 				t.Errorf("scan%+v\n\tgot error = %s", a, err)
    155 			}
    156 			continue
    157 		}
    158 		if x.cmp(a.x) != 0 {
    159 			t.Errorf("scan%+v\n\tgot z = %v; want %v", a, x, a.x)
    160 		}
    161 		if b != a.b {
    162 			t.Errorf("scan%+v\n\tgot b = %d; want %d", a, b, a.base)
    163 		}
    164 		if count != a.count {
    165 			t.Errorf("scan%+v\n\tgot count = %d; want %d", a, count, a.count)
    166 		}
    167 		next, _, err := r.ReadRune()
    168 		if err == io.EOF {
    169 			next = 0
    170 			err = nil
    171 		}
    172 		if err == nil && next != a.next {
    173 			t.Errorf("scan%+v\n\tgot next = %q; want %q", a, next, a.next)
    174 		}
    175 	}
    176 }
    177 
    178 var pi = "3" +
    179 	"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651" +
    180 	"32823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461" +
    181 	"28475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920" +
    182 	"96282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179" +
    183 	"31051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798" +
    184 	"60943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901" +
    185 	"22495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999837" +
    186 	"29780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083" +
    187 	"81420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909" +
    188 	"21642019893809525720106548586327886593615338182796823030195203530185296899577362259941389124972177528347913151" +
    189 	"55748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035" +
    190 	"63707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104" +
    191 	"75216205696602405803815019351125338243003558764024749647326391419927260426992279678235478163600934172164121992" +
    192 	"45863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818" +
    193 	"34797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548" +
    194 	"16136115735255213347574184946843852332390739414333454776241686251898356948556209921922218427255025425688767179" +
    195 	"04946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886" +
    196 	"26945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645" +
    197 	"99581339047802759009946576407895126946839835259570982582262052248940772671947826848260147699090264013639443745" +
    198 	"53050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382" +
    199 	"68683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244" +
    200 	"13654976278079771569143599770012961608944169486855584840635342207222582848864815845602850601684273945226746767" +
    201 	"88952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288" +
    202 	"79710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821" +
    203 	"68299894872265880485756401427047755513237964145152374623436454285844479526586782105114135473573952311342716610" +
    204 	"21359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435" +
    205 	"06430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675" +
    206 	"14269123974894090718649423196156794520809514655022523160388193014209376213785595663893778708303906979207734672" +
    207 	"21825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539" +
    208 	"05796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007" +
    209 	"23055876317635942187312514712053292819182618612586732157919841484882916447060957527069572209175671167229109816" +
    210 	"90915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398" +
    211 	"31501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064" +
    212 	"20467525907091548141654985946163718027098199430992448895757128289059232332609729971208443357326548938239119325" +
    213 	"97463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100" +
    214 	"44929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915" +
    215 	"44110104468232527162010526522721116603966655730925471105578537634668206531098965269186205647693125705863566201" +
    216 	"85581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318" +
    217 	"58676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797" +
    218 	"27082668306343285878569830523580893306575740679545716377525420211495576158140025012622859413021647155097925923" +
    219 	"09907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111" +
    220 	"79042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043" +
    221 	"06332175182979866223717215916077166925474873898665494945011465406284336639379003976926567214638530673609657120" +
    222 	"91807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862" +
    223 	"94726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939" +
    224 	"78054193414473774418426312986080998886874132604721569516239658645730216315981931951673538129741677294786724229" +
    225 	"24654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001" +
    226 	"59377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541" +
    227 	"34189948544473456738316249934191318148092777710386387734317720754565453220777092120190516609628049092636019759" +
    228 	"88281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267" +
    229 	"94561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337"
    230 
    231 // Test case for BenchmarkScanPi.
    232 func TestScanPi(t *testing.T) {
    233 	var x nat
    234 	z, _, _, err := x.scan(strings.NewReader(pi), 10, false)
    235 	if err != nil {
    236 		t.Errorf("scanning pi: %s", err)
    237 	}
    238 	if s := string(z.utoa(10)); s != pi {
    239 		t.Errorf("scanning pi: got %s", s)
    240 	}
    241 }
    242 
    243 func TestScanPiParallel(t *testing.T) {
    244 	const n = 2
    245 	c := make(chan int)
    246 	for i := 0; i < n; i++ {
    247 		go func() {
    248 			TestScanPi(t)
    249 			c <- 0
    250 		}()
    251 	}
    252 	for i := 0; i < n; i++ {
    253 		<-c
    254 	}
    255 }
    256 
    257 func BenchmarkScanPi(b *testing.B) {
    258 	for i := 0; i < b.N; i++ {
    259 		var x nat
    260 		x.scan(strings.NewReader(pi), 10, false)
    261 	}
    262 }
    263 
    264 func BenchmarkStringPiParallel(b *testing.B) {
    265 	var x nat
    266 	x, _, _, _ = x.scan(strings.NewReader(pi), 0, false)
    267 	if string(x.utoa(10)) != pi {
    268 		panic("benchmark incorrect: conversion failed")
    269 	}
    270 	b.RunParallel(func(pb *testing.PB) {
    271 		for pb.Next() {
    272 			x.utoa(10)
    273 		}
    274 	})
    275 }
    276 
    277 func BenchmarkScan(b *testing.B) {
    278 	const x = 10
    279 	for _, base := range []int{2, 8, 10, 16} {
    280 		for _, y := range []Word{10, 100, 1000, 10000, 100000} {
    281 			if isRaceBuilder && y > 1000 {
    282 				continue
    283 			}
    284 			b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) {
    285 				b.StopTimer()
    286 				var z nat
    287 				z = z.expWW(x, y)
    288 
    289 				s := z.utoa(base)
    290 				if t := itoa(z, base); !bytes.Equal(s, t) {
    291 					b.Fatalf("scanning: got %s; want %s", s, t)
    292 				}
    293 				b.StartTimer()
    294 
    295 				for i := 0; i < b.N; i++ {
    296 					z.scan(bytes.NewReader(s), base, false)
    297 				}
    298 			})
    299 		}
    300 	}
    301 }
    302 
    303 func BenchmarkString(b *testing.B) {
    304 	const x = 10
    305 	for _, base := range []int{2, 8, 10, 16} {
    306 		for _, y := range []Word{10, 100, 1000, 10000, 100000} {
    307 			if isRaceBuilder && y > 1000 {
    308 				continue
    309 			}
    310 			b.Run(fmt.Sprintf("%d/Base%d", y, base), func(b *testing.B) {
    311 				b.StopTimer()
    312 				var z nat
    313 				z = z.expWW(x, y)
    314 				z.utoa(base) // warm divisor cache
    315 				b.StartTimer()
    316 
    317 				for i := 0; i < b.N; i++ {
    318 					_ = z.utoa(base)
    319 				}
    320 			})
    321 		}
    322 	}
    323 }
    324 
    325 func BenchmarkLeafSize(b *testing.B) {
    326 	for n := 0; n <= 16; n++ {
    327 		b.Run(fmt.Sprint(n), func(b *testing.B) { LeafSizeHelper(b, 10, n) })
    328 	}
    329 	// Try some large lengths
    330 	for _, n := range []int{32, 64} {
    331 		b.Run(fmt.Sprint(n), func(b *testing.B) { LeafSizeHelper(b, 10, n) })
    332 	}
    333 }
    334 
    335 func LeafSizeHelper(b *testing.B, base, size int) {
    336 	b.StopTimer()
    337 	originalLeafSize := leafSize
    338 	resetTable(cacheBase10.table[:])
    339 	leafSize = size
    340 	b.StartTimer()
    341 
    342 	for d := 1; d <= 10000; d *= 10 {
    343 		b.StopTimer()
    344 		var z nat
    345 		z = z.expWW(Word(base), Word(d)) // build target number
    346 		_ = z.utoa(base)                 // warm divisor cache
    347 		b.StartTimer()
    348 
    349 		for i := 0; i < b.N; i++ {
    350 			_ = z.utoa(base)
    351 		}
    352 	}
    353 
    354 	b.StopTimer()
    355 	resetTable(cacheBase10.table[:])
    356 	leafSize = originalLeafSize
    357 	b.StartTimer()
    358 }
    359 
    360 func resetTable(table []divisor) {
    361 	if table != nil && table[0].bbb != nil {
    362 		for i := 0; i < len(table); i++ {
    363 			table[i].bbb = nil
    364 			table[i].nbits = 0
    365 			table[i].ndigits = 0
    366 		}
    367 	}
    368 }
    369 
    370 func TestStringPowers(t *testing.T) {
    371 	var p Word
    372 	for b := 2; b <= 16; b++ {
    373 		for p = 0; p <= 512; p++ {
    374 			x := nat(nil).expWW(Word(b), p)
    375 			xs := x.utoa(b)
    376 			xs2 := itoa(x, b)
    377 			if !bytes.Equal(xs, xs2) {
    378 				t.Errorf("failed at %d ** %d in base %d: %s != %s", b, p, b, xs, xs2)
    379 			}
    380 		}
    381 		if b >= 3 && testing.Short() {
    382 			break
    383 		}
    384 	}
    385 }
    386