[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

--- Comment #10 from github-bugzi...@puremagic.com ---
Commits pushed to newCTFE at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/6b4c2585fe5d25488a2df6a7b9b7c49031c63253
Fix Issue 4125 - std.numeric.gcd can use a binary GCD

https://github.com/dlang/phobos/commit/19445fc71e8aabdbd42f0ad8a571a57601a5ff39
Merge pull request #4940 from Darredevil/issue-4125

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

--- Comment #9 from github-bugzi...@puremagic.com ---
Commits pushed to stable at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/6b4c2585fe5d25488a2df6a7b9b7c49031c63253
Fix Issue 4125 - std.numeric.gcd can use a binary GCD

https://github.com/dlang/phobos/commit/19445fc71e8aabdbd42f0ad8a571a57601a5ff39
Merge pull request #4940 from Darredevil/issue-4125

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

github-bugzi...@puremagic.com changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

--- Comment #8 from github-bugzi...@puremagic.com ---
Commits pushed to master at https://github.com/dlang/phobos

https://github.com/dlang/phobos/commit/6b4c2585fe5d25488a2df6a7b9b7c49031c63253
Fix Issue 4125 - std.numeric.gcd can use a binary GCD

https://github.com/dlang/phobos/commit/19445fc71e8aabdbd42f0ad8a571a57601a5ff39
Merge pull request #4940 from Darredevil/issue-4125

Fix Issue 4125 - std.numeric.gcd can use a binary GCD

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

Alexandru Razvan Caciulescu  changed:

   What|Removed |Added

 CC||alexandru.razva...@gmail.co
   ||m

--- Comment #7 from Alexandru Razvan Caciulescu  
---
After conducting some benchmarks we arrived to the conclusion that currently
the dmd compiler works best with Euclid's algorithm for GCD, otherwise we use
Stein's algorithm for ldc or gdc.

I tested both the previously shared benchmarks on the forum and a couple of my
own  and noted that gcd_binary2 implemented by bearophile_h...@eml.cc has the
best results, so I used that.

PR: https://github.com/dlang/phobos/pull/4940

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

Andrei Alexandrescu  changed:

   What|Removed |Added

   Keywords||bootcamp
   Assignee|and...@erdani.com   |nob...@puremagic.com

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=4125

Andrei Alexandrescu and...@erdani.com changed:

   What|Removed |Added

Version|future  |D2

--

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

https://d.puremagic.com/issues/show_bug.cgi?id=4125



--- Comment #6 from bearophile_h...@eml.cc 2014-01-07 18:04:17 PST ---
Created an attachment (id=1313)
Faster GCD

Code for a binary GCD that on LDC2 is about twice faster on uint values, and
it's rather faster with dmd too.

Timings (gcd is the Phobos one):

DMD 2.061alpha (32 bit):
  gcd, time = 1924
gcd_recursive, time = 1937
gcd_iterative_sub, time = 2931
gcd_iterative_mod, time = 1948
   gcd_binary, time = 3357
   gcd_binary_mod, time = 2136
 gcd_binary_2, time = 1406
 gcd_binary_2, time = 1391
Results sum: 1284258816


LDC2 (32 bit):
  gcd, time = 1930
gcd_recursive, time = 1924
gcd_iterative_sub, time = 3148
gcd_iterative_mod, time = 1926
   gcd_binary, time = 2635
   gcd_binary_mod, time = 2036
 gcd_binary_2, time = 1461
 gcd_binary_3, time = 1026
Results sum: 1284258816

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4125



--- Comment #4 from Don clugd...@yahoo.com.au 2013-01-08 02:37:41 PST ---
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 0x_
or 0x_.

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: ---

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4125


Artem Tarasov lomerei...@gmail.com changed:

   What|Removed |Added

 CC||lomerei...@gmail.com


--- Comment #5 from Artem Tarasov lomerei...@gmail.com 2013-01-08 06:42:51 
PST ---
(In reply to comment #0)
 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

Maybe 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: ---

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4125



--- Comment #3 from bearophile_h...@eml.cc 2013-01-06 03:44:33 PST ---
(In reply to comment #2)

 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.
 ...
 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: ---

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4125


Peter Alexander peter.alexander...@gmail.com changed:

   What|Removed |Added

 CC||peter.alexander...@gmail.co
   ||m


--- Comment #2 from Peter Alexander peter.alexander...@gmail.com 2013-01-05 
11:15:04 PST ---
(In reply to comment #1)
 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: ---

[Issue 4125] std.numeric.gcd can use a binary GCD

[d-bugmail]

http://d.puremagic.com/issues/show_bug.cgi?id=4125


Andrei Alexandrescu and...@metalanguage.com changed:

   What|Removed |Added

 Status|NEW |ASSIGNED
 CC||and...@metalanguage.com
 AssignedTo|nob...@puremagic.com|and...@metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---