Talk:Binary GCD algorithm

Arbitrary unique factorization domains

As far as I can see, the cited paper only provides an algorithm for integer rings of number fields, not for arbitrary UFDs. Or am I missing something? Mgs2804 (talk) 18:41, 4 April 2021 (UTC)

Good catch. <3

I seem to recall spending a while looking for the relevant literature, when I overhauled the page, so I suspect I made a mistake and cited the wrong paper. I will annotate as “ref. needed” for now, as I do not currently have the energy to properly fix it, so feel free to fix it. nicoo (talk) 10:00, 17 February 2022 (UTC)

I couldn't easily find the relevant citation, and don't really have a lot of energy to invest in that specific detail, so I am simply removing the mention of UFDs under the assumption this was a mistake.

Sorry it took so long to resolve this ^^' nicoo (talk) 09:46, 15 February 2023 (UTC)

Citing uutils

The Rust implementation in the article is derived from the one I wrote in the uutils project, which is mentioned upfront.

User:Ohconfucius removed the link to the original in rev. 1084500718 "Script-assisted style fixes" so I am assuming it was an issue with that particular script rather than a violation of the MoS.

Still, I am not keen on the inline link, so I'd welcome another way to cite source code from open projects? I know of {{Cite web}} but that doesn't seem quite appropriate? nicoo (talk) 10:03, 15 February 2023 (UTC)

• Inline links are indeed systematically removed by one of my scripts, as this is the standard format for spamlinks. I would suggest you created a citation or a footnote if they are legitimate informational or citation links you want to keep. -- Ohc ^{revolution of our times} 22:24, 16 February 2023 (UTC)

The Implementation section was wrong

gcd(i32::MAX, i32::MIN + 1) gave the result 1. Since the two inputs are negatives of each other and both are far away from one, the result should be one or the other. gcd(i32::MIN, i32::MAX) even crashes the program because of integer overflow. You cannot use unsigned integer algorithms on signed integers without knowing what's going on. The code didn't even compile without syntax warnings.

Because people will use algorithms found on Wikipedia, I have removed that algorithm. I will attempt to rewrite it correctly. — Chai T. Rex (talk) 11:54, 12 July 2023 (UTC)

I have rewritten the algorithm to be correct and hidden the explanatory comment on how it avoids some branches, as it no longer applies. Improvements to the algorithm can be tested with the linked program. — Chai T. Rex (talk) 15:55, 12 July 2023 (UTC)

Yes, the implementation I originally wrote (then adapted for greater legibility) specifically took in u64 (unsigned) integers. That was changed in rev. 1154862632, which introduced less-legible and incorrect code as you found out.

The revision's summary was “the previous code doesn't work, return 0 all the time” which is incorrect (see tests in playground).

Given that, I'm going to revert the changes to the implementation section: correctly handling signed integers introduces complexity which IMO takes away from the didactic & illustrative purpose of an example implementation.

I'll add a note explaining this, and how to express signed-integers GCD in terms of unsigned GCD. nicoo (talk) 12:16, 4 February 2024 (UTC)

PS: Sorry for the huuuge delay in reaction: I apparently missed all the watched-pages notifications due to the UI changes. nicoo (talk) 12:19, 4 February 2024 (UTC)