Issue #15161 has been reported by jzakiya (Jabari Zakiya).

----------------------------------------
Feature #15161: making gcd faster for 3x3
https://bugs.ruby-lang.org/issues/15161

* Author: jzakiya (Jabari Zakiya)
* Status: Open
* 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: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>