Why no gcd in standard lib?

Just about every language I've used has a builtin gcd (greatest common divisor) function.
It's used for so many different algorithms and purposes.
Why isn't this in the Rust standard library?

1 Like

Not sure exactly but I found this issue while looking for gcd.

I don't actually know of any languages that have it besides that __gcd thing in C / C++. I don't know why Rust doesn't have it, but it's luckily rather simple to implement.

2 Likes

Nim, Ruby, Go, D, Julia, etc, all have it.

I would recommend using the Binary GCD (Stein's algorithm) vs (old) Euclid algorithm.

See some discussions below.

https://bugs.ruby-lang.org/issues/15161

No matter how its implemented it's required for many numerically heavy fields (number theory, cryptography, statistics, algorithms, etc).

4 Likes

From Help for my parallel sum:

So the Rust-ian answer is to publish a crate with the desired functionality, under an appropriately permissive license.

13 Likes

Excuse me for my use of not rigorous Rust language, if I misused standard library.

There should be some approved crate|module|whatever with this function in it so users can import it into their programs and not have to implement|test it on their own.

In fact, Ruby is stripping out certain functionality and putting them into their own gems which will be included into a standard build of the language. This provides the capability to add|improve implementation of the standard language, as it develops to its next major release Ruby 3.0, now scheduled for release Dec 25, 2020 (not at 2.7).

This is such a commonly function it doesn't seem right users have to figure out how to implement it (correctly) on their own (even if Euclid's method is pretty simple).

There's a crate called gcd.

5 Likes

Since nobody else linked it yet, please see https://crates.io/crates/gcd. To use the crate, simply add

[dependencies]
gcd = "1.2.0"

to your Cargo.toml file.

With the dependency in place, you can use the crate like this:

use gcd::Gcd;

let x: u32 = 2024;
let y: u32 = 748;
println!("gcd({}, {}) = {}", x, y, x.gcd(y));
3 Likes

Thanks for the info. I've included it into my program.

To reiterate (rant) again though, gcd is so ubiquitous, and frequently used, and part of every
other language I have regularly used, I still think, for the benefit of programmers, it should be part of the std lib.

I use languages to get stuff done in. I could care less about the ideological purity of the basis for the language. Languages (both computer and human) evolve to meet the current needs and use pattern of the humans that use them, which mean they invariably will grow in vocabulary and size.

I see there are allot more functions in std lib that will probably never be used more frequently than gcd, but yet they are there. Putting gcd in the std lib will be one more little thing to make Rust easier for programmers to use (fewer hoops to jump through) and more friendly, as Rust is hard enough to learn already.

As a mostly Ruby programmer, don't let ideological purity trump programmer happiness.

2 Likes

To reiterate from my post upthread:

What functionality in gcd requires special support in the compiler?


____________________________

Continuing from my upstream post:

Your second post upthread states

If someone had implemented Euclid's algorithm in early std, and there were observable timing differences from Stein's algorithm that would break existing code, then it might not have been possible to replace the Euclid version with the Stein version. In other words, if it's in std it may not be permissible to improve it even when better algorithms are published.

6 Likes

That's quite an edge case, would we even consider that code to be logically correct if variance in timing created a race condition? I could probably break that same program by pausing some of the threads for the right amount of time; that could even happen automatically and randomly by a thread scheduler.

What about collections, smart pointer types, futures, iterators, Option/Result? None of these depend on compiler intrinsics, so they all could be maintained in external crates; many of them may have alternate implementations with varying tradeoffs, which could be another reason. By your logic they then all should be.

Simple rules are efficient, but problems are never that straightforward. The reason that these things are in std is because they're so widely used that we decided, subjectively, that it's worth including standard implementations of these things. Some of them, especially futures, may only be used by crates in particular fields, but that didn't preclude those things from being added. It's certainly worth considering adding gcd even if it is niche in some ways.

2 Likes

Generally I do agree that there is value to having some very fundamental operations in the std even if they don't interact closely to the compiler. That said some of these examples are not examples of this, e.g.:

  1. Smart pointer types: Smart pointers including Box and Rc are special lang items which allow you to use them as the type of a self-parameter, e.g. fn foo(self: Rc<Self>)
  2. Futures: Futures were moved into std exactly because this is required to make the async/await language feature work.
  3. Iterators: The implementation of for loops depends on the IntoIterator trait. Additionally iterators internally makes use of unstable features for performance reasons (see TrustedLen)
  4. Option/Result: Both are special in order to work with the ? operator.

Collections are a rather good example though ­— in fact our hash map is an external crate that is reexported in std.

8 Likes

Which shows the way to achieve the OP's goal: write an external crate for gcd, then make the case via an RFC that it should be reexported in std.

1 Like

A lot of numerics were moved out of the standard library during the stabilization of Rust 1.0, see the num crate. It provides an implementation of gcd employing Stein's algorithm.

8 Likes

Thanks for the info.

Because everyone here is very intelligent I'm not going to keep repeating a very simple point, so this is likely the last I'll say on this topic.

You can decide to do whatever you want, for whatever reasons, with Rust. That's true for any other project too. And when ideological purity is the most important thing, no other factor can exceed that.

My simple point is this, you can make Rust easier to use for programmers, as the highest goal, or you can force programmers to adhere to your ideological paradigm as a higher goal.

