Fun with rotations

The following puzzle might be trivial if you study physics and deal with lots of optics. Or, if you are simply good enough with math, especially with geometry.

First, visualize a 3-d Euclidean space where x-y plane is the "floor" and z points "upward". You are somewhere in this space.

Now assume you have two rotation operators denoted as Q and H. The idea is: both have fixed rotation angle but freely chosen rotation axis.

The common thing of both operators is that the rotation axis can be anything but it must lie on the x-y plane (i.e. the floor), so you can have [1 0 0]^T or [0 1 0]^T as the rotation vector but not [0 0 1]^T. This way, the rotation vector can also be specified by its angle with the x axis. If we denote the angles as a and b for the rotation vectors of Q and H, we write the rotation operators as Q(a) and H(b). Hint: the rotation vector of Q(a) is thus [cos(a) sin(a) 0]^T.

Next comes the difference. The rotation angle for Q is 90 degrees, while the rotation angle for H is 180 degrees.

Here is the quiz. Supposed you have a point at [0 0 1]^T. This point is first rotated by Q(a). The result is then rotated again by H(b). The questions are:

1. What will be the locus of the final result?
(Hint: find the result as function of a and b).

2. Can you replace the whole transformation (for the point at [0 0 1]^T only) by just one Q operator? If yes, determine the rotation vector of this Q.
(Hint: compare the answer to first question with the transformation result by only one Q).

Spoiler Warning: if you have passion for puzzles, go away and solve this one by yourself first. Then come back again here and compare it with the following analysis.

Remark

