|
| minthreadsleft = 0
}}
{{Talk header}}
{{Talk header|archive_bot=lowercase sigmabot III|archive_age=1|archive_units=year}}
{{WikiProject Computing}}banner shell|class=Start|
{{WikiProject Computing|importance=Mid}}
{{WikiProject Computer science|importance=Mid}}
{{WikiProject Mathematics|importance=Mid}}
}}
== The Implementation section was wrong ==
== 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?
[[User:Mgs2804|Mgs2804]] ([[User talk:Mgs2804|talk]]) 18:41, 4 April 2021 (UTC)
<tt>gcd(i32::MAX, i32::MIN + 1)</tt> 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. <tt>gcd(i32::MIN, i32::MAX)</tt> 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.
: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. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|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 ^^' [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 09:46, 15 February 2023 (UTC) ▼
Because people will use algorithms found on Wikipedia, I have removed that algorithm. I will attempt to rewrite it correctly. — [[User:Chai T. Rex|Chai T. Rex]] ([[User talk:Chai T. Rex|talk]]) 11:54, 12 July 2023 (UTC)
== “WP is not a code repository!” / [[Special:Contributions/91.56.241.188|91.56.241.188]] ==
: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 [https://play.rust-lang.org/?edition=2021&gist=d571ddc17eddc9f504ef9f1732924d5c the linked program]. — [[User:Chai T. Rex|Chai T. Rex]] ([[User talk:Chai T. Rex|talk]]) 15:55, 12 July 2023 (UTC)
[[Special:Contributions/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.
:Yes, the implementation I originally wrote (then adapted for greater legibility) specifically took in ''u64'' (unsigned) integers. That was changed in [[Special:Diff/1154862632|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 [https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=056b42ed4b2292e1a4aadd79a8cecc78 playground]).
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 [[WP:BOLD|boldly]] rework the “Implementation” section.
: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. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 1312:0216, 54 OctoberFebruary 20212024 (UTC)
▲:: PS: Sorry itfor tookthe sohuuuge longdelay toin resolvereaction: I apparently missed all the watched-pages notifications due to thisthe UI ^^'changes. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 0912: 4619, 154 February 20232024 (UTC)
:Reverted [https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&diff=1054325962&oldid=1048336339&diffmode=source 1054325962] “Implementation in C” for the same reasons:
:- no didactic purpose: restated the same thing as the Rust example right above, was <s>probably a direct translation</s> 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. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|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 [https://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&diff=prev&oldid=1084500718&diffmode=source rev. 1084500718] "Script-assisted style fixes" so I am assuming it was an issue with [[User:Ohconfucius/script|that particular script]] rather than a violation of the [[Wikipedia:Manual_of_Style|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 [[Template:Cite_web| {{Cite web}}]] but that doesn't seem quite appropriate? [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 10:03, 15 February 2023 (UTC)
| 