digitalmars.D.bugs - [Issue 4125] New: std.numeric.gcd can use a binary GCD
- d-bugmail puremagic.com (20/20) Apr 24 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (10/10) Jan 09 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (33/33) Jan 31 2012 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (21/23) Jan 05 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (10/17) Jan 06 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (11/11) Jan 08 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4125
- d-bugmail puremagic.com (13/18) Jan 08 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4125
http://d.puremagic.com/issues/show_bug.cgi?id=4125 Summary: std.numeric.gcd can use a binary GCD Product: D Version: future Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: bearophile_hugs eml.cc std.numeric.gcd can use a faster Binary GCD algorithm, especially when the input type is unsigned. This page has both C code (and asm, but the C code is probably enough in many situations): http://en.wikipedia.org/wiki/Binary_GCD_algorithm -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Apr 24 2010
http://d.puremagic.com/issues/show_bug.cgi?id=4125 Andrei Alexandrescu <andrei metalanguage.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |ASSIGNED CC| |andrei metalanguage.com AssignedTo|nobody puremagic.com |andrei metalanguage.com -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 09 2011
http://d.puremagic.com/issues/show_bug.cgi?id=4125 Marco Leise <Marco.Leise gmx.de> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |Marco.Leise gmx.de Replace uint with ulong for the longer version ;) I use this and it is notably faster than what I used before. uint gcd(uint u, uint v) { int shift; if (u == 0 || v == 0) return u | v; for (shift = 0; ((u | v) & 1) == 0; ++shift) { u >>= 1; v >>= 1; } while ((u & 1) == 0) u >>= 1; do { while ((v & 1) == 0) v >>= 1; if (u < v) { v -= u; } else { uint diff = u - v; u = v; v = diff; } v >>= 1; } while (v != 0); return u << shift; } -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 31 2012
http://d.puremagic.com/issues/show_bug.cgi?id=4125 Peter Alexander <peter.alexander.au gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |peter.alexander.au gmail.co | |m 11:15:04 PST ---Replace uint with ulong for the longer version ;) I use this and it is notably faster than what I used before.I implemented this (exactly as you have it) and it was slower than the algorithm that is already there. I tested on all pairs of integers below 10,000, and also on the pairs (x^2, y) for all x,y < 10,000. At best it was 50% slower, at worst 3x slower. All tests used dmd -O -release -inline I suspect the reason for the performance reduction is due to poor pipelining. The binary version involves a lot more branching, and more loop iterations than the standard algorithm. Also, the branches taken are highly unpredictable. Maybe I'll look at this again in the future to try and make it faster, but it's pretty low on my priority list. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 05 2013
http://d.puremagic.com/issues/show_bug.cgi?id=4125I implemented this (exactly as you have it) and it was slower than the algorithm that is already there. I tested on all pairs of integers below 10,000, and also on the pairs (x^2, y) for all x,y < 10,000. At best it was 50% slower, at worst 3x slower. ... Maybe I'll look at this again in the future to try and make it faster, but it's pretty low on my priority list.Thank you for doing some experiments. Once the experiments are conclusive, this enhancement can be closed. (Then at the moment a more important function for Phobos is an efficient GCD for bigints.) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 06 2013
http://d.puremagic.com/issues/show_bug.cgi?id=4125 FWIW, you can get rid of most of the conditional branches by using: min(u,v) = v + ( (cast(int)(u-v)) >> (8*int.sizeof - 1)) & (u-v) the shift smears the sign bit of u-v so that it makes a mask either 0x0000_0000 or 0xFFFF_FFFF. I think the general consensus is that (at least if you use asm), binary GCD is faster on all known processors, but not necessarily by a large amount. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 08 2013
http://d.puremagic.com/issues/show_bug.cgi?id=4125 Artem Tarasov <lomereiter gmail.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |lomereiter gmail.com PST ---std.numeric.gcd can use a faster Binary GCD algorithm, especially when the input type is unsigned. This page has both C code (and asm, but the C code is probably enough in many situations): http://en.wikipedia.org/wiki/Binary_GCD_algorithmMaybe instead of reinventing the wheel LibTomMath library should be used? It is in public domain, has decent performance, and is stable enough to provide implementation of big integers in TCL and Rubinius. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Jan 08 2013