Older blog entries for fzort (starting at number 73)

Bin packing is NP-complete

After almost a year, I decided to go back to an almost abandoned project. It seriously needs a facelift.

Lots of things in the code are embarrassing. For instance, I'm creating a different texture for each character in the font. That is yucky. So I had a little fun yesterday writing code to pack the characters of a font in a single 2^n*2^n texture. Here is a sample.

Mouse vs. Supercomputer

Not too long ago, news that IBM researchers simulated a (damaged) mouse brain on the Blue Gene/L were making the rounds. Anyway, someone gave me a link to the research report:

"... we were able to represent 8x10^6 neurons (80% excitatory) and 6300 synapses per neuron in the 1 TB main memory of the system. Using a synthetic pattern of neuronal interconnections, and at a 1ms resolution and an average firing rate of 1 Hz, we were able to run 1s of model time in 10s of real time."

Maybe trying to simulate a mouse brain is too ambitious a goal. Perhaps they should've started with lobsters instead.

Energy figures:

• IBM Blue Gene/L: 1.5 MW
• Mouse brain: 8*10^6 neurons * 3*10^-12 Watt/neuron/firing rate * 10Hz = 0.24 mW [source]

The Departed

Crap. I want my four hours back (not really sure if it actually lasted four hours, but it sure felt like it).

I heard it was based on some Hong Kong cop movie. I bet the original was better.

O filme pode ser condensado em um aforisma aprendido em meus anos de Escola Municipal Tenente José Maria Pinto Duarte (o famoso "Pintão"), na longínqua década de 80: "cagoeta morre cedo".

I shall start using my Advogato account more often. If that bothers you, feel free to lower my journal's rating. I entertained the idea of using Livejournal of Wordpress or something for my random ramblings, but both are blocked from work.

OMG BRUCE SCHNEIER CAUGHT WRONG IN PRINT LOL

In Applied Cryptography, latest edition, in the subsection on the Chinese Remainder Theorem, the following code is given without justification:

/* r is the number of elements in arrays m and u;
   m is the array of (pairwise relatively prime) moduli
   u is the array of coefficients
   return value is n such than n == u[k]%m[k] (k=0..r-1) and
                               n  < m[0]*m[1]*...*m[r-1]
*/
int
chinese_remainder(size_t r, int *m, int *u)
{
    size_t i;
    int modulus;
    int n;
    modulus = 1;
    for (i=0; i<r; ++i)
        modulus *= m[i];
    n = 0;
    for (i=0; i<r; ++i) {
        n += u[i] *
          modexp(modulus/m[i], totient(m[i]), m[i]);
        n %= modulus;
    }
    return n;
}

This does not work. bi observed that it could be made to work if the line in boldface was changed to:

n += u[i] * modexp(modulus/m[i], totient(m[i]), modulus);

Weirdly for a decade-old book, this is not in the latest errata.

Coding

I don't get to do much of that at work. When I do, it involves maintaining the Worst Code Ever. In order to avoid becoming this guy, I've been playing a bit at sites like SPOJ, acm.uva, and Project Euler. It's less demanding than trying to participate in a more or less relevant free software project, and you're rewarded for doing just the (at least for me) interesting part of programming, that of actually solving problems.

In the process, I've been accumulating a body of math factoids such as a formula for the size of the Farey sequence of order n, or wtf a Farey sequence is for that matter. I should start documenting that sort of stuff in my page sometime.

Listening to

Sarah White - You're Not Easy, You're Hard

I solved this problem the other day. It's related to Ulam's spiral, a pretty crazy little mathematical factoid. I'm glad the creationists don't seem to have heard about it yet.

Way too much images on advogato's recentlog lately.

Found a dynamic programming solution for this algorithmic problem and was quite pleased with myself for a while. Then showed the problem to a friend, and he quickly came up with a simpler and much, much faster, greedy solution, that provably works. Bummer.

Played Go quite a bit against Wally on the train on my way to work today. Something it's seriously missing is the concept of life and death. Sometimes pretty simple tsume-go arise and it will happily allow me to play on the vital point, killing a large group of stones. A consequence of this shortcoming is that it uses Chinese counting. You need to keep playing until you remove all the enemy stones you can from the board, even the obviously dead ones.

Of course, saying that a position is "obviously" settled is not enough - the problem is provably not efficiently computable, a consequence of the PSPACE-completeness of Go.

Like with other hard problems, heuristics can help in this case. This paper, by the author of Handtalk (a very strong Go playing program), looks quite useful.

I should probably move my diary somewhere else. I'd like to write more to practice my English, but most of the stuff I want to write about - a book I read, mathematics, learning Go, some SPOJ problem I've been working on - is not really directly related to Free Software (with which I haven't been really much involved lately).

I still suck at Go.

OpenSpecies: yeah, it's also a skill that can be acquired.

I'm studying Kaoru Iwamoto's "Go for Beginners". Despite what the title may suggest, it's anything but easy.

I ported Wally, an old Go playing program, to *gasp* Windows CE, adding a GUI to it. I can run it on HalJr, my ancient Cassiopeia E-11. This should give me something interesting to do during the long train rides to/from home. Gnu Go has been ported to CE, but it doesn't run on the Cassio.

The program is not very strong, but that's ok, since neither am I.

I'll post some pictures after I polish it a bit.

If you think I should throw that away and get a more capable palmtop that can run GNU/Linux instead, you obviously haven't been introduced to São Paulo's wonderful urban train infrastructure.

badvogato:

I need to construct a 3D goboard where there is no 'corner' reduced liberty but unified 4 liberties for every positions on the new GO surface.

Forget 3D, you want a goban on a toroidal topology. Think Asteroids. This project has Go on torii and other exotic topologies, I think.