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)

“WP is not a code repository!” / 91.56.241.188

91.56.241.188 removed the iterative Rust version, with “WP is not a code repository!” as a stated reason... then reintroduced an x86 assembly version that used the same techniques, a week later. This is obviously incoherent behaviour, and conveyed much less clearly the point of the iterative implementation (showing where the concrete speedups are, beyond the algorithm-as-written); as such, I simply rolled back their changes.

However, I do agree that WP is not a code repository, and that code samples that do not fulfill a didactic purpose should not be kept; I had shied from removing the C example initially, even though it doesn't convey additional information compared to the algorithm's description, but I will go and boldly rework the “Implementation” section.

nicoo (talk) 13:02, 5 October 2021 (UTC)

Reverted 1054325962 “Implementation in C” for the same reasons:

- no didactic purpose: restated the same thing as the Rust example right above, was probably a direct translation copied verbatim from Lemire's blog ;

- lack of clarity: code wasn't commented, used “bit tricks” like ctz(u | v) = min(ctz(u), ctz(v)) for no particular reason.

Furthermore, I doubt it is possible to implement this algorithm in C in a way that is both standard-compliant, realistic (“nobody” would implement this without a ctz primitive), and readable. A code example that doesn't meet those criteria doesn't seem fit for encyclopedic purposes. nicoo (talk) 12:46, 12 November 2021 (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.

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)