Ruby's highest goal is programmer happiness. It's easier to learn and easier to use, and was designed from jump street for that purpose. That's why it is so loved by its users (like me). For some large percentage (90% ?) of tasks it's perfectly fast enough, since you can't beat it for developer design speed.

I totally understand Mozilla started Rust to solve (make better) very specific issues with memory use in Firefox. OK, fine. But that doesn't necessarily have to conflict with doing things with the language to make it easier to use for the average person (someone who isn't coming from C/C++ and/or isn't trying to do systems programming).

The least you can do is make the docs identify where things are when people put in keyword searches, so they will know to consider crate x to get functionality y.

All I am asking is to have a higher appreciation for user happiness as a determiner of the language development.

That's it.

1 Like

I'm happiest when an update doesn't break my existing code, so I appreciate the care that goes into choosing what is put in the standard library. (As an aside, I don't think I've ever used gcd except for a class exercise.)

11 Likes

I have no idea about or opinion of "ideological purity" but I take a practical view of things. Or at least try to. To that end I have a few random thoughts about your question:

  1. After decades of programming I have never needed a GCD algorithm. As such I see no reason why any standard library needs to include one.

  2. Euclid shows us that GCD is a very simple thing. If I never needed one I would just make one in a few lines of code. I have no idea about Stein's algorithm or whatever.

  3. The C standard library has always included a ton of stuff which is now seen as a bad idea and whose use is discouraged. Like strcpy() and friends and a bunch of thread unsafe stuff. But still any standards compliant C implementation has to carry that baggage around.

  4. Given the amazing ease with which anything can be used via Cargo and all the crates people have created there is a lot less pressure to put things in the standard library than back in the day of C/C++. The line between "standard" and otherwise is blurred.

  5. Given all the above it seems to me to be a good move to keep the Rust standard library as lean and mean as possible.

14 Likes

You appear to have a somewhat biased viewpoint on the importance and ubiquity of gcd outside fairly specific use cases related to math or algorithmics. In fact, I’d bet that if we asked the greater Rust community what single function they’d most like to see added to the std, gcd would be far from the top.

7 Likes

The state of the "what goes in std?" debate hasn't really changed since I wrote https://internals.rust-lang.org/t/expansion-of-standard-library/10475/7?u=ixrec on IRLO, so I'll just quote myself here:

The key point is that Rust comes out-of-the-box with a toolchain that makes adding a 3rd party crate to your project a completely hassle-free non-issue. That creates a complete paradigm shift for how we think about a "standard library".

In many other language ecosystems, especially C++ (and I think Go to a lesser extent, until recently?), the reality is that the standard library is the only library for many if not most users, thus the bar for inclusion in the standard library is fundamentally not that far from "is this useful to people?" Any problem that's "been solved already" becomes something we want to "standardize" just for the sake of allowing the rest of the C++ community to use it, because in practice 3rd party libraries are simply not worth the hassle.

In Rust, none of that applies. When all 3rd party code is just as easy to depend on as the standard library, there's no longer any special availability advantage to being in the standard library. The idea that any "already solved problem" needs to be "standardized" simply evaporates into a non-problem, because once it's on crates.io, then "everyone has it" in practice already. Moving it into std does not increase the availability any further.


So the "what should go in std?" question is completely different in Rust. Typical compelling arguments for putting things in the Rust standard library include "vocabulary types" (e.g. the whole Rust ecosystem needs to agree on a single str type just so everyone's code can talk to each other), code that needs to interact with the compiler in some magical way, or tricky unsafe operations (because we trust std verification more than 3rd party crate verification, though even that could potentially change in the future), or platform abstractions that help keep a lot of Rust code portable-by-default (though that strategy didn't scale as well as we hoped, so that might change too). All of these are pretty fuzzy and case-by-case criteria, not remotely official in any way. In fact, in the specific case of an HTTP server, there is an obvious vocabulary types problem, but the ecosystem ended up agreeing on a 3rd party crate for that and AFAIK no one's ever asked for it to be moved into std.

gcd doesn't involve unsafe, doesn't interact with compiler internals, isn't a vocabulary type, and doesn't have any portability issues, so its absence from std seems perfectly typical. The fact that there's multiple non-obvious implementations with different tradeoffs seems to confirm the usual benefits to not standardizing things that don't need to be standardized.

If there was some compelling evidence that "programmer happiness" would be increased by putting gcd in std (or any other concrete argument at all), we could discuss that, but AFAICT none has been presented.

(quick aside: "ideological purity" is a pretty loaded and heated term. Without articulating a specific ideology, and why the alternative position is both not an ideology and better than whatever an ideology is, the phrase doesn't really mean anything. It should probably be avoided in serious technical discussion)

15 Likes

Another argument: what types should gcd work over? Just f64? What about f32 or a future f128? What about usize, u128, u64, and so on?

num used to be a part of std (including gcd, iiuc!), but was removed because of the difficulty of specifying the "perfect" stable-forever numerical abstraction traits.

Personally, if num becomes canonical enough to migrate back to std, I'd be behind seeing gcd in std (or at least, the standard distribution (crates available without crates-io, even if not called std)). My personal guideline for the standard distribution is both vocabulary types and primitives that you might implement before reaching for a library.

2 Likes