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 »

8 Comments | algorithms, Mathematics, programming | Tagged: benchmark, benchmarking, binary gcd, boxplot, Euclid, GCD, recursion | Permalink

Posted by Steven Pigeon

February 7, 2012
In a previous post, I told you about a short script to rip and encode CDs using Flac, and I discussed a bit about how LPC works. In this post, let us have a look on how efficient Flac is.

Let us use a quantitative approach to this. Since I have a great number of songs, we can use statistics to give us a good idea of what kind of compression we can expect.

Read the rest of this entry »

1 Comment | data compression, Data Visualization | Tagged: box plot, box-and-whiskers, boxplot, Compression Ratio, FLAC | Permalink

Posted by Steven Pigeon

July 28, 2009
There’s always a number of graphics primitives you will be using in all kinds of projects. If you’re lucky, you’re working on a “real” platform that comes with a large number of graphics libraries that offer abstractions to the graphics primitives of the OS and, ultimately, to its hardware. However, it’s always good to know what’s involved in a particular graphics primitives and how to recode it yourself should you be in need to do so, either because you do not have a library to help you, or because it would contaminate your project badly to include a library only to draw, say, a line, within an image buffer.

Lines are something we do a lot. Perfectly horizontal or vertical lines have very simple algorithms. Arbitrary lines are a bit more complicated, that is, to get *just right*. This week, let us take a look at a few algorithms to draw lines. First, we’ll discuss a naïve algorithm using floating point. We’ll also have a look at Bresenham’s algorithm that uses only integer arithmetic. Finally, we’ll show that we can do better than Bresenham if we used *fixed* point arithmetic.

Read the rest of this entry »

12 Comments | algorithms, bit twiddling, C, C99, embedded programming, Instruction Sets, Mathematics, Portable Code, programming | Tagged: 32 bits computing, 32bits, 64 bits computing, 64bits, AMD64, assembly language, box plot, boxplot, branch prediction, branchless, branchless algorithm, Breseham, Bresenham Algorithm, Line, microsecond, pipeline, x86 | Permalink

Posted by Steven Pigeon

June 23, 2009
Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.

Read the rest of this entry »

2 Comments | algorithms, bit twiddling, C, C99, data structures, hacks, Mathematics, programming, theoretical computer science, Uncategorized | Tagged: address transformation, box plot, box-and-whiskers, boxplot, comparison sort, gettimeofday, graphs, median, microsecond, quartile, quartiles, Quick Sort, QuickSort, radix, Radix Sort, tests, timer, trials | Permalink

Posted by Steven Pigeon