Rfcs: Offer GCD function in Rust again

[clarfonthey]

Rust used to offer this pre-1.0, but once the numeric traits were ditched in favour of inherent methods, these were removed.

Considering how the implementation is nontrivial, but very commonly used, it makes sense to re-offer this in the standard library. I'm not sure if it would make the most sense as an inherent method (although it seems reasonable), but I don't think it's unreasonable to include it.

[SimonSapin]

very commonly used

Is it? Assuming you mean greatest common denominator I only remember using it once, since high school.

[clarfonthey]

@SimonSapin I've ended up using GCD-like computations a lot but a lot of the code I tend to use it in is more mathematical in nature. Factoring numbers, simplifying fractions, etc.

I shouldn't have said very, but I do think that it's common enough to include.

[porky11]

There probably already exists some math crate impleneting this. Else just implement it yourself, isn't difficult

[ExpHP]

greatest common denominator

(Oddly enough, I have a terrible habit of calling it this, too, and only notice the mistake when other people do it.)

[clarfonthey]

@porky11 it is offered by the num-integer crate currently. I was just a bit confused why it wasn't included in the standard library, as it seems useful enough in a general context to provide upstream.

Also, the implementation of the Euclidean algorithm is standard and easy to write, but the faster version (Stein's Algorithm) is not really immediately obvious. I doubt that most people wishing to simplify a ratio would know offhand how to compute the GCD.

[clarfonthey]

@ExpHP Yeah, it's greatest common divisor. Some people call it HCF (highest common factor) but most implementations call it GCD.

[Centril]

Triage: @clarcharr Are you still interested in this? If so, file an RFC perhaps / move to internals?

[Lonami]

GCD is not as basic as other operations like sin, cos etc. I personally think this feature should indeed belong to a third-party crate, with more math-related functions.

[SimonSapin]

I think it’s fine for this algorithm to live in an external crate. sin and cos are already provided by libc/libm, so we’re only providing bindings.

[Centril]

Doesn't seem like there's interest from the libs team to put this in libstd so ill close.