← Back to branch summary

~ubuntu-branches/ubuntu/utopic/golang/utopic

« back to all changes in this revision

Viewing changes to src/pkg/math/big/nat_test.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/math/big/nat_test.go
6
6
 
7
7
import (
8
8
        "io"
 
9
        "runtime"
9
10
        "strings"
10
11
        "testing"
11
12
)
62
63
        {nat{0, 0, 991 * 991}, nat{0, 991}, nat{0, 991}},
63
64
        {nat{1 * 991, 2 * 991, 3 * 991, 4 * 991}, nat{1, 2, 3, 4}, nat{991}},
64
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
 
67
        {
 
68
                natFromString("11790184577738583171520872861412518665678211592275841109096961"),
 
69
                natFromString("515377520732011331036461129765621272702107522001"),
 
70
                natFromString("22876792454961"),
 
71
        },
 
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)
 
75
        {
 
76
                natFromString(strings.Repeat("1", 70000)),
 
77
                natFromString("1" + strings.Repeat(strings.Repeat("0", 699)+"1", 99)),
 
78
                natFromString(strings.Repeat("1", 700)),
 
79
        },
 
80
        // z = 111....1 (20000 digits)
 
81
        // x = 10^10000 + 1
 
82
        // y = 111....1 (10000 digits)
 
83
        {
 
84
                natFromString(strings.Repeat("1", 20000)),
 
85
                natFromString("1" + strings.Repeat("0", 9999) + "1"),
 
86
                natFromString(strings.Repeat("1", 10000)),
 
87
        },
 
88
}
 
89
 
 
90
func natFromString(s string) nat {
 
91
        x, _, err := nat(nil).scan(strings.NewReader(s), 0)
 
92
        if err != nil {
 
93
                panic(err)
 
94
        }
 
95
        return x
65
96
}
66
97
 
67
98
func TestSet(t *testing.T) {
135
166
        }
136
167
}
137
168
 
138
 
var mulArg, mulTmp nat
139
 
 
140
 
func init() {
141
 
        const n = 1000
142
 
        mulArg = make(nat, n)
143
 
        for i := 0; i < n; i++ {
144
 
                mulArg[i] = _M
145
 
        }
146
 
}
147
 
 
148
 
func benchmarkMulLoad() {
149
 
        for j := 1; j <= 10; j++ {
150
 
                x := mulArg[0 : j*100]
151
 
                mulTmp.mul(x, x)
152
 
        }
 
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
 
174
        f()
 
175
        runtime.ReadMemStats(&stats)
 
176
        return stats.TotalAlloc - t
 
177
}
 
178
 
 
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))
 
184
        x := rndNat(50000)
 
185
        y := rndNat(40)
 
186
        allocSize := allocBytes(func() {
 
187
                nat(nil).mul(x, y)
 
188
        })
 
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)
 
192
        }
 
193
}
 
194
 
 
195
func rndNat(n int) nat {
 
196
        return nat(rndV(n)).norm()
153
197
}
154
198
 
155
199
func BenchmarkMul(b *testing.B) {
 
200
        mulx := rndNat(1e4)
 
201
        muly := rndNat(1e4)
 
202
        b.ResetTimer()
156
203
        for i := 0; i < b.N; i++ {
157
 
                benchmarkMulLoad()
 
204
                var z nat
 
205
                z.mul(mulx, muly)
158
206
        }
159
207
}
160
208
 
362
410
        }
363
411
}
364
412
 
 
413
func TestScanPiParallel(t *testing.T) {
 
414
        const n = 2
 
415
        c := make(chan int)
 
416
        for i := 0; i < n; i++ {
 
417
                go func() {
 
418
                        TestScanPi(t)
 
419
                        c <- 0
 
420
                }()
 
421
        }
 
422
        for i := 0; i < n; i++ {
 
423
                <-c
 
424
        }
 
425
}
 
426
 
365
427
func BenchmarkScanPi(b *testing.B) {
366
428
        for i := 0; i < b.N; i++ {
367
429
                var x nat
369
431
        }
370
432
}
371
433
 
 
434
func BenchmarkStringPiParallel(b *testing.B) {
 
435
        var x nat
 
436
        x, _, _ = x.scan(strings.NewReader(pi), 0)
 
437
        if x.decimalString() != pi {
 
438
                panic("benchmark incorrect: conversion failed")
 
439
        }
 
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++ {
 
444
                go func() {
 
445
                        for j := 0; j < m; j++ {
 
446
                                x.decimalString()
 
447
                        }
 
448
                        c <- 0
 
449
                }()
 
450
        }
 
451
        for i := 0; i < n; i++ {
 
452
                <-c
 
453
        }
 
454
}
 
455
 
372
456
func BenchmarkScan10Base2(b *testing.B)     { ScanHelper(b, 2, 10, 10) }
373
457
func BenchmarkScan100Base2(b *testing.B)    { ScanHelper(b, 2, 10, 100) }
374
458
func BenchmarkScan1000Base2(b *testing.B)   { ScanHelper(b, 2, 10, 1000) }
463
547
func BenchmarkLeafSize14(b *testing.B) { LeafSizeHelper(b, 10, 14) }
464
548
func BenchmarkLeafSize15(b *testing.B) { LeafSizeHelper(b, 10, 15) }
465
549
func BenchmarkLeafSize16(b *testing.B) { LeafSizeHelper(b, 10, 16) }
466
 
func BenchmarkLeafSize32(b *testing.B) { LeafSizeHelper(b, 10, 32) } // try some large lengths 
 
550
func BenchmarkLeafSize32(b *testing.B) { LeafSizeHelper(b, 10, 32) } // try some large lengths
467
551
func BenchmarkLeafSize64(b *testing.B) { LeafSizeHelper(b, 10, 64) }
468
552
 
469
553
func LeafSizeHelper(b *testing.B, base Word, size int) {
470
554
        b.StopTimer()
471
555
        originalLeafSize := leafSize
472
 
        resetTable(cacheBase10[:])
 
556
        resetTable(cacheBase10.table[:])
473
557
        leafSize = size
474
558
        b.StartTimer()
475
559
 
486
570
        }
487
571
 
488
572
        b.StopTimer()
489
 
        resetTable(cacheBase10[:])
 
573
        resetTable(cacheBase10.table[:])
490
574
        leafSize = originalLeafSize
491
575
        b.StartTimer()
492
576
}
616
700
}
617
701
 
618
702
func TestTrailingZeroBits(t *testing.T) {
619
 
        var x Word
620
 
        x--
621
 
        for i := 0; i < _W; i++ {
622
 
                if trailingZeroBits(x) != i {
623
 
                        t.Errorf("Failed at step %d: x: %x got: %d", i, x, trailingZeroBits(x))
 
703
        x := Word(1)
 
704
        for i := uint(0); i <= _W; i++ {
 
705
                n := trailingZeroBits(x)
 
706
                if n != i%_W {
 
707
                        t.Errorf("got trailingZeroBits(%#x) = %d; want %d", x, n, i%_W)
624
708
                }
625
709
                x <<= 1
626
710
        }
 
711
 
 
712
        y := nat(nil).set(natOne)
 
713
        for i := uint(0); i <= 3*_W; i++ {
 
714
                n := y.trailingZeroBits()
 
715
                if n != i {
 
716
                        t.Errorf("got 0x%s.trailingZeroBits() = %d; want %d", y.string(lowercaseDigits[0:16]), n, i)
 
717
                }
 
718
                y = y.shl(y, 1)
 
719
        }
627
720
}
628
721
 
629
722
var expNNTests = []struct {