tree 42e388e27029f269f35eab8c1f99958dfc57308f
parent dc606a20ceeb48d68616f46f6ed24b1f5f0afe78
author Robert Griesemer <gri@golang.org> 1272420968 -0700
committer Robert Griesemer <gri@golang.org> 1272420968 -0700
golang-hg b75b37bee7eeefdea7a25a0dafada14db6a01f83

big: implemented Karatsuba multiplication

Plus:
- calibration "test" - include in tests with gotest -calibrate
- basic Mul benchmark
- extra multiplication tests
- various cleanups

This change improves multiplication speed of numbers >= 30 words
in length (current threshold; found empirically with calibrate):

The multiplication benchmark (multiplication of a variety of long numbers)
improves by ~35%, individual multiplies can be significantly faster.

gotest -benchmarks=Mul
big.BenchmarkMul	     500	   6829290 ns/op (w/ Karatsuba)
big.BenchmarkMul	     100	  10600760 ns/op

There's no impact on pidigits for -n=10000 or -n=20000
because the operands are are too small.

R=rsc
CC=golang-dev
https://golang.org/cl/1004042