Saturday, April 30, 2005

Friday, April 29, 2005

Can You See Infinity

The figure above shows a simple circle. Mathematically a circle us made up of infinite straight lines. So now can you see infinity?

Now what would happen if we started counting numbers on the circle instead of straight line. How many points do you think a semicircle has? A quarter of a circle?

I am thankful, I can see infinity, even if not in all the detail.

NOTE: This is ofcourse not true on the computer, we have a limited set of pixels.

Thursday, April 28, 2005

Assert Yourself

Well, assertiveness is a nice quality to have. It's a virtue. The same thing holds good for programming. In my article Software Programming can be humbling. Point 7 talks about assertions.


The line above shows the affect of a bug in a software system. The line represents the state of the system. The bug is activated at the point "bad" in the line. The earlier we catch the bug, the better the chances of avoiding an ill affect later. Assertions can help catch bugs early and leave the system in a more stable state. This enables us to debug a little better.

In "C" assertions are supported by including assert.h.
assert(condition), takes in one parameter. From the man page of assert

The macro assert() generates no code, and hence does nothing
at all. Otherwise, the macro assert() prints an error message to stan-
dard output and terminates the program by calling abort() if expression
is false (i.e., condition equal to zero).

The purpose of this macro is to help the programmer find bugs in his
program. The message "assertion failed in file

Wednesday, April 27, 2005

Permutation code on popular demand

I have been asked by several people individually to make the permutation code available on the blog. Well here goes (The code is in Java and contains the iterative and the recursive version)

* Don Knuth's Permutation Algorithm

