GCC Built-ins

January 7, 2014

In the discussion of The Speed of GCD, Daniel Lemire remarked that one could use the compiler-specific intrinsic function __builtin_ctz to get a good speed-up on binary GCD. That remark made me look into all the others intrinsics and built-ins offered by GCC.


Let’s have a look to at least a few of them!

Read the rest of this entry »

The Speed of GCD

December 10, 2013

The subject of computing the GCD was brought up a couple of times lately, and we assumed that the straightforward divide-and-remained implementation was the most efficient. But is it?


Before writing this post, I knew of basically two versions, one due to Euclid, invented sometimes in Antiquity of course, and one that used the remainder (that is, modulo) to do basically the same thing (which can be implemented either recursively or iteratively). Turns out that there are other algorithms, for example the so-called binary GCD that tries to somewhat speed up the process by removing multiples of two. But which one is the most efficient?

Read the rest of this entry »

Euclid, Primes numbers, and a Bit of Algorithm Analysis (Part IV)

September 24, 2013

While we looked at using the GCD for devising a Las Vegas-type algorithm to test for the primality of a number in a previous entry, we saw that actually testing the number against a list of primes (therefore assuming we have an arbitrarily long list of primes), one prime at a time, is much faster.


The GCD method, for divisor d, tests a number in O(1+\frac{1}{2}\log_2 d) steps, but we haven’t determined the complexity of the other method. Let’s do that now.

Read the rest of this entry »

Euclid and Primality Testing (III)

July 2, 2013

So in previous installments, we looked at how to use the euclidean algorithm to devise a Las Vegas-type algorithm for primality testing. We also found that, in general, simply testing factors one after the other is much more efficient (but that doesn’t mean that there are not better algorithms to test for primality!).


We also considered only relatively small primorials (the products of the first n prime numbers) since they rapidly exceeded 2^{32}. But just how fast do primorials grow?

Read the rest of this entry »

Euclid, Primes numbers, and a Bit of Algorithm Analysis

June 25, 2013

Last time we had a look at using the greatest common divisor and Euclid’s algorithm to devise a Las Vegas algorithm for primality testing. We also had a look at how the inclusion exclusion principle helps us determine the proportion of the numbers correctly tested.


However, we finished by asking ourselves if the method is actually efficient compared to, say, simply testing small divisors, one by one. Let us now find out.

Read the rest of this entry »

Euclid, Prime numbers, and the Inclusion-Exclusion Principle

May 28, 2013

The Euclidean algorithm, the algorithm to compute the greatest common divisor, or \gcd, of two numbers, dates back to antiquity (obviously). We can use it to make a fast test for primality, at least up to some confidence—and that’s where the inclusion-exclusion principle comes in.


Let us begin by the Euclidean algorithm. Originally, the algorithm was done by successive subtraction (and becomes quickly tedious as numbers grow), but the modern version, at least the one that I know of, uses divisions and remainders (modulo), and computes the \gcd(a,b) of two numbers a and b in O(\lg\min(a,b)) (counting division as an O(1) operation), which is very fast.

Read the rest of this entry »