]> Cypherpunks repositories - gostls13.git/commit
big: improved computation of "karatsuba length" for faster multiplies
authorRobert Griesemer <gri@golang.org>
Fri, 30 Apr 2010 18:54:27 +0000 (11:54 -0700)
committerRobert Griesemer <gri@golang.org>
Fri, 30 Apr 2010 18:54:27 +0000 (11:54 -0700)
commit407dbb42d40374ac4a9ecd54a5f8f13ee5d165d4
tree6d4ca71c585da8cd14daf7270d02455ff0fd0efe
parentf78b09e6734ef69f3acfbf4defdaecc000466f6b
big: improved computation of "karatsuba length" for faster multiplies

This results in an improvement of > 35% for the existing Mul benchmark
using the same karatsuba threshold, and an improvement of > 50% with
a slightly higher threshold (32 instead of 30):

big.BenchmarkMul           500    6731846 ns/op (old alg.)
big.BenchmarkMul    500    4351122 ns/op (new alg.)
big.BenchmarkMul           500    3133782 ns/op (new alg., new theshold)

Also:
- tweaked calibrate.go, use same benchmark as for Mul benchmark

R=rsc
CC=golang-dev
https://golang.org/cl/1037041
src/pkg/big/calibrate_test.go
src/pkg/big/nat.go
src/pkg/big/nat_test.go