public class permu {
int[] a;
int j, k, l, n;

permu(int n) {
a = new int[n+1];
this.n = n;

for (int i = 0; i <= n; i++)
a[i] = i;


void visit() {
for (int i = 1; i <= n; i++)
System.out.print(a[i] + " ");

void swap(int j, int k) {
if (j == k) return;
int tmp = a[j];
a[j] = a[k];
a[k] = tmp;

// print all permutations of the numbers 1 to n
void permute() {

do {
j = n - 1;
while (j != 0 && a[j] >= a[j+1]) {
if (j == 0) break;

l = n;
while (a[j] >= a[l]) {

swap(j, l);
k = j+1;
l = n;
while (k < l) {
swap(k, l);
} while (j >= 0);

void rpermute(int k, int m) {

int i;

if (m == k) {

for (i = k; i <= m; i++) {
swap(i, k);
rpermute(k+1, m);
swap(i, k);

public static void main(String [] args) {
int n;
if (args.length != 1) {
System.out.println("usage is permu ");
} else {
n = Integer.parseInt(args[0]);

permu p = new permu(n);
permu p2 = new permu(n);
p2.rpermute(1, n);


Do you see the similarity with quicksort? For a good explanation of the algorithm see Don Knuth's Fascicle 4.

Function and Macro with the same name

Although the situation where you have a function and a macro with the same name is not common in programming, the possibility cannot be ruled out. The compiler will not complain if the macro is defined after the function.

Can one resolve the call to ensure that the function gets called?

Here is an example of how to do so

#include < stdlib.h >

max(int a, int b)
printf("calling function max\n");
return ((a > b) ? a : b);

#define max(a, b) ((a > b) ? (a) : (b))

int i = 10, j = 5;
printf("1) %d\n", max(i, j));
i = 5;
j = 10;
printf("2) %d\n", (*max)(i, j));

return 0;

The good thing about C programming is that the function name also acts a function pointer. In addition, a function can be called by its name or called by dereferencing the function pointer.

Sunday, April 24, 2005

Simplicity and Complexity

I think most humans think simple. All our thoughts begin with simple things. When the simplicity cannot meet our needs, we add complexity. So, the next time you see something complex, know that the complex thing was probably not the first thought, but the thought added to the simplicity to meet the extended needs.

I think the same thing holds for software programs. We write them and try to keep them simple. If we feel to meet our requirements using the simplicity, we add complexity. I think if something needs to be documented, it should be the need for the complexity. Given all my thoughts, I wonder if KISS (Keep It Simple Stupid), stresses on finding the best simple solution known to us. I think, it says before you add complexity, evaluate other simple solutions.

Saturday, April 23, 2005

Thought for the day

Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it.

Brian W. Kernighan

Friday, April 22, 2005

Funny Picture Of The Windows OS

I found this on David Salomon's web site. Please do not treat this as an insult to any OS, its just funny.

Please check

Thought for the day

I have made this letter longer than usual because I lack the time to make it short

Blaise Pascal

Boost Libraries

Everyone whose programming in C++, knows that Boost is a popular set of libraries, that keep up with the C++ standard in progress. I have been trying to understand MPL and find it very interesting. The classic book on templates is
The code library loki now form the base test cases for most C++ compilers. There are two forewords by Scott Meyers and John Vlissides (both worth reading in detail).

Thursday, April 21, 2005

Solution to the question posted before

In my post on Problem Solving and Decision Making I posted a problem

Given 9 points (arranged as 3x3 matrix) connect all the points using 4 lines. The rules are

  1. Tracing back is not allowed
  2. The pen/pencil should not be lifted from the paper while drawing

Well, here is the solution, the dots in blue are imaginary


For the curious lot, I drew this image using . I will share the code sometime later, when I blog on , if you need it now, email me or write a comment.

Wednesday, April 20, 2005

My Prediction for the Indo Pak Cricket Series

Well, I had predicted in the post Indo Pak Cricket Series that

  • India WILL win the test series

  • Pakistan MIGHT win the one dayer's

Well, the reality

  • The test series ended in a draw (India definitely had the upper hand)

  • Pakistan actually won the one day series

Problem solving and Decision Making

I recently attended a training on Problem Solving and Decision Making. The training was nice, what struck me most that there are so many known techniques for problem solving and decision making. I/We use many of them unknowingly, but there is so much more to explore. As I explore further, I shall share details on this blog, but meanwhile, I will leave you with a problem.

Given 9 points (arranged as 3x3 matrix) connect all the points using 4 lines. The rules are

  1. Tracing back is not allowed
  2. The pen/pencil should not be lifted from the paper while drawing.
More soon....

Sunday, April 17, 2005

Video Distribution

Participatory Culture has an open standards based video distribution software. They cover both sides of the TV equation DTV and Broadcasting. It is based of blog torrent. The claim is that you can watch TV and publish video. The steps for creating a video channel is here.

Saturday, April 16, 2005

Customer Service and Support

As a customer, I have had a lot of interesting experiences with customer support. I plan to document them here someday, but for now, I do not want a blog full of complaints. Here is what an uncle of mine (Mr Mukherjee) told me about customer support. They use a technique called the ABC technique, which all of us must be aware of.

  • A is for Avoid
  • B is for Bullshit
  • C is for Confuse

At first they will try and avoid the issue. You will hear things like "that's standard", "we use it all the time", "trust me, it is ok", etc. Second, they start bullshiting you , they will start talking without facts. "Sir, we get 150 new customers a day", "Our stats show 95% of our customers are happy", "I have gone beyond my limits to help you", etc. Third, they start confusing you. "What you have is the best, the other things are bad", "Let me share a secret with you", etc.

So, the next time, be more careful and ask for facts, justification and satisfy yourself and always check things and get back.

Friday, April 15, 2005

Software Stack

Have you heard people referring to their code as a software stack or the terms I/O stack, TCP/IP stack, Firewire, USB, etc stack. Have you wondered why the term stack is used? I was asked this and I thought I should illustrate it.

The figure (could be better) shows the application at the center of data processing. The color green shows data going out and red shows data coming in. Whenever, software is organized as layers, the data flow is always LIFO (Last In First Out) or FILO (First In Last Out). Since a stack functions in a similar manner, the code is referred to as a stack.

Tuesday, April 12, 2005


The book "blink" refers to the IAT as a mechanism to determine built in prejudices. I took one and found it very interesting. I would recommend the tests to friends and other people as well.

Leslie Lamport's Web Page

Leslie lamport has had an online web page for quite a while now. If you are looking for any of his classical papers, there are all present there. You can also find information on TLA (The Temporal Logic of Actions) as well. Check out the book on TLA+ as well.

Monday, April 11, 2005

Swapping and temporaries

Has anyone ever asked you this? "swap two integers without using temporary variables".
Well, here is the answer that most people give

a = a^b;

b = a^b;

a = a^b;

where 'a' and 'b' are the variables to be swapped.
Lets look at the traditional approach for swapping two variables


swap(long *a, long *b)


int tmp = *a;

*a = *b;

*b = tmp;


The second version and the first version both use three "C" statements to swap.
The first version will not work for non-scalar types. It will work only for integers, longs, characters and other integral types (called scalars). The second version is easier to maintain and can be extended to cover other types (using templates for example).

On some architectures a = a^b, a^b is stores the result in a temporary and then assigned to 'a'.


Sunday, April 10, 2005

Extension to Horner's rule

Horner's rule is used in computation to calculate polynomials using reduced multiplications. Please see the following references

  1. Eric W. Weisstein. "Horner's Rule." From MathWorld--A Wolfram Web Resource.
The same rule can be extended and used for debugging. When you have "n" unknowns in debugging, your problem is a polynominal of degree "n". Solve the unknowns 1 by 1 as Horner's rule does for calculation of polynomials, by taking factors and converting the calculation to n multiplications and additions. Solving too many unknowns at once is complex, solve them one by one

Wednesday, April 06, 2005

MIT Courseware

They have moved on so quickly ever since they started. The contents seem to grow quickly and the quality is good. Checkout the mathematics and Electrical and Computer Science sections.

Do Software Processes Make Sense?

In India many organizations compete by using their software certifications, but I have heard many engineers/developers complain that processes take away a lot of time. Many people complain about forging and process for the sake of processes. Here is my first take on software processes

Software processes are good, but they come at a cost. The trade off is not straightforward. Lets consider the following points

  1. Software processes serve as a discipline for the forgetful programmer
  2. Reviews give us insight into potential issues and save us the time of reworking things later
  3. Unit testing and Integration testing should be stressed upon, it really helps catch a lot of potential defects

On the other hand

  1. Excessive processes might be time consuming
  2. The focus should not shift from the work product to the processes

I hope I will not be called radical for stating that "sometimes its better to let the one odd complex/hard to reproduce bug be in there", its easier to fix when someone hopefully internally catches and tells you how it occurs, instead of spending a lot of time for finding and fixing it. This does not mean that you leave potentially disastrous things in your software, if you are satisfied with your testing -- move on!

New methodologies like eXtreme Programming are radical in their focus on testing, developer burn-out and online review. It makes no sense to write code that has never been tested.

I have been trying to figure out the main reason for software development being so expensive and sometimes buggy. Here is a first cut at the list of what software developers have

  • Software reuse
  • Extensive testing (which adds to the cost)
  • Good tools, compilers and debuggers (like gcc, lint, purify, etc)
  • Availability of free compilers, code and tools (they have licensing restrictions to a great extent)

I would also like to consider the discuss the pros and cons of Project Management

I think that about 70% of the productive code is written by 30% of the people.

Can we come with methods to streamline and refine the process of software development, reduce costs/increase productivity and reduce developer burn-out?


Bitkeeper is not going to be free anymore

Looks like Bitmover does not like OSDL, they have decided to end the free bitkeeper version. Kernel trap has the complete story. Wonder what Linus will move to next?

Fourier Series

I tried exploring the Fourier series a bit more (to learn DSP well). I found two wonderful references, which I must share.

Eric W. Weisstein. "Fourier Series." From MathWorld--A Wolfram Web Resource. The discussion of orthonognal functions is particularly insightful and so is the discussion on the Gibbs Phenomenon.

The second one is R W Hammings book on Numerical Analysis. I wish all books were written in the same simple manner this book adopts. After all, the "Purpose of computing is insight, not numbers"

I remember some of these details from my engineering days, but I wish I had access to these resources then.

Saturday, April 02, 2005

Introduction to CS

I would recommend Introduction to Computer Science to one and all. It has material everyone might find useful

Porting code from x86 to ARM

There is a good HOWTO on porting code at Porting software to ARM Linux. I found it quite useful. Before you call your code portable, you might want to look into this.

Believe In Ganguly

I got this email from a friend of mine

You can see the following message behind Maggie 2 minutes noodles pack:

Step 1: boil one cup of water

Step 2: as soon as ganguly goes for batting, put the noodles in the
boiled water and add the tastemaker.

Step 3: stir till ganguly is on the field.

Step 4: As soon as ganguly is back in pavilion, your noodles are ready to eat.

He is going through a rough patch, but I do not think he is replaceable. Everyone goes through a rough patch, but we must be patient and not write them off, just yet. See his statistics at crickinfo Sourav Chandidas Ganguly I do not think there is any body who can replace him just yet. He is close 10,000 runs in One-day cricket. Lets all be patient with him and trust him to come back to form. I think he should be back to form soon, maybe the next match?

References for Endianess

Are you struggling with a project that involves dealing with Endianess issues or if you want to compare and contrast little endian systems with big endian systems, here are some references

  3. On Holy Wars and a Plea for Peace
  4. Appendix 9B of Computer Organization and Architecture by William Stallings
I will try to add more as and when I find more references

Friday, April 01, 2005

Kernel Planet

Kernel Planet seems like a good site with blog extracts of famous people. I would recommend it to people fond of the Linux kernel. Remember there is always something to learn!

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...