code review 145650043: math/big: math.Exp should return result >= 0

math/big: math.Exp should return result >= 0 for |m| > 0

The documentation states that Exp(x, y, m)
computes x**y mod |m| for m != nil && m > 0.
In math.big, Mod is the Euclidean modulus,
which is always >= 0.

Fixes issue 8822.

[gri, 2014-09-30 20:40:48]

Hello agl@chromium.org (cc: golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[agl1, 2014-09-30 20:47:14]

LGTM

https://codereview.appspot.com/145650043/diff/40001/src/math/big/int_test.go
File src/math/big/int_test.go (right):

https://codereview.appspot.com/145650043/diff/40001/src/math/big/int_test.go#...
src/math/big/int_test.go:808:
"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B7"
+
nit (feel free to ignore): these lines are long enough that I'd make them just a
single line per value. As it is, unless you have a >= 160 width display, they'll
be broken anyway and it looks even worse.

[gri, 2014-09-30 20:51:48]

https://codereview.appspot.com/145650043/diff/40001/src/math/big/int_test.go
File src/math/big/int_test.go (right):

https://codereview.appspot.com/145650043/diff/40001/src/math/big/int_test.go#...
src/math/big/int_test.go:808:
"-0x1BCE04427D8032319A89E5C4136456671AC620883F2C4139E57F91307C485AD2D6204F4F87A58262652DB5DBBAC72B0613E51B835E7153BEC6068F5C8D696B7"
+
On 2014/09/30 20:47:13, agl1 wrote:
> nit (feel free to ignore): these lines are long enough that I'd make them just
a
> single line per value. As it is, unless you have a >= 160 width display,
they'll
> be broken anyway and it looks even worse.

Done.

[r, 2014-09-30 21:05:32]

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go
File src/math/big/int.go (right):

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go#newco...
src/math/big/int.go:608: if len(z.abs) > 0 && x.neg && len(yWords) > 0 &&
yWords[0]&1 == 1 {
deserves a comment. this is magic.

[gri, 2014-09-30 21:18:03]

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go
File src/math/big/int.go (right):

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go#newco...
src/math/big/int.go:608: if len(z.abs) > 0 && x.neg && len(yWords) > 0 &&
yWords[0]&1 == 1 {
On 2014/09/30 21:05:32, r wrote:
> deserves a comment. this is magic.

hence the comment just below...

(this kind of code is pretty common in this package)

[r, 2014-09-30 21:52:13]

LGTM. ask rsc.

[rsc, 2014-10-02 19:04:14]

LGTM either way

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go
File src/math/big/int.go (right):

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go#newco...
src/math/big/int.go:608: if len(z.abs) > 0 && x.neg && len(yWords) > 0 &&
yWords[0]&1 == 1 {
On 2014/09/30 21:18:03, gri wrote:
> On 2014/09/30 21:05:32, r wrote:
> > deserves a comment. this is magic.
> 
> hence the comment just below...
> 
> (this kind of code is pretty common in this package)

i think you could plausibly keep the old phrasing and then frame this mod thing
as a fixup:

z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has
no sign

if z.neg && len(mWords) > 0 {
    // make modulus result positive
    z.abs = ...
    z.neg = false
}

[gri, 2014-10-02 20:02:35]

*** Submitted as https://code.google.com/p/go/source/detail?r=52bacae4f5b0 ***

math/big: math.Exp should return result >= 0 for |m| > 0

The documentation states that Exp(x, y, m)
computes x**y mod |m| for m != nil && m > 0.
In math.big, Mod is the Euclidean modulus,
which is always >= 0.

Fixes issue 8822.

LGTM=agl, r, rsc
R=agl, r, rsc
CC=golang-codereviews
https://codereview.appspot.com/145650043

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go
File src/math/big/int.go (right):

https://codereview.appspot.com/145650043/diff/60001/src/math/big/int.go#newco...
src/math/big/int.go:608: if len(z.abs) > 0 && x.neg && len(yWords) > 0 &&
yWords[0]&1 == 1 {
On 2014/10/02 19:04:14, rsc wrote:
> On 2014/09/30 21:18:03, gri wrote:
> > On 2014/09/30 21:05:32, r wrote:
> > > deserves a comment. this is magic.
> > 
> > hence the comment just below...
> > 
> > (this kind of code is pretty common in this package)
> 
> i think you could plausibly keep the old phrasing and then frame this mod
thing
> as a fixup:
> 
> z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0
has
> no sign
> 
> if z.neg && len(mWords) > 0 {
>     // make modulus result positive
>     z.abs = ...
>     z.neg = false
> }
> 

Done.