diff options
| author | Evan Shaw <chickencha@gmail.com> | 2010-04-20 20:39:36 -0700 |
|---|---|---|
| committer | Evan Shaw <chickencha@gmail.com> | 2010-04-20 20:39:36 -0700 |
| commit | 46914854ff711a1dd6f46ab7c62f78acade05a72 (patch) | |
| tree | 97187583895cbbfba584e51112fbea6541318de9 /test/bench/pidigits.go | |
| parent | c6746a7efa9025613f143569c338ebc5ffba7913 (diff) | |
| download | golang-46914854ff711a1dd6f46ab7c62f78acade05a72.tar.gz | |
big: Add Lsh and Value; convert pidigits to use big
This yields a pretty significant performance boost to pidigits and there are still some improvements to be made. Here are my numbers:
amd64 w/ bignum:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r
gc pidigits 22.92u 0.02s 22.97r
gc_B pidigits 22.62u 0.00s 22.65r
amd64 w/ big:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.09u 0.02s 2.11r
gc pidigits 12.68u 0.04s 12.72r
gc_B pidigits 12.71u 0.03s 12.75r
386 w/ bignum:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.09u 0.00s 2.09r
gc pidigits 44.30u 0.01s 44.35r
gc_B pidigits 44.29u 0.03s 44.35r
386 w/ big:
pidigits 10000
gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r
gc pidigits 22.70u 0.06s 22.79r
gc_B pidigits 22.80u 0.09s 22.91r
R=rsc, gri
CC=golang-dev
http://codereview.appspot.com/881050
Committer: Russ Cox <rsc@golang.org>
Diffstat (limited to 'test/bench/pidigits.go')
| -rw-r--r-- | test/bench/pidigits.go | 50 |
1 files changed, 28 insertions, 22 deletions
diff --git a/test/bench/pidigits.go b/test/bench/pidigits.go index aaa9f53a5..a05515028 100644 --- a/test/bench/pidigits.go +++ b/test/bench/pidigits.go @@ -38,7 +38,7 @@ POSSIBILITY OF SUCH DAMAGE. package main import ( - "bignum" + "big" "flag" "fmt" ) @@ -47,11 +47,14 @@ var n = flag.Int("n", 27, "number of digits") var silent = flag.Bool("s", false, "don't print result") var ( - tmp1 *bignum.Integer - tmp2 *bignum.Integer - numer = bignum.Int(1) - accum = bignum.Int(0) - denom = bignum.Int(1) + tmp1 = big.NewInt(0) + tmp2 = big.NewInt(0) + y2 = big.NewInt(0) + bigk = big.NewInt(0) + numer = big.NewInt(1) + accum = big.NewInt(0) + denom = big.NewInt(1) + ten = big.NewInt(10) ) func extract_digit() int64 { @@ -60,36 +63,39 @@ func extract_digit() int64 { } // Compute (numer * 3 + accum) / denom - tmp1 = numer.Shl(1) - bignum.Iadd(tmp1, tmp1, numer) - bignum.Iadd(tmp1, tmp1, accum) - tmp1, tmp2 := tmp1.QuoRem(denom) + tmp1.Lsh(numer, 1) + tmp1.Add(tmp1, numer) + tmp1.Add(tmp1, accum) + tmp1.DivMod(tmp1, denom, tmp2) // Now, if (numer * 4 + accum) % denom... - bignum.Iadd(tmp2, tmp2, numer) + tmp2.Add(tmp2, numer) // ... is normalized, then the two divisions have the same result. if tmp2.Cmp(denom) >= 0 { return -1 } - return tmp1.Value() + return tmp1.Int64() } func next_term(k int64) { - y2 := k*2 + 1 - - tmp1 = numer.Shl(1) - bignum.Iadd(accum, accum, tmp1) - bignum.Iscale(accum, y2) - bignum.Iscale(numer, k) - bignum.Iscale(denom, y2) + // TODO(eds) If big.Int ever gets a Scale method, y2 and bigk could be int64 + y2.New(k*2 + 1) + bigk.New(k) + + tmp1.Lsh(numer, 1) + accum.Add(accum, tmp1) + accum.Mul(accum, y2) + numer.Mul(numer, bigk) + denom.Mul(denom, y2) } func eliminate_digit(d int64) { - bignum.Isub(accum, accum, denom.Mul1(d)) - bignum.Iscale(accum, 10) - bignum.Iscale(numer, 10) + tmp := big.NewInt(0).Set(denom) + accum.Sub(accum, tmp.Mul(tmp, big.NewInt(d))) + accum.Mul(accum, ten) + numer.Mul(numer, ten) } func printf(s string, arg ...interface{}) { |