Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

math/big: GCD support for negative and zero arguments #28878

Open
TuomLarsen opened this issue Nov 20, 2018 · 20 comments

Comments

Projects
None yet
8 participants
@TuomLarsen
Copy link

commented Nov 20, 2018

Please consider adding support for zero and negative arguments to math/big GCD.

As of version 1.11.1, to calculate GCD of two integers one has to write:

new(big.Int).GCD(nil, nil, new(big.Int).Abs(a), new(big.Int).Abs(b))

In other words, one needs two extra allocations (or copies) as the nat field of big.Int is private.

If on the other hand negative inputs were allowed the code would read:

new(big.Int).GCD(nil, nil, a, b)

For negative inputs the resulting GCD could be treated as GCD(|a|, |b|), the precise sign does not really matter as long as it is documented. (For example, "GCD is non-negative".)

While I'm at it, it would be also nice to support zero arguments as it is well defined (GCD(a, 0) = |a|, GCD(0, 0) = 0) and it would simplify the code because there would be no need to special-case zero inputs. Currently it sets the result to zero.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Nov 20, 2018

@ianlancetaylor ianlancetaylor added this to the Go1.13 milestone Nov 20, 2018

@bmkessler

This comment has been minimized.

Copy link
Contributor

commented Nov 20, 2018

Note, you can avoid allocation by using:

new(big.Int).GCD(nil, nil, a.Abs(a), b.Abs(b))

Which switches the sign without allocation.

What would be the proposed convention for the signs of the Bezout coefficients?

z = a*x + b*y
or
z = |a|*x + |b|*y

I don't think there is an established convention here.

For zero values, I presume you would set x=0 if a=0 and y=0 if b=0

What is the use case for GCD of negative numbers?

@TuomLarsen

This comment has been minimized.

Copy link
Author

commented Nov 21, 2018

That would mutate the arguments, however. I don't think it is desirable to change a or b when asking for new(big.Int).

If it worked as GCD(|a|, |b|) then I think the latter would make more sense. And as you say for the case of zeros.

Normalizing fractions, computing content of polynomials, simplify integer matrices, all these work beyond natural numbers.

@bmkessler

This comment has been minimized.

Copy link
Contributor

commented Nov 21, 2018

Yes, it's not ideal that you would have to track the signs of a and b and restore them after calculating the GCD, I was just noting that you could currently calculate the GCD without allocating by doing some additional bookkeeping.

For reference, GMP uses the first convention for the Bezout coefficients z = a*x + b*y
https://gmplib.org/manual/Number-Theoretic-Functions.html

@TuomLarsen

This comment has been minimized.

Copy link
Author

commented Nov 21, 2018

This as well but also accessing a or b from other threads would be unsafe.

@Merovius

This comment has been minimized.

Copy link

commented Nov 29, 2018

Disclaimer: No, don't do this ;)

func evilAbs(x *big.Int) *big.Int {
	y := *x
	y.Abs(&y)
	return &y
}
@gopherbot

This comment has been minimized.

Copy link

commented Mar 4, 2019

Change https://golang.org/cl/164972 mentions this issue: math/big: allow all values for GCD

@bcmills

This comment has been minimized.

Copy link
Member

commented Mar 4, 2019

The documentation for (*big.Int).GCD currently says:

If either a or b is <= 0, GCD sets z = x = y = 0.

That's unfortunate: it gives well-defined non-error behavior for an input that arguably should have been defined to be a user error. It also makes any change to GCD for zero or negative inputs violate Go 1 compatibility, and per #28221, we want to avoid such redefinitions.

That seems to suggest that the extended GCD function must have a new name.

@bmkessler

This comment has been minimized.

Copy link
Contributor

commented Mar 4, 2019

That is unfortunate. I don't think there should be a different GCD function that accepts zero or negative inputs. So that probably makes this a Go 2 proposal then.

@bcmills

This comment has been minimized.

Copy link
Member

commented Mar 4, 2019

Even a Go 2 proposal will generally need to follow the guidelines from #28221 in order to be accepted.
I don't think there is a viable alternative to putting the behavior in a separate method.

@bmkessler

This comment has been minimized.

Copy link
Contributor

commented Mar 4, 2019

Doesn't math/big fall under standard-library-changes and not changes to the core language.

One of the benefits of a Go 2 transition is the chance to release some of the standard library packages from the Go 1 compatibility guarantee.

