Timeline for What is most efficient for GCD?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2023 at 8:24 | comment | added | DirkT | Even though this post does not directly answer the question, it brings up some valid points. Firstly it presents a third, valid GCD variant, which was not considered by the author of the question. While it is true that integer division has become much faster on modern CPUs, subtraction still is magnitudes faster in my experience. The author also carefully qualified his answer with "perhaps" and "for small numbers". I disagree with the criticism against this answer. | |
| Oct 15, 2016 at 14:41 | comment | added | Yuval Filmus | This will be extremely slow. Given $n,1$ as input, it runs for exponentially many steps (in the input length, $\log n$). | |
| Jun 2, 2015 at 20:46 | comment | added | Gilles 'SO- stop being evil' | I think the idea that modulo is slower than subtraction can be considered folklore. It holds both for small integers (subtraction usually takes one cycle, modulo rarely does) and for large integers (subtraction is linear, I'm not sure what the best complexity is for modulo but it's definitely worse than that). Of course you also need to consider the number of necessary iterations. | |
| Jun 2, 2015 at 19:26 | comment | added | Juho | I'm downvoting as your answer only contains code. We like to focus on ideas on this site. For instance, why is % an expensive operation? Speculation on a piece of code is not really a good answer for this site, in my opinion. | |
| Jun 2, 2015 at 18:14 | review | Low quality posts | |||
| Jun 2, 2015 at 20:47 | |||||
| Aug 31, 2014 at 21:19 | comment | added | Florian F | Normally, GCD[a,0] should also return a. Yours loops forever. | |
| Aug 31, 2014 at 20:58 | comment | added | Per Alexandersson | Ah, yes, I made a mistake. Fixed (I think), and clarified. | |
| Aug 31, 2014 at 20:55 | history | edited | Per Alexandersson | CC BY-SA 3.0 |
fixed.
|
| Aug 31, 2014 at 20:55 | comment | added | Florian F | It doesn't look right. For b==1, it should return 1. And GCD[2,1000000000] will be slow. | |
| Aug 31, 2014 at 20:21 | history | answered | Per Alexandersson | CC BY-SA 3.0 |