Although at a glance it looks complicated, the questions are quite easy to solve. It is a matter of doing rotation (couldn't be simpler!). The standard 3x3 transformation matrix will do the job, but usually you can do it much faster if you are familiar with quaternion. For convenience, here are the quaternions for Q and H:

Q(a) = 1 + i*cos(a) + j*sin(a)
H(b) = i*cos(b) + j*sin(b)

(Exercise: normalize the above quarternions)

Then, use the quarternions to find the rotation result with the usual quaternion algebra.

Answer to question #1

After rotated by Q(a), the point [0 0 1]^T will become [sin(a) -cos(a) 0]. Transform it with H(b) and you will get [-sin(2*b-a) cos(2*b-a) 0]^T.

Note: what you get is actually [x y 0]^T with:

x = cos(b)*sin(a-b) - sin(b)*cos(a-b)
y = cos(b)*cos(a-b) + sin(b)*sin(a-b)

which could be simplified using some trigonometric relations.

For the trained eyes, [-sin(2*b-a) cos(2*b-a) 0]^T is the equation for a circle because sin(2*b-a)^2+cos(2*b-a)^2 = 1. The z coordinate is 0, means the circle is on the floor.

So, the answer to the first question: the locus will be a unit circle on the x-y plane.

Answer to question #2

After rotated by Q(p), the point [0 0 1]^T will become [sin(p) -cos(p) 0]^T. This is also a unit circle. It means, direct transformation of [0 0 1]^T by Q(p) will also give a circle. That's the answer: yes, rotation by Q(a) followed by H(b), for the point at [0 0 1]^T, can be replaced by one Q operator.

But how to find p in Q(p)? Recall [-sin(2*b-a) cos(2*b-a) 0]^T from the answer to the first question. Comparing it with [sin(p) -cos(p) 0]^T yields p = pi - a + 2*b.

Or, you can specify the rotation vector of Q(p) directly as [-cos(2*b-a) -sin(2*b-a) 0]^T.

Not too difficult, isn't it?

three is the magic number

The best thing about cooking is: there is no right or wrong. It means, you will not make any mistake.

After some experiments, I found that adding some extra stuff when preparing mie goreng (a.k.a fried noodles) gives it a distinctive and unique taste. It's not like the common fried noodles anymore. Here I share the secret: basil leaves cut into pieces, few slices of ginger, and a bit of curry powder. Like a charm.

Aller guten Dinge sind drei.

iPhone in Germany

In Germany, iPhone is sold with a price tag of 399 euros. But then you must sign a 24 months exclusive contract with T-Mobile, with a minimum plan of 49 euros monthly fee. This means (ignoring depreciation) at least you'll lose 1575 euros in total. With one time activation fee, that makes it 1600 euros. On top of that, if you want to actually make a call, be ready to face the 39 cents/minute rate, which is (insanely) expensive compared to other offers. The fact that it is T-Mobile is also interesting, I don't know whether it means a bless or a disaster.

Due to a move from Vodafone, T-Mobile is also forced to sell an unlocked iPhone. So you can pick your favorite provider but only if you're ready to shell out 999 euros for that. Might be better, but 999 euros? You can get 21 Motorola w205 with that amount of money :-) Or do/buy other sensible stuff.

Usually I am not that skeptical. But this does not sound like a success recipe at all.

SpeedCrunch: "Nona" edition

SpeedCrunch version 0.9 has just been released. The improvements are not really user visible, but check the ChangeLog and fixed bugs, nevertheless. Also, this release is available in 17 languages (and contributions are welcomed).

Source tarball and Windows installer are ready for consumption. Go to http://code.google.com/p/speedcrunch/ and get it while it's hot. Binary packages for major Linux distributions usually follow soon.

And now that the first ever release of KDE 4 is on the horizon, it's time to think to start enabling KDE integration in SpeedCrunch.

Note: Nona is nine ninth in Portuguese.

extraordinary

The only extraordinary thing about me is that I am just an ordinary man.

(on thinking about myself)

Random number 1..5 to 1..7

The task is to solve this puzzle:

Given a function which produces a random day Kliwon, Legi, Paing, Pon, Wage, write a function which produces a random day Sunday to Saturday

OK, I modified the question a bit. Read about Anno Javanico if the names of the day sound strange to you. Originally, it says:

Given a function which produces a random integer in the range of 1 to 5, write a function which produces a random integer in the range of 1 to 7

This is well-known as one of the so called Microsoft/Google interview questions. There are million ways to solve it. Here is my take. Bear in my mind that my math skill is mediocre and I never studied computer science, so don't be surprised if the next few paragraphs look bogus and stupid.

Spoiler warning: If you have passion for puzzles, go away and solve it and then come back again later. Don't let this blog entry spoils the fun for you.

First, let's assume the random number 1..5 is generated by the following (the randomness, or lack thereof, of stdlib's rand() doesn't play any significant role here):

#include <stdlib.h>
int rand5()
{
 return 1 + rand() % 5;
}

Now we must write rand7() which gives an integer between 1 and 7 and which is allowed to call only the above rand5().

The trivial solution, which you should have in mind in a fraction of seconds, is:

int rand7()
{
  return rand5();
}

because nowhere it says that the original nor the new function must give a random number following a specific distribution, e.g. uniform distribution. Of course this can or can't be the real answer, depends on how you look at it.

The next logical step is assuming that the return value of rand7() must have a uniform distribution. The probability to get one of the number in the range of 1..7 is therefore approximately 0.143.

So what comes to mind is to reduce 1/5 probability from rand5() to 1/35, then increase it again to 5/35, which equals to 1/7. The former can be done by calling rand5() several times and treating the first result as 1..5, the second as 6..11 and so on until 31..35. The latter is easier, it's just a modulus operator. The code for this idea (which is shorter than the explanation above):

int rand7()
{
 static int c = 0;
 int x = rand5() + c;
 c = (c + 5) % 35;

 return (x % 7)+1;
}

(I know static variables can be evil, but that's another chapter...)

The disadvantage is obvious, the result is not completely random. For example, the first call will not yield 1 or 7 at all. Another variant is then by making c a bit random, though now that requires two calls to rand():

int rand7()
{
 static int c = 0;
 int x = rand5() + c;
 c = (c + 5*rand5()) % 35;

 return (x % 7)+1;
}

Another nice solution is by using rejection sampling, similar to the famous Box-Muller transform. Here we expand the range of 1...5 to 1..25 and reject anything larger than 7. The code is:

int rand7()
{
 int x = 8;
 while( x > 7)
  x = rand5() + 5*rand5() - 5;
 return x;
}

Pity that we throw away 8..25. It can be improved by reducing the rejection range to 22..25, IOW we would take anything in the range 1..21:

int rand7()
{
 int x = 22;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 int r = 1 + (x % 7);
 return r;
}

(or, further by going to 1...125 and rejecting 120..125).

Modulus of 7 can be "optimized" by hand, this is because 7 is a Mersenne prime. For the details, see what I wrote before on modulus with Mersenne prime. This looks useless and even obfuscates the code, but it's harmless and you can tease your interviewer :-)

int rand7()
{
 int x = 25;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;

 int r = (x >> 3) + (x & 7);
 r = (r >= 7) ? r - 6 : r + 1;
 return r;
}

Care to share your solutions?

PictureFlow on another real device (or Cover Flow for HTC Touch)

Update: see also PictureFlow running on different mobile devices.

HTC Touch is a touch-screen smartphone running Windows Mobile 6.0. It is armed with 200 MHz 32bit Texas Instruments OMAP 850 processor and 2.8 inch color transflective 240 x 320 screen. Like other Windows Mobile devices, HTC Touch is interesting because Qt runs also there, using Qt/WinCE.

After Chumby, HTC Touch is another real device that enjoys Apple-like Cover Flow effect, of course by using PictureFlow. Espen recently showed PictureFlow running on his HTC Touch, as can be seen in his YouTube video:

"Awesome", according to him. We trust you, Espen :-)

Now I know that someone must have tried this on the Greenphone. Can anyone give a video or even a picture?

(Picture from HTC Touch product page)

deja vu

long weekend

Downtown is like a dead city.

Today is Allerheiligen (All Saint's day) and it's public holiday in some states in Germany (Baden-Württemberg, Bayern, Nordrhein-Westfalen, Rheinland-Pfalz und Saarland).

Of course, like many others, wisely I take vacation on Friday, thereby giving me a very nice and enjoyable long weekend.