Intel’s Game Demo Contest announce winners

…and our friend Mauro Persano won in two categories: 2nd on Intel graphics and 5th on best game on the go.

The game, Protozoa, is a retro Petri-dish style frenetic shooting-the-hell-out-of-the bacteria, virii and protozoa stuff that comes in your way. You can play with a PS2 (two-analogue sticks) control, one for the movements and other for the shooting, or just use the keyboard. The traditional timed-power-up and megalomaniac explosions raise even more the sense of nostalgia.

You can download the latest Windows version here but don’t worry, it also runs pretty fine with Wine.

Have fun!

Numerical methods package in C++

I still code in my spare time and for a while I’ve been gathering some numerical methods I did at university in an easy-to-understand generic C++ package. Despite being easy to understand, I also tried to implement the best method I knew for each problem.

The root finding algorithm is based on Brent’s method which is, in turn, based on the secant method. If everything fails, it throws an exception and you can use the safe bisection method.

The integration is using the Romberg’s method, which is a further extrapolations of Simpson’s method which is already much better than the trapezoid basic method.

For Interpolation I’m using the Natural Cubic Spline but would like to implement other types of splines (like complete, periodical, clamped etc). The interpolation is working, but I couldn’t managed to get the coefficients right yet.

Other codes I have are Monte Carlo, Runge-Kutta and Markov Chain (this one using boost graph library for C++) and will be integrated soon. I’ll let you know when it’s done.

Silly projects of the week

Last week I did two silly but still quite funny projects: word search on protein sequences and chat bot using markov chains.

Word search

Searching for similar sequences among the known proteins to understand evolutionary paths and function similarities is a powerful algorithm called BLAST. Following the same lines I spent a few minutes to develop a similar (but not quite the same) algorithm to search for all dictionary words on all UniProt sequences.

The algorithm will look into a dictionary (say /usr/share/dict/words) and for every sequence it’ll find the words in it, allowing a few (no more than 2) amino-acids to be between the letters. Than it gives a weight to the match based on the size of the word and the “added length” due to additional amino-acids in between. You can also restrict the number of letters on the word list to avoid too short or long words.

The results for 7 to 9 characters words in English searched only on Swiss-Prot entries are:

STRANGE  1.4
CHARADE  1.75
SLEDGED  1.75
MEALIER  1.75
DEMEANS  2.33333
DETAINS  2.33333

Markov bot

I knew a markov chain could have true wisdom but I never tried to make it actually talk to anyone until a friend told me about MegaHAL (much better than my markov model, of course). I decided to give it a try and got the XMPP bot from the Python examples and plugged in my markov program on all phrases spoken to it.

In the beginning it was awful, of course, it knew nothing. But with time (and hard work from some friends to actually teach him about leisure, programming, physics etc) it could babble a few coherent words once in a while.

The results are complete rubbish, below is a sample of the complete non-sense conversation I had with it now:

rengolin: how are you doing? have you managed to find the answer to Life, The Universe and Everything?
oraculoids: with an amazing company makes the basic points of some operator
rengolin: operator or not, you must come to reality and sense the danger there is in talking like that after such a complex and meaningful question
oraculoids: dead as an interface to follow an animal
rengolin: whatever animal you prefer, I would say but it seems that you are now driving the conversation
oraculoids:
rengolin: aha! I know you didn’t have answers to everything!
oraculoids: how is in between and pray
rengolin: I don’t pray too much, really, I’m not that kind of a person anyway…
oraculoids: but at the conversation it’t fall into them!
rengolin: I would never say that, especially not with you my friend
oraculoids: A design pattern is a practical laywer
rengolin: lawyers have no purpose other than screwing up the poor
oraculoids: hi bot
rengolin: I am not a bot
oraculoids: field of some of life, love them!

Quite stupid, I might say, but still I had a lot of fun doing it and that’s what matters… 😉 In spite of that, though, megaHAL is quite an impressive program and BLAST is a very powerful search mechanism.

