Talk:Binary GCD algorithm
| This is the talk page for discussing improvements to the Binary GCD algorithm article. This is not a forum for general discussion of the subject of the article. |
Article policies
|
| Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL |
Archives: 1Auto-archiving period: 12 months  |
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||
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)
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.