Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(355)

Side by Side Diff: src/pkg/big/calibrate_test.go

Issue 1004042: code review 1004042: big: implemented Karatsuba multiplication (Closed)
Patch Set: code review 1004042: big: implemented Karatsuba multiplication Created 13 years, 11 months ago
Left:
Right:
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | src/pkg/big/int.go » ('j') | src/pkg/big/nat.go » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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.
4
5 // This file computes the Karatsuba threshold as a "test".
6 // Usage: gotest -calibrate
7
8 package big
9
10 import (
11 "flag"
12 "fmt"
13 "testing"
14 "time"
15 "unsafe" // for Sizeof
16 )
17
18
19 var calibrate = flag.Bool("calibrate", false, "run calibration test")
20
21
22 // makeNumber creates an n-word number 0xffff...ffff
23 func makeNumber(n int) *Int {
24 var w Word
25 b := make([]byte, n*unsafe.Sizeof(w))
26 for i := range b {
27 b[i] = 0xff
28 }
29 var x Int
30 x.SetBytes(b)
31 return &x
32 }
33
34
35 // measure returns the time to compute x*x in nanoseconds
36 func measure(f func()) int64 {
37 const N = 100
38 start := time.Nanoseconds()
39 for i := N; i > 0; i-- {
40 f()
41 }
42 stop := time.Nanoseconds()
43 return (stop - start) / N
44 }
45
46
47 func computeThreshold(t *testing.T) int {
48 // use a mix of numbers as work load
49 x := make([]*Int, 20)
50 for i := range x {
51 x[i] = makeNumber(10 * (i + 1))
52 }
53
54 threshold := -1
55 for n := 8; threshold < 0 || n <= threshold+20; n += 2 {
56 // set work load
57 f := func() {
58 var t Int
59 for _, x := range x {
60 t.Mul(x, x)
61 }
62 }
63
64 karatsubaThreshold = 1e9 // disable karatsuba
65 t1 := measure(f)
66
67 karatsubaThreshold = n // enable karatsuba
68 t2 := measure(f)
69
70 c := '<'
71 mark := ""
72 if t1 > t2 {
73 c = '>'
74 if threshold < 0 {
75 threshold = n
76 mark = " *"
77 }
78 }
79
80 fmt.Printf("%4d: %8d %c %8d%s\n", n, t1, c, t2, mark)
81 }
82 return threshold
83 }
84
85
86 func TestCalibrate(t *testing.T) {
87 if *calibrate {
88 fmt.Printf("Computing Karatsuba threshold\n")
89 fmt.Printf("threshold = %d\n", computeThreshold(t))
90 }
91 }
OLDNEW
« no previous file with comments | « no previous file | src/pkg/big/int.go » ('j') | src/pkg/big/nat.go » ('J')

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b