• Robert Griesemer's avatar
    big: implemented Karatsuba multiplication · b2183701
    Robert Griesemer authored
    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
    b2183701
int.go 7.2 KB