benchmark.zig

const std = @import("std");

const assert = std.debug.assert;

fn hybrid(p: anytype, q: anytype) @TypeOf(p, q) {
    assert(p >= 1);
    assert(q >= 1);

    const T = @TypeOf(p, q);
    var u: T = undefined;
    var v: T = undefined;
    if (p < q) {
        u = q;
        v = p;
    } else {
        u = p;
        v = q;
    }
    assert(v <= u);
    u %= v;
    if (u == 0) return v;

    const zu = @ctz(u);
    const zv = @ctz(v);
    const shift = @min(zu, zv);
    u >>= @intCast(zu);
    v >>= @intCast(zv);

    while (true) {
        const diff = u -% v;
        if (u > v) {
            u = v;
            v = diff;
        } else {
            v -= u;
        }
        if (diff != 0) v >>= @intCast(@ctz(diff));
        if (v == 0) break;
    }

    const result = u << @intCast(shift);
    assert(result > 0);
    return result;
}

fn euclid(p: anytype, q: anytype) @TypeOf(p, q) {
    assert(p >= 1);
    assert(q >= 1);

    const T = @TypeOf(p, q);

    var a = p;
    var b = q;
    var c: T = undefined;

    while (b != 0) {
        c = b;
        b = @mod(a, b);
        a = c;
    }

    assert(a > 0);
    return a;
}

pub fn main() !void {
    var prng = std.Random.DefaultPrng.init(0x12345678);
    var random = prng.random();

    var etime: usize = 0;
    var htime: usize = 0;

    var timer = try std.time.Timer.start();

    inline for (.{ u32, u64, u128 }) |T| {
        for (0..10_000_000) |_| {
            const a = random.int(T);
            const b = random.int(T);
            if (a == 0 or b == 0) continue;

            var t = timer.read();
            const e = euclid(a, b);
            etime += timer.read() - t;

            t = timer.read();
            const h = hybrid(a, b);
            htime += timer.read() - t;

            assert(e == h);
        }
        std.debug.print("{}: {} vs. {} = {d:.2}x\n", .{ T, etime, htime, @as(f64, @floatFromInt(etime)) / @as(f64, @floatFromInt(htime)) });
    }
}

gcd.cc

// g++ -std=c++20 gcd.cc
#include <cstdint>
#include <bit>
#include <utility>
#include <algorithm> 
#include <iostream>

typedef uint64_t int_type ;
int_type hybrid_binary_gcd_noswap(int_type __a, int_type __b) {
   if (__a < __b) {
    int_type __tmp = __b;
    __b       = __a;
    __a       = __tmp;
  }
  if (__b == 0)
    return __a;
  __a %= __b; // Make both argument of the same size, and early result in the easy case.
  if (__a == 0)
    return __b;

  int __az    = std::countr_zero(__a);
  int __bz    = std::countr_zero(__b);
  int __shift = std::min(__az, __bz);
  __a >>= __az;
  __b >>= __bz;
  do {
    int_type __diff = __a - __b;
    std::cerr << __a << " " << __b << " " << __diff << std::endl;
    if (__a > __b) {
      __a = __b;
      __b = __diff;
    } else {
      __b = __b - __a;
    }
    if (__diff != 0)
      __b >>= std::countr_zero(__diff);
  } while (__b != 0);
  return __a << __shift;
}


int main() {
  std::cout << hybrid_binary_gcd_noswap(2244737270, 1344042732) << std::endl;
  return 0;
}