From: mame@... Date: 2018-09-25T22:33:02+00:00 Subject: [ruby-core:89169] [Ruby trunk Feature#15161][Closed] making gcd faster for 3x3 Issue #15161 has been updated by mame (Yusuke Endoh). Status changed from Open to Closed It already uses the variant of the binary (Stein's) algorithm. https://github.com/ruby/ruby/blob/3abbaab1a7a97d18f481164c7dc48749b86d7f39/rational.c#L285-L307 See #13503. ---------------------------------------- Feature #15161: making gcd faster for 3x3 https://bugs.ruby-lang.org/issues/15161#change-74195 * Author: jzakiya (Jabari Zakiya) * Status: Closed * Priority: Normal * Assignee: * Target version: ---------------------------------------- With the goal of making Ruby as fast as possible for 3x3 I would like to propose a faster implementation of the ``gcd`` function. I use ``gcd`` a lot in my ``primes-utils`` gem, and in cryptography and Number Theory problems. The current implementation https://ruby-doc.org/core-2.5.1/Integer.html#method-i-gcd uses a recursive implementation. I propose using the binary (Stein's) algorithm, which I believe has been proposed/discussed before. https://en.wikipedia.org/wiki/Binary_GCD_algorithm However, I recently raised an issues with Crystal's implementation (also recursive) and suggested using Stein's algorithm, which they approved. https://github.com/crystal-lang/crystal/issues/6683 However, the default (iterative) wikipedia implementation is nowhere near as fast as possible. https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/ The author provides benchmarks of different implmentations (including recursive) https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/12/26/gcd.cpp and the version below is the fastest, and also the simplest. ``` unsigned int gcdwikipedia2fastswap(unsigned int u, unsigned int v) { int shift; if (u == 0) return v; if (v == 0) return u; shift = __builtin_ctz(u | v); u >>= __builtin_ctz(u); do { v >>= __builtin_ctz(v); if(u>v) std::swap(u,v); v = v - u; } while (v != 0); return u << shift; } ``` Thank you for considering this. -- https://bugs.ruby-lang.org/ Unsubscribe: