Feature #15161


making gcd faster for 3x3

Added by jzakiya (Jabari Zakiya) about 4 years ago. Updated about 4 years ago.

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

uses a recursive implementation.

I propose using the binary (Stein's) algorithm, which I believe has been proposed/discussed before.

However, I recently raised an issues with Crystal's implementation (also recursive)
and suggested using Stein's algorithm, which they approved.

However, the default (iterative) wikipedia implementation is nowhere near as fast as possible.

The author provides benchmarks of different implmentations (including recursive)

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.

Related issues 1 (0 open1 closed)

Is duplicate of Ruby master - Bug #13503: Improve performance of some Time & Rational methodsClosedActions

Updated by shevegen (Robert A. Heiler) about 4 years ago

I think a benchmark may be useful to the issue here.

I don't think the ruby team minds any speed improvement but what
is usually done is to verify any potential gain through benchmarks
(e. g. optcarrot for, I think, ruby 3x3 goals).

Updated by mame (Yusuke Endoh) about 4 years ago

  • Status changed from Open to Closed

It already uses the variant of the binary (Stein's) algorithm.

See #13503.

Actions #3

Updated by mame (Yusuke Endoh) about 4 years ago

  • Is duplicate of Bug #13503: Improve performance of some Time & Rational methods added

Also available in: Atom PDF