Polymath Programmer

Today’s featured demo is Inflorescence by mfx. Download it here. It’s about 4 minutes in length and 19.5 MB in size.

Since I’ve discovered Capped, I am happy to announce that you can now watch demos even if you have a sucky, I mean, graphics-card-challenged computer. Get a load of this:

My first impression? Very X-Files…

The demo makes heavy use of a technique called bump mapping. It allows you to create detailed surfaces with less polygons. For example, we have here a curved surface:

Perhaps we want it to be rougher in texture. Instead of pulling and pushing vertices out of alignment on the curved surface, we could use bump mapping. Tada!

Recalculating vertex normals so that light falls on the surface and create shadows correctly (due to physically shifting the vertices) is expensive. The cheaper way is to use the same 3D model, and add a processing step before the lighting calculations. Thus it looks like the vertices are physically changed, but aren’t.

I don’t know how to put this. Things have been a little … quiet around here. So I’ve decided to put my analytical and intuitive skills to the test, and hopefully gain some answers…

So, over the past one year or so of blogging, I collected what little information I had. Some emails, some comments, some Stumbles, and a delicious bookmark or Reddit or so.

You are probably from the United States. In fact, you are 41.54% likely to be from the United States (courtesy of Google Analytics). Or you’re 9.35% likely to hail from Harry Potter’s country (urgh… Dementors). Ok fine, I don’t really know anything. You could be from, let me see, Canada, India, Singapore (helllooo!), Australia or some other fine place on Earth.

And now, I’m going to reveal an embarrassing fact. My blog traffic is about 50 unique visitors per day, spiking up once in a while when a post gets Stumbled or Reddit. Page views are about 1900 to 2100 per month. Rest assured you’re more than a web site statistic. I love talking to you (even if you’re a bit shy talking back sometimes…). R.E.S.P.E.C.T.

Despite the low number of web visitors, I have about 35 RSS readers (thank you mem!) and a PageRank of 4. I’m not sure exactly what Google’s algorithm does, but I think 4 is a good value.

Now, the page views thing wouldn’t have been a big deal, until I read Daniel Scocco’s answer to a reader question

6000 page views per month means you are getting around 200 page views daily, right? Well, I think that is a pretty low number for a website that has been online for 3 months. I would aim for some 2,000 page views after 3 months.

Mother of all source code! I’ve been blogging for over a year, and have only about 2000 page views per month. And I’m supposed to have surpassed that after 3 months? Oh man, I so totally suck at this…

Yeah, it’s been a long lonely journey sometimes… Which is why this came in at the right time

Yes, I feel like giving up sometimes. But I know I won’t. And I hope you’ll stick it out too.

You thought I’d stop the math lessons, did you? *smile*

Where was I? Oh right, analysing data. I’ve had someone come through from Dream In Code, highly probably a student. He emailed and asked me a studently programming question and I gave him an answer and pointers. How do I know he’s a student? Because another person asked the same question in the forums. Probably not from the same professional programming team, so rival classmates?

The only thing I wanted to handle better was that I should not have given the answer in the forums too. He came all the way here to ask me something. I should’ve treated him better. So whoever you are, mysterious student, I’m sorry and I should have respected you more.

Speaking of students, my intuitive senses tell me that you are probably in your twenties, probably a student still in school. Yes, I’m guessing, but based on data from the few comments and emails I received (tonality, grammar, and gut feeling). Hah, that’s something Google Analytics don’t have!

Even if you do comment, you don’t put your web site down. You’ve also given me false emails. This is fine, it’s just an observation, and I’m just happy I got a human response. Do you know how deliriously happy I get when I see 3 emails in my blog inbox and I think “Ooh, someone commented/emailed/asked something!” and I expect to find 1 email from a human (because, you know, the other 2 are spam)? I dance around waving my hands in the air for about 10 seconds. I’m not kidding.

There’s this other observation. The no-web-site part. This tells me you are either really cautious, or you really don’t have a blog or web site. Which means I get less links, even if you like my posts (you do like my posts, right?), since you’ve got nowhere to link them from. Well, you could always share a post you like on a bookmarking site or email your friends. Yes I still respect you even if Google or some other web arachnid thinks my blog isn’t worth much.

Combating this undesirable serenity, in my free slots in the space-time continuum of weekends, I practised hard. I pored over ancient texts, meditated on the future of programming, and bent my body into all manner of uncomfortable positions. And I’ve finally achieved it.

Other than my current super power, I am now also psychic! I understand that clicking through from a feed reader to comment on something, or even using my contact form may be too much trouble for you. So I’ve come up with a solution. If it’s too much hassle to submit something to me, then think it to me.

