The Speed of GCD

7 Responses to The Speed of GCD

  1. Nice post.

    What happens if you use GCC’s __builtin_ctz (or call an instruction like bsr) instead of doing expensive bit-check-and-shift loops?

    • First I doubt that __builtin_ctz works miracles (but I haven’t tried, so can’t confirm).

      I guess is just that it’s mostly a pointless optimization because the probability of having a number with 2^n as a factor is proportional to 2^{-n}, so the “optimization” gives maximal payoff with asymptotically zero probability.

      (and sorry for the very late approve+reply… I’ve been rather busy lately.)

  2. Non-recursive version in Euler Math Toolbox. Note, that there is a built-in command.

  3. […] A while ago, we looked at the computation of the GCD and found that the simplest implementation was, by far, the fastest. This week, we’ll have a look at another numerical problem: fast exponentiation (modulo machine-size integers). […]

  4. […] have honestly never written a program where computing the gcd was the bottleneck. However, Pigeon wrote a blog post where the binary GCD fared very poorly compared to a simple implementation of Euler’s […]

  5. […] the discussion of The Speed of GCD, Daniel Lemire remarked that one could use the compiler-specific intrinsic function __builtin_ctz […]

  6. P_P says:

    Fastest for me (C#):

    static uint gcd(uint a, uint b)
    while (a != 0)
    b %= a;
    if (b == 0) return a;
    a %= b;
    return b;

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 90 other followers

%d bloggers like this: