Trigonometric Tables Reconsidered

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.

The Minimalist Calculus Cheat Sheet

We do not know closed form solutions for all optimization problems, even when they are somewhat innoccent-looking. One of the many possible methods in such as case is to use (stochastic) gradient descent to iteratively refine the solution to the problem. This involves the computation of… yes, the gradient.

In its simplest form, the gradient descent algorithm computes the gradient of an objective function relative to the parameters, evaluated on all training examples, and uses that gradient to adjust the model’s parameters. The gradient of a (not necessarily objective) function has the general form

Lossless Coding of CD Audio

Once upon a time, I discussed how to pick bit-rate for MP3, while considering re-ripping all my CDs. But if I’m to re-rip everything, I might as well do it one last time and use lossless compression.

In this post, we’ll discuss the simple script I cooked up to do just that, and a bit on how Flac works, and how it compares to MP3.

(more) Mild Obfuscation

In Mild Obfuscation, I proposed

as a “cryptographic” primitive. For , the only possible solutions for are and . But what are the solutions if ? Are there better than others?

Hash Functions (checksums, part II?)

On a number of different occasions, I briefly discussed Hash Functions, saying that if a hash function needn’t be very strong if the intend is to use it for look-up, contrary to cryptographic applications. But, unsurprisingly, it’s rather difficult to get a good fast hash function.

Coming up with a very good hash function isn’t easy, but we can at least make an effort to build one by understanding what makes a better hash function, especially by explicitly testing them. Let us have a try at building a good hash function (for look-up) from scratch.

Introducing Theano & PyLearn

Today I am going to talk about my day job a bit. Contrary to previous jobs, a good part (but not all) of what I do now is either public domain or open-source. Two the projects I joined recently are Theano and PyLearn.

Theano is a mathematical expression compiler that maps expressions described in Python to machine-efficient code, either targeting the CPU or the GPU. PyLearn is a work in progress that aims to provide a comprehensive machine-learning framework for Theano.

Mild Obfuscation

Sometimes, you have a small bit of data, may something like a GUID (for which there are many possible solutions), that you may have to store in a plain-text file, nothing crucial, not sensitive, but that you don’t really want your users to poke with, even if they really mean to. In such cases, you could use encryption, but it may be that mild obfuscation is quite sufficient and dissuasive.

So, if you don’t really want strong encryption, what can you do to provide a machine-efficient encryptionnette?

Pairing Functions

Sometimes you have to encode reversibly two (or more) values onto a single one. The typical example of a pairing function that encodes two non-negative integers onto a single non-negative integer (therefore a function ) is the Cantor function, instrumental to the demonstration that, for example, the rational can be mapped onto the integers.

In a more pragmatic way, it may be necessary to encode two values onto one for data compression purposes, or to otherwise exploit a protocol that does not allow many distinct values to be sent separately. The simplest way of pairing two integer is to interleave their bits, for example, with something like:

/* no comments (part II) */

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.

Analog Thinking

About five years ago, I found an old book, probably now an introuvable, Korn and Korn’s Electronic Analog Computers (D-c Analog Computers), 1956 [1].

Well, that mostly unrelated to today’s post, except that in some cases, relatively crude analog methods may give surprisingly good results in numerical problems (the topic came up while I was discussing the golden ratio and its place in art with friends, trying to make a point that it was mostly heuristic, bordering on the numerological). Take the pyramids, for example. The Ancient Egyptians did not have GPSes and laser guided telemetry. Yet, they managed to get some of their buildings incredibly well aligned with the celestial north.