code review 963044: big: use fast shift routines

big: use fast shift routines

- fixed a couple of bugs in the process
  (shift right was incorrect for negative numbers)
- added more tests and made some tests more robust
- changed pidigits back to using shifts to multiply
  by 2 instead of add

  This improves pidigit -s -n 10000 by approx. 5%:

  user 0m6.496s (old)
  user 0m6.156s (new)

[gri, 2010-05-01 00:17:33]

Hello rsc (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[rsc1, 2010-05-01 00:38:35]

LGTM

http://codereview.appspot.com/963044/diff/2001/3003
File src/pkg/big/nat.go (right):

http://codereview.appspot.com/963044/diff/2001/3003#newcode557
src/pkg/big/nat.go:557: v.shiftLeftDeprecated(v, shift)
?

http://codereview.appspot.com/963044/diff/2001/3003#newcode828
src/pkg/big/nat.go:828: //           used directly in divLarge and
powersOfTwoDecompose
Say why they can't be used directly now?
The only guess I have is the overlap case but
it looks like the routines above already handle that.

[gri, 2010-05-01 02:57:11]

It is the overlap case. Since the result and the argument are the same in
DivLarge we have always overlap but DivLarge requires the shift to operate
in place (or at the very least it's inefficient not to do so; I haven't
looked at the other routine in detail).
- Robert

On Fri, Apr 30, 2010 at 5:38 PM, <rsc@google.com> wrote:

> LGTM
>
>
>
> http://codereview.appspot.com/963044/diff/2001/3003
> File src/pkg/big/nat.go (right):
>
> http://codereview.appspot.com/963044/diff/2001/3003#newcode557
> src/pkg/big/nat.go:557: v.shiftLeftDeprecated(v, shift)
> ?
>
> http://codereview.appspot.com/963044/diff/2001/3003#newcode828
> src/pkg/big/nat.go:828: //           used directly in divLarge and
> powersOfTwoDecompose
> Say why they can't be used directly now?
> The only guess I have is the overlap case but
> it looks like the routines above already handle that.
>
>
> http://codereview.appspot.com/963044/show
>

[gri, 2010-05-01 04:25:56]

*** Submitted as http://code.google.com/p/go/source/detail?r=f3b8969c33da ***

big: use fast shift routines

- fixed a couple of bugs in the process
  (shift right was incorrect for negative numbers)
- added more tests and made some tests more robust
- changed pidigits back to using shifts to multiply
  by 2 instead of add

  This improves pidigit -s -n 10000 by approx. 5%:

  user 0m6.496s (old)
  user 0m6.156s (new)

R=rsc
CC=golang-dev
http://codereview.appspot.com/963044