# Monthly Archives: June 2008

## Good memories of WidSets

I used to be happy with WidSets

At that time, I could download my preferred feeds and read them everywhere offline on my Nokia Phone.

Now, using an iPhone, I have a bigger screen, Wi-Fi conectivity, a nice usability due to the multitouch screen and many other advantages of the Apple’s blockbuster. But I can’t read my feeds when I am not near from a hotspot. Ironically, I can download audio and video podcasts from iTunes, synchronize my device and listen/see them later. Why can’t I do the same with my RSS feeds?

There are many iPhone webapps to read RSS (even Netvibes has an iPhone specific version), but no one works offline. Unfortunately, neither WidSets will be the savior because it’s not compatible with iPhone (requires Java MIDP 2.0).

I’ve been looking for an iPhone RSS Reader that works offline. That’s my message:

• If you know one, please let me know, leaving a comment; I will really appreciate it.
• If you are a iPhone developer, that’s a good idea of a new application;
• If you are from WidSets development team, it’s time to code a new version compatible to iPhone;
• If you are from iTunes development team, feeds (as well as podcasts) downloading an synchronization would be really good feature.

In any case, I will really appreciate it.

## A roman inspiration for the Discrete Fourier Transform

Divide et impera (in english, divide and rule): that was one of the main foundations of the political, military and economic strategy of the expansionist Roman Empire. The roman ambition was too big to be achieved without division. They realized that the sum of necessary efforts to perform each part of a divided task may be less than one needed to perform the same task without dividing it.

Playing with algebraic notation without any mathematical or conceptual formalism: if a task that demands an effort $T$ to be performed could be divided in $n$ subtasks, each one with its respective $T_i$ performing efforts, it is intuitive to consider that $T_1+T_2+...+T_n=T$. Instead, the roman experience establishes the opposite: $T_1+T_2+...+T_n!

In mathematics and computer science, this “roman insight” is called Divide and Conquer Algorithm: a logical maneuver that breaks a big problem in many little others to (among other benefits) reduce its overall computational complexity. There are many applications of it, but my preferred is the Cooley-Tukey algorithm to process a DFT (Discrete Fourier Transform), most known as the Fast Fourier Transform. A really simple subtlety (breaking the problem into subproblems recursively) makes the problem much easier.

A classical result is to compute the DFT of a sequence with $N=2^n$ elements, $N^2$ complex multiplications are needed by the original DFT algorithm. If we the Cooley-Tukey algorithm instead, only $N \log_2 N$ multiplications have to be done. Don’t you see big difference? Imagine that you have to process a tiny signal with 1024 samples:

• Original DFT algorithm: $2^{20}$ complex multiplications
• Cooley-Tukey algorithm: $10 \cdot 2^{10}$

In this example the FFT, also called as 2-radix FFT (because the sequence is broken recursively in 2 others) is 102.4 faster than the original. If $N$ increases, the difference will be much more than this. What would be the Digital Signal Processing without such subtleties? So, let us divide to conquer.

Ave Cooley and ave Tukey!