Enhanced GCD that doesn't trap

[jasonbobier]

By returning T.Magnitude instead of T, the gcd call never traps. This also allows the end user of the call to decide how to handle the result.

PR: #310

(Also note that this is in preparation for lcm, which will be a separate PR.)

[stephentyrone]

Producing T is generally useful, and the trap cases closely mirror division, which is relatively explainable. However, not trapping is also pretty useful, so I'm open to discussion on this. @NevinBR may have opinions as well, since he did the original GCD.

[jasonbobier]

Note that I closed #310 only because I wanted to split it up into a couple of PRs. By not trapping, it allows a GCD that can be used with LCM that throws instead of trapping. I thought about having two versions, but because it is just one line of code (init(exactly:)), it didn't seem to make sense.

[stephentyrone]

Yep. It's an interesting case because the vast majority of the time, I think people will want to have the result as T, and always writing Int(gcd(a,b)) gets a little bit silly (on the other hand, trapping is also unfortunate).

It's directly analogous to abs( ), which returns the argument type (and therefore can trap), but we also provide .magnitude which returns the magnitude and never traps. We may want to do something similar here. @xwu probably has wrangled with this a bit as well.

[xwu]

Yeah, after noodling with alternatives, I concluded that those gcd use cases that need to deal with overflow can go through the trouble of converting the arguments and doing a tiny bit of post-processing.

I've always thought that this is superior to making everyone else convert the result. Trapping obviously isn't anyone's idea of a good time but I think for numeric operations such as this it's still the right default.

If this is a frequent enough operation, my preference then and now would be to encapsulate the logic into a distinct gcdReportingOverflow function.

[jasonbobier]

The original code that I wrote had both. It had gcd() that could trap that was analogous to abs() and meant to be a more 'pure' version of the mathematical function and greatestCommonDivisor() that used Magnitude for the return type. gcd() used greatestCommonDivisor() internally for consistency should that algorithm change. Looking ahead, this is exactly what the code does for least common multiple (which I'm separating into a separate PR). There is lcm() that can trap and is meant for variable width integers and a leastCommonMultiple() that instead throws an overflow error with the full width result (using a slower path). So, for consistency, it would also make sense to have both. (Note that lcm needs a gcd that doesn't trap.)

[jasonbobier]

After separating it out into a separate PR, I remembered several of my thoughts when I originally wrote the code a few months ago and why I settled on using T.Magnitude as the result.

• The current code is discarding a perfectly valid result and trapping, thus potentially causing an unnecessary program crash without defensive code written around it at each call site.
• The overflow issue is primarily with 2's complement signed fixed width integers. Unsigned, variable width, 1's complement, etc... don't overflow the gcd function and the result would already be T because T == T.Magnitude in those cases.
• Returning T.Magnitude removes a couple of lines of special case code that would be unnecessarily executed even if T == T.Magnitude.
• Preventing overflow by requiring type conversion of T parameters at each call site adds additional code that would often require additional unnecessary type conversion unless the api user knew the internals of the gcd function. For example a user wanting gcd<Int> that didn't trap on a 64 bit platform would probably convert the parameters to Int128s to avoid overflow. This would cause an additional unnecessary conversation because the parameters would then be converted to UInt128s to get their magnitudes. Whereas simply returning T.Magnitude on the initial T parameters would only convert them the one time to their proper final type (instead of once by the user and once by the function).
• Or instead the user could use the magnitude of the parameters, which would end up with a T.Magnitude result anyway.
• I don't think that gcdReportingOverlow is the proper naming because the xReportingOverlfow functions seem to be meant to represent an overflow bit check after an arithmetic operation. gcd is different in that we are specifically discarding a valid result and trapping.
• Finally, I thought about why I preferred gcd(T, T) -> T and realized that it was simply because that is what I was used to from C and C++, and that is how I thought about the mathematical signature. But Swift has a better way to describe this and in fact the result of gcd is actually a magnitude of the parameters.

Anyway, #320 contains the PR.