Complementing the 24 by 7 nature of the web, I am now psychically receptive to thought submissions. Because of this new service, I have decided to give up sleeping, which I usually do around 12 midnight to 6 am (1600 - 2200 UTC). I am dedicating this sacred 6 hour period to be attuned to the thought waves travelling around the world to this blog.

No more filling out names, email addresses, web sites, your question/comment, credit card numbers, phone numbers, home addresses! Everything will be autopsychically filled for you! I may look like I’m just lying in bed, but I’m really maximising my psychic receptivity. No, that’s not me snoring.

You can still psychically submit stuff to me in the other 18 hours. I’m just totally devoted to receiving psychic messages from you in the designated time slot.

To encourage submission, I’ll tell you a bit more about myself, so you’ll have fodder for questions.

• Worked at a startup company for exactly 6 weeks
• Have more than 5 years of professional programming experience
• Studied for 4 years in university, majored in Applied Mathematics and Computational Science
• Worked at 3 distinct companies (I repeated working at one of them)
• Speak 2 languages fluently (English/Chinese or C#/VB.NET. Take your pick)
• … And a partridge in a pear tree *smile*

Since I’m new at this, I may not always get your message, or even get the correct message. Psychic receptivity isn’t an exact science, you know. Your best bet is still emailing me directly.

Hmm… and you picked the card Ace of Spades, right?

My friend presented me with a puzzle: Construct a geometric shape with 7 points such that there are 6 straight lines, and each line must pass through 3 points.

My friend came up with a solution, but he wasn’t sure, so he consulted me. Actually there was a “model” answer, but he wanted to find another solution. So we had 2 solutions. I’ll present that model answer here so you can understand the puzzle better.

Points A, B and C form an equilateral triangle. Points D, E and F are the midpoints of lines AB, AC and BC respectively. Point G is the centre of the triangle.

Note: 3 points are collinear if they lie on a straight line.

The 7 points are A to G. The 6 lines are formed by ADB, AEC, BFC, AGF, BGE and CGD.

[I'm not going to go too much into math theories and proofs. Besides, I'm not even sure if I can recall them after losing track for so long...]

The first three lines should be easy to understand. D is the midpoint of AB, so ADB is a straight line. So it is for AEC and BFC.

E is the midpoint of AC, and BE is the perpendicular bisector (remember ABC is an equilateral triangle). And G lies on the line BE, since G is the centre of the triangle. So BGE is a straight line.

Using this reasoning, AGF and CGD are also straight lines.

I know, the explanation I gave isn’t quite backed up with math proofs, more with intuitive reasoning. But I’m sure they are (I just don’t know exactly which theorems to cite…).

So I have 2 favours:

• Send me a more proper explanation of the solution given above
• Or send me another solution (remember I have another one?)

I know there are at least 2 solutions. Just wondering if there are more. I will post my other solution, together with any submissions from you next Monday. Or earlier, depending on the number of submissions. You’re welcome to do both. *smile*

Since this is a geometric construction, a picture together with some explanations is appreciated. You can host the image on a site like Flickr, then add a comment to this post with a link to that image and a brief explanation.

Or you can send me your solution via email to vincent at polymathprogrammer dot com. Let me know if you want to remain anonymous (why?), and I’ll just post your solution only.

Your construction doesn’t have to be exact in proportions. Meaning if there’s a right angle, it doesn’t have to be 90 degrees exactly, so long as it looks like it’s 90 degrees. Just add some explanation to supplement the drawing. Try Paint.NET if you don’t have any image editing software.

Have fun!

In a previous article, I asked what this does

int foo(int para)
{
	int temp = para << 3;
	return temp + temp + temp;
}

The function basically returns a value of the parameter multiplied by 24 (thanks Mark!).

So why was it written that way? Speed.

From what I understand, in the olden days, multiplication was slower than addition and bit shift operations. I don’t know how slow, but it was slow. It was so slow that programmers (particularly game programmers) started replacing multiplication operations with a combination of additions and bit shifts.

Our example above with 1 bit shift and 2 additions was faster than just 1 multiplication operation. Hmm… that example may not be the best to use… Let me give another one.

The idea is to split the multiplication into additions first. So
i * 80
becomes
i * (64 + 16)
which becomes
(i * 64) + (i * 16)
which becomes
(i << 6) + (i << 4)
where we swap multiplications with powers of 2 to bit shifts. See, you do need some math in game programming.

Bit shifts are faster than additions, which are faster than multiplications. The speed difference obtained from rewriting the code was enough for some game programmers to adopt for use.

With modern computer chips, multiplications are just as fast as additions and bit shifts. So I did some comparison. Before I show you the code, there are 2 warnings:

• The code segments aren’t supposed to be tested on their own. The original speed improvements made sense when combined with their surrounding code.
• Measuring something changes it, so you’re not measuring the true value (some principle from physics. If you can find me a reference, I’d appreciate it).

I will present 4 different ways of multiplying by 24 using 4 functions. The first is the one posed in the previous post:

int foo(int para)
{
    int temp = para << 3;
    return temp + temp + temp;
}

The second function uses multiplication.

int goo(int para)
{
    int temp = para;
    return temp * 24;
}

I didn’t really have to declare the variable temp. I did it so all 4 functions declare a variable. Even variable declaration takes time, minute as it is, so I had to take that into account and standardise it across the 4 functions. This is the part where “measuring something changes it”…

The third function uses 2 bit shifts and 1 addition.

int hoo(int para)
{
    int temp = para;
    return (temp << 4) + (temp << 3);
}

Convince yourself that the return value is a multiplication of the parameter by 24.

The fourth function is a modification of the first function.

int loo(int para)
{
    int temp = para << 3;
    return (temp << 1) + temp;
}

If bit shifts are faster than additions, temp << 1 is faster than temp + temp, right? The use of temporary variables to hold intermediate values for another calculation is another technique used in game programming. This sounds a little vague, so I’m publishing another article to explain this further.

And here’s the timing code

const int cnMax = 500000000;
const int cnLoops = 20;
const int cnValue = 5;
DateTime dtStart = DateTime.Now;
DateTime dtEnd = DateTime.Now;
TimeSpan ts;
int i, j, temp = 0;

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = foo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = goo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = hoo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

temp = 0;
dtStart = DateTime.Now;
for (i = 0; i < cnLoops; ++i)
{
    for (j = 0; j < cnMax; ++j)
    {
        temp = loo(cnValue);
    }
}
dtEnd = DateTime.Now;
ts = dtEnd - dtStart;
Console.WriteLine(ts.TotalSeconds);
Console.WriteLine(temp);

I’ve initialised temp to 0 just before the test loops, and printed its value after the loops to check that the calculations give correct results. The loops are coded with a standard structure, and the only difference is the function used. All 4 functions are coded in as similar a structure as possible, to isolate only the method of calculation.

I’ve used nested for loops to increase the number of iterations. One loop can only go as high as 2^31 iterations (unless I use long). Nested loops increase this limit by doing a lower iteration limit multiple times.

And the conclusion? Multiplications are now just as fast. I didn’t get consistent results to rank the methods in order of speed though. Generally speaking, the 2-shift-1-add method (3rd function) is faster than multiply-by-24 method (2nd function).

That’s it. As an exercise, you might want to come up with better code to time them. Follow some simple rules:

• The results must be repeatable
• Tests must be standardised

A suggestion? Perhaps you can add more code to the loop structure (or the functions). So long as all 4 loops (or function code) are similar, you don’t need a minimalistic approach. This allows you to increase the percentage of identical parts between the tests, and thus highlight the difference in only the calculation method (let me know if you’re confused by this).

Have fun!

I was working at a software development house where one of those enterprisey .NET web applications was created for a large company. It was fairly standard. There were workflow processes, inventory tracking business logic, user management and the like.

The web application also had to display information in both English and Japanese (the customer was, you know, a Japanese company).

While the database column names were in English, there must be an option to display the Japanese equivalent. Suppose we had a table scripted like:

create table staff
(
STF_ID nchar(10) not null,
STF_NAME nvarchar(100) not null,
EFF_DT datetime not null
)

When I was creating datasets, I used Pascal case as recommended, and typed out words in full. So I had something like

ds.StaffID = "FIRSTID";
ds.StaffName = "Some name";
ds.EffectiveDate = DateTime.UtcNow;

The lead developer gently asked me why I coded that way. I explained the recommended practices for variable naming. I was actually quite puffed up with pride because of that knowledge.

The lead developer said he understood (though I didn’t think he did). Then he gave me an explanation why my method was a bad idea. He said translations for English and Japanese were based on resource files, and the contents of those files were based on the names used in the database tables.

So in the resource file, there would be an entry for STF_ID to be translated into “Staff ID” in English and “sutafu ID” in Japanese.

If I used “ds.StaffID”, it would be confusing for other programmers because I did some “translating” on my own. Someone else might translate differently and soon, the whole project would go up in flames. A standard way of referring to the database column name was established, and that was whatever the column name was originally. Even if it doesn’t look quite right in code.

So there would be

ds.STF_ID = "ID09183";
ds.STF_NAME = "another robot";
ds.EFF_DT = DateTime.UtcNow;

After some thinking, I had to concede. Using the database column name in code did make sense. There were full-time people hired to enter a code, word or phrase with the English and Japanese equivalent into the resource files. There were many developers working on that project. It’s just more efficient to use the column names as a standard.

That said, there’s much to be desired for the variable naming skills of the database administrators…