February 12, 2013

The possible strategies for data compression fall into two main categories: lossless and lossy compression. Lossless compression means that you retrieve exactly what went in after compression, while lossy means that some information was destroyed to get better compression, meaning that you do not retrieve the original data, but only a reasonable reconstruction (for various definitions of “reasonable”).

Destroying information is usually performed using transforms and quantization. Transforms map the original data onto a space were the unimportant variations are easily identified, and on which quantization can be applied without affecting the original signal too much. For quantization, the first approach is to simply reduce precision, somehow “rounding” the values onto a smaller set of admissible values. For decimal numbers, this operation is rounding (or truncating) to the nth digit (with n smaller than the original precision). A much better approach is to minimize an explicit error function, choosing the smaller set of values in a way that minimizes the expected error (or maximum error, depending on how you formulate your problem).

Read the rest of this entry »

Trigonometric Tables Reconsidered

February 28, 2012

A couple of months ago (already!) 0xjfdube produced an excellent piece on table-based trigonometric function computations. The basic idea was that you can look-up the value of a trigonometric function rather than actually computing it, on the premise that computing such functions directly is inherently slow. Turns out that’s actually the case, even on fancy CPUs. He discusses the precision of the estimate based on the size of the table and shows that you needn’t a terrible number of entries to get decent precision. He muses over the possibility of using interpolation to augment precision, speculating that it might be slow anyway.

I started thinking about how to interpolate efficiently between table entries but then I realized that it’s not fundamentally more complicated to compute a polynomial approximation of the functions than to search the table then use polynomial interpolation between entries.

Read the rest of this entry »

/* no comments (part II) */

September 6, 2011

In a previous installment, I discussed the quality of English in comments, arguing that the quality of comments influences the reader’s judgment on the quality of the code as well.

That’s not the only thing that can make code harder or easier to understand. Today (anyway, at the time of writing), I was working on something where arbitrary-looking constants would constantly come up. I mean, constants that you wouldn’t know where they’re from unless there’s a comment. A clear comment. Let’s see some of those.

Read the rest of this entry »

Python References vs C and C++

June 14, 2011

As I’ve mentioned before, my new job will ask me to program more in Python than C++, and that’s some what new for me. Of course, I’ve criticized Python’s dismal performance on two occasions, getting me all kind of comments (from “you can’t compare performance like that!” to “use another language then” passing by “bind to external high-performance libraries”).

But it seems that my mastery of Python is still quite inadequate, and yesterday (at the time of writing, anyway) I discovered how Python’s by-reference parameters work. Unlike C or C++ that use explicit syntax to specify what kind of object we’re dealing with (either by value, pointer, or by reference), Python is a bit sneaky.

Read the rest of this entry »

Suggested Readings: Programming Pearls

May 15, 2011

Jon Bentley — Programming Pearls — 2nd Ed, Addison-Wesley, 2000, 240 pp. ISBN 0-201-65788-0

(Buy at Amazon.com)

The central theme of this book is efficiency and economy of solutions of programming problems. However, if the book is globally interesting, it would greatly benefit from an update; the proposed programming style—independently of the gist of the solutions— is old school in many respects. The style should probably updated to take modern programming style into account, say, à la Alexandrescu and Sutter for C++.

Read the rest of this entry »

INT_MAX is a terrible NaN (Safer Integer Types, Part IV)

March 15, 2011

I came across a lovely bug lately. Integer arithmetic, especially in C and C++ it seems, is error-prone. In addition to the risk of having the wrong expressions altogether (a logic error, one could say), integer arithmetic is subject to a number of pitfalls, some I have already discussed here, here, and here. This week, I discuss yet another occasion for error using integer arithmetic.

Consider this piece of code, one that you have seen many times probably, at least as a variation on the theme:

Read the rest of this entry »

Scary Code

November 9, 2010

If you code a lot in a week, you’re bound to make some (possibly) amusing typos. Almost every time, the typo is detected by the compiler and an error is issued, but sometimes you manage to (mis)type valid code! And I recently make one of those typo and I started wondering how far we can push this idea in writing really, really, really, really ugly code.

Read the rest of this entry »