In particular, it would appear to be part of the penumbra-standard-library

The penumbra standard library consists of those packages that are included with a release but are maintained independently. This will be most of the current standard library. These packages will follow the same discipline as today, with the option to move to a v2 where appropriate.

Which seems to indicate this change would be possible in a future release.

@bcmills

This comment has been minimized.

Copy link
Member

commented Mar 4, 2019

Given semantic import versioning, adding a v2 of an entire package is strictly more duplication than adding a method to an existing type. An entire v2 package would be a very large hammer for a problem that could be addressed by adding a somewhat-redundant method with a somewhat-suboptimal name.

@TuomLarsen

This comment has been minimized.

Copy link
Author

commented Mar 7, 2019

IMHO, I don't think this warrants a new method. GCD(x, 0) = |x| (or at least x), everything else is wrong result. If there was a bug in stdlib and users started to rely on, would Go prefer to fix it or keep the broken behaviour? The only situation where this would break current code is when the user relied on inexact result. Go 1.12 introduced more precise Sin, Cos, ... which produce non-identical results from earlier releases. If I relied on the old transcendental function, this would break my code. As a side note, Python is in similar situation now. They have both fractions.gcd and math.gcd, and marked the former as deprecated.

@Merovius

This comment has been minimized.

Copy link

commented Mar 7, 2019

@TuomLarsen A bug is, generally speaking, a deviation of the behavior of a program from its intention. The fact that this behavior is explicitly documented, though, shows that this behavior is the intention - someone made the deliberate decision that the function should behave that way. As such, if you rely on it, you're also not relying on "inexact results" - it is clearly specified how the function behaves in this case and you're relying on that specification.

In any case, this is actually documented (even though we're talking stdlib and not language, the same principles apply). This would at best fall under "specification error" and be incompatible. And the compatibility guarantee clearly states that they only happen for security issues. Bugs, to answer your question, can be fixed, even if it breaks code that relies on it. And as to Sin, Cos, those changes would fall under "unspecified behavior" (it was never guaranteed that the results would stay bitwise identical). Grain of salt though, that again this is stdlib and not language :)

@bcmills AIUI the intention was to keep this around as a "if we ever release math.Big/v2 for whatever reason, we could add this change to the bunch", not to release a new version specifically to address this. AIUI the opinion is that this is not important enough to warrant the cost of a new function - but if we ever have to pay the transition cost of a major version anyway, we might as well throw this in for basically free.

(I have no opinion on my own whether this should have a new function. I think doing what's suggested would be the correct way for GCD to behave, but it is inconsequential to me if and how that would be achieved :) )

@griesemer

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

Per the discussion above, I have to agree that the new definition would indeed be problematic in the light of backward-compatibility. I am also not convinced that we should add a new function (GCD2) at this point. At any rate, it is easy for a client needing the extra functionality to just write that code.

Leaving this on hold for now.

@randall77

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

It is true that the docs for GCD say:

If either a or b is <= 0, GCD sets z = x = y = 0.

but even before that, they say:

a and b, which both must be > 0

Kind of self-contradictory, but we currently forbid < 0 args, even if we also specify a behavior for them.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented Mar 18, 2019

Fair point; I did miss that.

@bcmills Do you still have strong objections in light of this? Personally, I'd go forward with it.

@bcmills

This comment has been minimized.

Copy link
Member

commented Mar 28, 2019

I still think it's a breaking change, but if you want to call it a specification error instead I'm ok with trying it out and seeing what breaks.
(The “specification error” in this case would be the fact that we documented the behavior for prohibited inputs.)

@bmkessler

This comment has been minimized.

Copy link
Contributor

commented May 1, 2019

@griesemer @bcmills Is there a final decision on this? As far as any practical effects, I don't foresee that any code was calling GCD with negative arguments and doing something specific with an all zero result. Likely, any code calling GCD with negative arguments would have been checking the sign of arguments before the call since the all zero result would not be what they wanted.

@griesemer

This comment has been minimized.

Copy link
Contributor

commented May 1, 2019

Let's try this (and consider the current documentation at "specification error"). For Go 1.14.

@griesemer griesemer added NeedsFix and removed NeedsDecision labels May 1, 2019

@griesemer griesemer modified the milestones: Go1.13, Go1.14 May 1, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.