RDBMS, to rewrite or not to rewrite… I got confused…

Mike Stonebreaker (Ingres/Postgres) seems to be confused as well…

First he said Google’s Map/Reduce was “Missing most of the features that are routinely included in current DBMS”, but earlier he said to ditch RDBMS anyway because “modern use of computers renders many features of mainstream DBMS obsolete”.

So, what’s the catch? Should we still use RDBMS or not? Or should we still develop technologies based on relational databases while Mike develops himself the technology of the new era? Maybe that was the message anyway…

My opinion:

MapReduce is not a step backwards, there are sometimes when indexing is actually slower than brute-force. And I’m not saying that on insert time the indexes have to be updated and so on, I’m saying in the actual search for information, if the index is too complex (or too big) it might take more time to search through the index, compute the location of the data (which might be anywhere in a range of thousands of machines), retrieve the data and later on, sort, or search on the remaining fields.

MapReduce can effectively do everything in one step, while still in the machine and return less values per search (as opposed to primary key searches first) and therefore less data will be sent over the network and less time will be taken.

Of course, MapReduce (as any other brute-force methods) is hungry for resources. You need a very large cluster to make it really effective (1800 machines is enough :)) but that’s a step forward something different from RDBMS. In the distributed world, RDBMS won’t work at all, something have to be done and Google just gave the first step.

Did we wait for warp-speed to land on the moon?! No, we got a flying foil crap and landed on it anyway.

Next steps? Many… we can continue with brute-force and do a MapReduce on the index and use the index to retrieve in an even larger cluster, or use automata to iteratively search and store smaller “views” somewhere else, or do statistical indexes (quantum indexes) and get the best result we can get instead of all results… The possibilities are endless…

Lets wait and see how it goes, but yelling DO IT than later DON’T is just useless…

UPDATE:

This is not a rant against Stonebreaker, I share his ideas about the relational model being far too outdated and the need for something new. What I don’t agree, though, is that MapReduce is a step backwards, maybe not even a step forward, probably sideways.

The whole point is that the relational model is the thesis and there are lots of antithesis, we just didn’t come up with the synthesis yet.

Computer Forensics: Recovering Files – Part 2

Last week I introduced you Active@ File Recovery as a useful computer forensics tool and file recovery software.

Today, we go a bit further in Active@ File Recovery usage.

A few tips when using Active @ File Recovery to recover your lost files:

    1. Before install Active@ File Recovery for Windows it’s a good idea create a Recovery point, so, that way, if you don’t like the software or if it doesn’t work properly, you can easily restore your system for the situation before to install Acite@ File Recovery.
        – Actually, it’s a good idea set up a Recovery Point for Windows every time you will install any software in your Windows System. It will provide the basis for recovery if and when needed.
      • – A recovery Point is the basis that allows you undo all changes made in your system and recover all your configurations.
    2. Try to use Active@ File Recovery without install, so, there’s no risk to overwrite your files.
    3. Install Active@ File Recovery in a different Hard Drive or partition of the affected drive partition to avoid of writing over data that you wish to recover.
    4. After install Active@File Recovery, you can open it and navigate just like you do in Windows Explorer.
    5. Go to the file or folder you want to recover and choose recover option.

    1. When you choose this option it will open a new windows asking where do you want to place the recovery file or folder.

  1. If you chose to save at the original place, the system will warn you to save it in another place to avoid overwrite your file or folder. In this case, it will be impossible a future recovering operation.

But remember, not every lost file can be recovered. You have to think about the following possibilities:

    • We have to assume that the file entry still exists, I mean, it was not overwritten. The more the files have been created on your HD, the less chances that the space for that deleted file has been used for other entries.
    • We assume that the file entry is more or less safe to point to the proper place where file clusters are located. If the operating system had been damaged file entries right after deletion, the first data cluster becomes invalid and further entry restoration will not be possible.

So, as a general advice, do not write anything in the drive containing your deleted data and do not try to recover your files to the original drive data.