C++ Evolution

If you are interested in the evolution of C++, see these links

1. C++ Evolution Issues
2. C++ STL WishList

Can my blog be audible?

I am exploring techniques to make my blog audible, yes audible!

Unfortunately, I do not own the blog server and hence do not have access to any technology on the server side. I will be forced to implement something at the client end. Does anybody know of a good technology to help me make my blog audible?

Let me know if you do or any suggestions you have

Return Addresses

Andrew Appel states that return addresses were earlier pushed on the stack by the function call instruction. Data shows that it is faster and easier to pass the return addresses in a register. This has two advantages

1. It keeps the memory traffic down
2. It avoids building in any particular stack discipline into the machine

This is certainly true for MIPS, ARM, etc. For the Intel IA32 platform see Notes on Translating Three-Address Code to Assembly Code for the X86.

The return address is still stored on stack. Generally the ENTER, LEAVE and RET instructions are used for stack manipulation. Gcc uses CALL, LEAVE and RET.

The Composite Pattern

The Design Patterns (Gang of Four) book explains the composite pattern. See Composite Pattern

One example of a composite pattern is a file in a filesystem/directory hierarchy. The figure below shows a probable implementation of a filesystem hierarchy using the composite pattern

First Analysis of Swap Space

When I was learning to configure my first Dynix/Ptx system, I was told by a senior team member to ensure that the swap is at least twice the memory size. I asked him what was the logic behind that, he said, it was a rule of thumb. In the time to come, I would learn the some reasoning behind it. I would at this point recommend “Modern Operating Systems, by Andrew S. Tanenbaum”. He uses Don Knuth’s Fifty Percent Rule as the basis for his analysis. Let me explain the Fifty Percent Rule first

The simple explanation of the rule follows. In the state of equilibrium

1. Half the number of memory operations are allocations, the other half is freeing
2. For the half that is freeing, half of those operations result in holes being merged (contiguous ones)

This tells us that the ratio of holes to allocated blocks is fifty percent.

In the state of equilibrium there are half as many holes as total allocated blocks. A hole is referred to as a available memory (free memory). If the total allocated memory in blocks is n then the number of holes is n/2.

The total available blocks is 3n/2 and available blocks is n/2. The ratio of free memory to total available memory (assuming block sizes are equal) comes to 1/3. So if you have 256MB of RAM on your system and want it to be available free for the next task you want to run, then you must allocate a swap size of 512MB, so that the ratio of 1/3 is held.

There are of course complications to this simple rule or calculation that I explained above. I will try and explain some of those complexities in the next series of swapping articles.

Thought for the day

In today's Koffee with Karan, Rishi Kapoor said
"Don't let failure get to your heart and Don't let success get to your head".

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.

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 

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] + " ");
  System.out.println();
 }

 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 {
   visit();
   j = n - 1;
   while (j != 0 && a[j] >= a[j+1]) {
    j--;
   }
   if (j == 0) break;

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

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

 void rpermute(int k, int m) {

         int i;

         if (m == k) {
                 visit();
                 return;
         }

         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 ");
   return;
  } else {
   n = Integer.parseInt(args[0]);
  }

  permu p = new permu(n);
  p.permute();
  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 >

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

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

int
main(void)
{
 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.

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.

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

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 http://www.ecs.csun.edu/~dsalomon/nowindows.html

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).

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.

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....

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.

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.

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.

A Comparison of Version Control Systems

There is a good comparison of version control systems here

IAT

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.

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

inline

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'.

Comments?

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. http://mathworld.wolfram.com/HornersRule.html
2. http://planetmath.org/encyclopedia/HornersRule.html

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

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?

Comments?

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.

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

1. http://www.linux-mips.org/wiki/index.php/Endianess
2. http://en.wikipedia.org/wiki/Endianess
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

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!

Subsets of a given set

I read this interesting problem in Sahni, the problem is to generate all given subsets of a set. Sahni's answer is given on the web site at solution to exercise 5. I tried to solve the problem using iteration. There are two ways to do it

1. Convert Sahni's solution to use iteration
2. Use the method I describe (its a bit complex, but interesting)

The solution described in (1) eventually ends up generating all possible binary numbers for a word of length n. Where n is the number of elements in the set. This method will definitely not work for multisets. I solved the problem by first coming up with a method to generate combinations of C(n, k) which prints out all combinations of n taken k at a time. I have the C# implementation of the code, if you want to see it, let me know. This method can be easily extended to handle multisets (I think!)

Here is my implementation

//
// I am not an expert C# programmer, 
// I am learning the language please 
// feel free to comment on the style 
// and/or on the code
//
using System;

class Combo
{

 int[] c;  // counter for holding c1 .. ck
 int k;   // k of C(n, k)

 Combo(int k) 
 {
  init(k);
 }

 // For C(n, k), call it with k
 void init(int k)
 {
  c = new int[k+1];
  for (int i = 0; i <= k; i++)
   c[i] = i;
  this.k = k;
 }

 // prints all combinations of C(n, k) 
 // assuming they are in lexicographic
 // order 
 void combination(int n, int k)
 {
  int j;
  bool uc = false;

  do {
   visit();
   j = k;
   // counter reached max limit, increase the
   // counter next in the chain
   while (j > 0 && (c[j] == ((n - k) + j))) {
    j--;
    uc = true;
   }
   if (j == 0) break;
   c[j]++;
   if (uc) {
    // reload counters
    for (int i = j+1, l = 1; i <= k; i++, l++)
     c[i] = c[j]+l;
    uc = false;
   }
  } while (true);
 } 

 void visit()
 {
  for (int i = 1; i <= k; i++)
   Console.Write(c[i] + " ");
  Console.WriteLine();
 }

 // Find all subsets of a set
 void subset(int n)
 {
  for (int i = 0; i <= n; i++) {
   init(i);
   combination(n, i);
  }
 }
 
 public static void Main(string[] args)
 {
  int n;
  if (args.Length != 1) {
   Console.WriteLine("usage is subset ");
   return;
  } else {
   n = int.Parse(args[0]);
  }

  Combo p = new Combo(n);
  p.subset(n);
  
 }
}

CodeWorker

I found this interesting tool CodeWorker. I cannot wait to get started with it, hopefully sometime soon! If you guys start earlier, please feel free to share your experience as comments on my blog

GCC now has a Wiki

GCC now has a wiki at GCCWiki. I loved the Deadly Sins of a Compiler Writer. I think I committed most of those sins while working on my tiger clone

The Elements of Style Online

This classic has been available online for a while now. The Amazon Page for the book has reviews, sales ranking and other good information about the book.

Fascicles 1 and 2 available as books

Don Knuth's Fascicles are finally available in book form. Fascicles 1 and 2 have been released.

References for Permutations

In the article Iterative Permutations, I mentioned about my experience with permutation generation. I would like to give further references (this list will grow)

1. Permutation generation methods
2. Art of Computer Programming, Fascicle 2
3. Permutation Generation Methods (ACM paper)

Cell Phone with Built In Projector

PhysOrg.com is reporting this story on a cell phone with a built in projector. The image is taken from there. This sounds like fun, I can't wait to get hold of a device like that. The article is published here

Tool turns English To Code

Please see
Tools Turns English To Code

Holi Hai

Today is Holi Indiatimes has a good article on the Changing colours of Holi. I played a little bit of Holi myself (unexpectedly though, I must admit), I was cornered and coloured with colours.

Unix PATH overload

Many of us, customize our shells under Unix (for the difference between Unix and UNIX - see the Art of Unix Programming). We usually add to our PATH environment variable. Usually what we do is

PATH=$PATH:[paths to add]

Lets assume this file is called .profile and is read by the shell on start-up. This approach is good, but if the user were to change our .profile and run

. $HOME/.profile

Then on seeing the PATH variable, it would have repeated path names.

If the change to PATH was

PATH=$PATH:$HOME/bin:.

The on running . $HOME/.profile for the first time the user would see PATH as

[original]:[user's home directory]/bin:.:[user's home directory]/bin:.

One easy way to work around this problem is to use the following approach in your .profile

OLDPATH=${OLDPATH=$PATH}
export OLDPATH
export PATH=
export PATH=$OLDPATH:/sbin:/usr/sbin:$HOME/bin:.

and then customize PATH as the user did previously, repeated running of
. $HOME/.profile shall now not cause the PATH environment variable to grow uncontrollably

Adobe Acrobat 7 Reader Available

This was posted on our local TUG group (TUGIndia)

Adobe have released GNU/Linux version of Acrobat Reader 7.0.
Please grab from:
ftp://ftp.adobe.com/pub/adobe/reader/unix/7x/7.0/enu/



The screenshot above is Adobe Reader 7 running on my computer. This reader seems much better than Adobe Reader 5. As you can see I am reading chapter 2 of the Linux Device Drivers 3^rd Edition PDF book available for free online.

Linux Device Drivers 3rd Edition (The Indian print is out)

The Indian Edition of LDD3 is now out. The Indian Edition is printed by Shroff Publishers. As of now, the publishers have not announced availability of the book on their web site.

Iterative permutations

I spent quite a bit of time investigating permutations. The easiest known method for generating permutations is recursion. Iterative permutations are hard but not impossible. A quick comparison showed the following results. The C/C++ code without profiling was about 4-7 times faster than the java implementation.

The profiling had an impact on the C/C++ code. Java did better with profiling.

The recursive and the non-recursive versions did almost equally well. Here are some results for lengths 10 and 12.

Java Profile

Flat profile of 17.65 secs (1569 total ticks):
main

Interpreted + native   Method                   
0.2%     3  +     0    permu.permute
0.1%     1  +     0    permu.rpermute
0.1%     1  +     0    permu.main
0.3%     5  +     0    Total interpreted

 Compiled + native   Method                   

50.5%   792  +     0    permu.permute
49.2%   772  +     0    permu.rpermute
99.7%  1564  +     0    Total compiled

Flat profile of 0.01 secs (1 total ticks): 
DestroyJavaVM

Thread-local ticks:

100.0%     1             Blocked (of total)

Global summary of 17.74 seconds:

100.0%  1577             Received ticks

java -Xprof permu 12

Flat profile of 215.68 secs (18868 total ticks): 
main

Interpreted + native   Method                   
0.0%     1  +     0    permu.rpermute
0.0%     1  +     0    Total interpreted

 Compiled + native   Method                   

50.6%  9544  +     0    permu.permute
49.4%  9323  +     0    permu.rpermute
100.0% 18867  +     0    Total compiled

C++ execution time

/usr/bin/time ./permu 10
0.23user 0.00system 0:00.31elapsed

/usr/bin/time ./permu 12
30.44user 0.20system 1:28.34elapsed

rpermute is the recursive version of the permutation generator and permute is the lexicographic permutation generator. As can be seen, the execution times are almost the same. As far as the stack size is concerned, the iterative version uses a stack size of "s" and the recursive version goes upto a worst case of "ns".

The development of rpermute is much easier compared to the iterative version

Visual Programming

There is a new project called GIPSpin. It talks about graphical visualization of code and thread creation.

Ramanujan's work on partitions extended

Please see Classic maths puzzle cracked at last. For those who want to know a little bit more about Ramanujan, please see Srinivasa Ramanujan There is another reference to the above mentioned article.

Bucknor vs India

In today's match, Steve Bucknor cost India dearly. The batsmen (Tendulkar) kept complaining about the bad light. In the end Bucknor gave him out when he was not, the fielding team themselves were not appealing as much. Please see Bucknor is useless. I wonder if ICC will ever take any action against such bad umpires, who are biased. He has made so many bad decisions and mostly against India. Do a google search and you will find out what many people think about him.

It is sad to say that he is the first umpire to umpire 100 tests.

Steve Bucknor, India is furious with you. Please get your act right! ICC please do something about this!

But looking at another aspect, life balances out and hopefully Sachin Tendulkar will get lucky and given not out when out. Today he was in a great nick, it could affect the end result of the match.

Google code on sourceforge

Google has released a couple of tools on sourceforge. Please see google's code website. I have not downloaded the tools or registered for using the API's yet. May be in the future?

Google seems to provide good Python support. I must start using python more.

Yet Another Template Change

I changed my template for several reasons

• I like the new look and feel of this template
• I removed the sitemeter tool

Lets hope you like it better this way.

The Games Complements Play

I recently came across a program, that converted negative values to positive by using the following logic.

if (n < 0) {
n = -n;
}

It seemed correct and would work almost all the time. Why do we use the word almost. I was reading some parts of Don Knuth's famous Art of Computer Programming and the MMIX architecture


The only number that cannot be represented in signed integers of length k is 2^k. The number -2^k can be easily represented. What if n = -2^k

Taking two's complement (add one to ones' complement of the number) of returns the same value. If you are interested in the reason for difference in the apostrophe placement for the ones' complement and two's complement - see Art of Computer Programming volume 2

Coming back to "n = -n", this code does not work for n = -2^k.
The same thing has been mentioned in Andrew Koenig's C Traps and Pitfalls

Tendulkar joins 10,000 club

Even though his 35th century is evading him, he did join the 10,000 club. His performance has gone almost unnoticed, due to Sehwag's performance. The photo of him after getting there and a link to the story of his achievement. The story points to the location where the photo resides

I hope the Indian selector's will be patient with V V S Laxman. He is a great player and is one innings away from his display of class.

The Art of Unix Programming

I owned the book for a while, but just started reading it in detail. The book is available online at Eric's Web Page. See if you finding it interesting?

LDD3 is now online

I was scared that this might not happen, but it has as it did the last time. The book is available as PDF (as of now) online. Please see Linux Device Drivers, Third Edition for more details and the PDF files.

Linux now has a security team

Please see the following email from Chris Wright. The new team talks about security disclosure, disclosure dates. This makes sense for enterprise installations and for security of Linux. The average geeky Linux programmer might complain, but I am glad to see the good things being adopted by the Linux maintainers.

Indo Pak Cricket Series

Well, the much talked about cricket series is here.

Here is my favourite picture of day 4, test 1 from rediff.com



I have a prediction for the series

• India WILL win the test series
• Pakistan MIGHT win the one dayer's

Blogging is addictive

Once I start blogging, I feel addicted. Blogging gives one the sense of satisfaction of sharing and expressing ones thought.

The Two Way Thought Process

Sometimes while solving a problem, I have discovered for myself that the discovery works two ways

1. If a small problem is solved, one can generalize the solution and it becomes a learning
2. If a generic problem is solved, one can apply it to niche areas and problems to solve complex problems

Usually, I keep oscillating between (1) and (2). However, I wonder whether one should apply (1) or (2) to a problem first? I suspect it should be (1) and the authors of Concrete Mathematics seem to agree. What do you think?

Thought for the day

Think many times before doing something that you cannot undo

Balbir Singh

Lazy Programmers Thought for the day

Why do now what you can postpone until later? Why postpone something that can be avoided all together?

anonymous

The C++ Programming Language

I was re-reading some portions of The C++ Programming Language especially chapter 5, I think every C/C++ programmer must read it atleast once a year.

Being good at everything (allrounder)

I think it is normal for everyone to expect a person good in one field to be generally good in others and that might be true. But I have come across people who are narrowly focused in their domain, that they might not be good at anything else. Technology is growing at such a rapid phase that it is not possible to keep up and be good at everything. So here's a suggestion

1. Be good at what you do
2. Use common sense everywhere else (including above)

Law of Bug's

I heard this someplace recently

"The law of bug conservation states that - bugs can neither be created nor destroyed. The total number of bugs remain constant, they only change from one form to another"

Software programming can be humbling

My experience has been that software programming can humble the most experienced programmer. You sometimes need a fresh look at the problem at hand and probably fresh eyes as well to debug a problem. Based on my experience, I am trying to come up with a simple set of rules that might help the programmer with his situation, these rules can be generalized so much so that it almost becomes common sense.

1. Try not too hard to debug a problem, take a break, come back later
2. Are you able to explain the problem you are seeing? Can you describe the pattern in which it occurs? Stop looking at the code and try to understand the pattern and possible explanation for it
3. Use your friendly debugger or your friendlier console log messages
4. Can you narrow down the problem to something simpler
5. If you are dealing with numbers - think signed != unsigned
6. Are you dealing with garbage data? Garbage data implies faulty pointers or storing more than the capacity
7. Do you assert() the code (yourself) frequently enough
8. Is this a recently created problem - look at what you changed recently
9. Can you simulate what the computer is doing (if you can find the faulty logic in code) on paper or in your mind. If so, there is a good chance of you catching the bug
10. Don't solve the same problem twice
    

I will keep adding to this list as I get more input from all of you or start thinking clearly.

Some articles I recently read

Here are some articles/interviews I recently read and enjoyed

http://www.stlport.org/resources/StepanovUSA.html
http://www.sgi.com/tech/stl/drdobbs-interview.html

One of the best forewords

I have been reading the forward to "STL Tutorial and Reference Guide" by David R. Musser, Gillmer J. Derge and Atul Saini. The foreword is written by Alexander Stepanov and its one of the best I have read. Great work!

Answer to Fundamentals of Numbers

In the blog post Fundamentals of Numbers, a fundamental question was posted.

Well here is the hint

Take beta=10 and n = 121

121 = 1 * 10^2 + 2 * 10 + 1

Now try the following C based pseudo-code

while (n/beta) {
printf("%d\t", n % beta);
n /= beta;
}
if (n % beta) {
printf("%d\n", n % beta);
}
printf("\n");


It prints out the numbers in opposite order. Get it? No matter what the value of n and beta, we can find a sequence representing n in terms of beta.

This should really be an axiom.

Thought for the day

Attrition is equivalent to "Gifting talent to your competitors"

Balbir Singh

Lay off's are equivalent to "Ending the mistake that began elsewhere"

Balbir Singh

Issues with IE now

My Firefox issues got solved (by using meta tags), thanks to Narasimha. IE does not do a good job of rendering the last post and hence the entire page. As usual, I am working on it.

Fundamentals of Numbers

I am reading Numerical Analysis, a mathematical introduction by Michelle Schatzman. I found some really interesing questions for computer programmers and thought I would post them here followed by their answers in a short while. The questions are quite simple, but you learn more than you expect by answering them

Here is the first one

Test MATHML

I frequently use mathematical notation in my daily programming and study. Since some of the notation I use here is mathematical as well, I plan to use MATHML for some of them. But I am unable to add MATHML into my BLOG for now. So, I am stuck with photos that TeX produces, like the one below

Premier Hockey League

I think one of the best things that happened to hockey is PHL. The finals last night was among the best hockey matches I have seen recently. It was a thrilling encounter with the Sher-e-Jalander requiring to win within 70 minutes. The Sultans won 2-1, sending the home crowd into jubilation.

Reprints of Low Price Edition (LPE) of Books

One of the biggest disadvantages of Low Price Editions of books is that reprints are merely "reprints". They do not fix any errata as the original editions do. The LPE is only as good as the reprint that the publisher buys from the parent company and does not update it until a new edition is out.

Efficiency of Autoboxing in Java

I am trying to catch up with the changes in J2SE5.0. One of the feature additions is auto-boxing and auto-unboxing. It's a great feature and simplifies programming, reduces errors, but as well noted it is not efficient. Over use will result in a performance hit. Please see autoboxing notes from SUN for more details. I tried some experiments myself and found that auto-boxing happens each time, no caching is done for auto-boxed or auto-unboxed values. Below is a program and its disassembled output





public class AB4 {
public static void main(String args[])
{
Integer j = new Integer(1000);
int i = j + j + j + j;
int k = j + j;
System.out.println("i is " + i);
System.out.println("j is " + j);
System.out.println("k is " + k);
}
}


Compiled from "AB4.java"
public class AB4 extends java.lang.Object{
public AB4();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: return

public static void main(java.lang.String[]);
Code:
0: new #2; //class java/lang/Integer
3: dup
4: sipush 1000
7: invokespecial #3; //Method java/lang/Integer."":(I)V
10: astore_1
11: aload_1
12: invokevirtual #4; //Method java/lang/Integer.intValue:()I
15: aload_1
16: invokevirtual #4; //Method java/lang/Integer.intValue:()I
19: iadd
20: aload_1
21: invokevirtual #4; //Method java/lang/Integer.intValue:()I
24: iadd
25: aload_1
26: invokevirtual #4; //Method java/lang/Integer.intValue:()I
29: iadd
30: istore_2
31: aload_1
32: invokevirtual #4; //Method java/lang/Integer.intValue:()I
35: aload_1
36: invokevirtual #4; //Method java/lang/Integer.intValue:()I
39: iadd
40: istore_3



As can be seen, for each occurrence of j, the value is auto-unboxed and then added, could these values not be cached? Maybe, I need to specify a higher level of optimization, but at first glance I could not find specification of the level of optimization.

Interviews response

My Friend Narasimha spoke about interviewing at http://narasimhagm.blogspot.com/2005/02/interview.html
I find it very interesting, given that I have taken hundreds of interviews and attended quite a few (many times for the kick or out of optimisim or to learn something and/or check my current skills :-))

Here is his list

1. Do not get too technical (There is google for this)
2. Try to find out if the candidate is passionate about what he has worked on
3. Ask some questions which probe his analytical ability
4. Ask about academic projects.
5. Probe whether he understands some concepts about source control, unit testing
6. Ask whether he has uses google :)

Let me add a few more points

1. See if the candidate is capable of working independently
2. Don't expect him/her to know the obscure details of the language he/she uses for programming. After all a programming language is just a tool
3. Check his/her learning ability and flexibility and the willingness to adapt to new technologies
4. Check to see if he can tell you the reason for leaving his current job
5. Many more to come

What I find very surprising from my experience is that 95% of the people cannot write any algorithm to sort a list of arrays, 80% of the people need help with binary search and 95% people do not understand recursion. I would like to add more statistics here soon

Thought for the day

The difference between what we do and what we can do, can solve all the problems in the world

Mahathma Gandhi

Trouble with Firefox

Firefox seems to require a refresh to update contents of web-sites I visit. I need to find a solution to fix this problem or file a bug with them.

Archiving the WEB

I recently found http://www.archive.org/web/web.php. I found it simply amazing, I looked at pages from 1996 and compared them to pages of today, one can clearly see the advancement in web technology. From CGI to technologies of today.

If you do not find your link the in the archives, use http://pages.alexa.com/help/webmasters/index.html#crawl_site to add your URL and the bot will visit your website and start archiving it

Comments on Big-Oh (O) from CLRS

Section 3.1 of CLRS (Cormen, Leiserson, Rivest, Stein) discuss the Big-Oh notation O. The linear function an + b is O(n²), which is easily verified by taking c = a + |b|. cg(n) is a²n + ba + |b|b + |b|an. At the first glance this seems true if a + b >= n, since O is the worst case, we can use this. In addition, a = b = sqrt(n) also help in making the function O(n²). Please see the plots below


Figure 1: Plot of n²

Figure 2: Plot of a = 1,b = n

Figure 3: Plot of a = n,b = 1

Figure 4: Plot of a = sqrt(n),b = sqrt(n)

Figure 5:Plot of a = 1,b = 1

I think it is non-trivial to suggest find out that the function is indeed
O(n²). Comments please!

Expecting Linux Device Drivers, third (3rd) edition


Linux Device Drivers second edition was really good. I think the announcement of the third edition is around the corner. Hopefully the Indian edition or the free online edition will be out soon. Here is a link to some material the authors have put up on the web http://lwn.net/Articles/2.6-kernel-api/ also check out http://www.oreilly.com/catalog/linuxdrive3/

Probability

My favorite mathematical topic and well covered by the Cormen, et. al book. Chapter 5 of the book covers this topic in depth and explains applications to the "The Hiring Problem". The most interesting thing is ofcourse is the uniformly random permutation and the exercises built around it.

Randomize-in-place(A)
n <- length(A)
for i <- 1 to n
do swap (A[i], A[Random(i, n)])

The example above demonstrates a uniformly random permutation. See the book and if you need help with the exercise solutions, we can discuss it.

The Birthday Paradox implies that with atleast 28 people, we can expect to find atleast one matching pair of birthdays. But, what about the pigeon hole principle? The pigeon hole principle states that we require atleast 366 people to definitely find one pair of matching birthdays.

Programmers

Given my software development background and the industry experience I have; I decided to classify programmers. Think of this as a taxonomy, I plan to grow this list as time progresses. A programmer could fall into several categories at the same time

• The Post-it Programmer :- Usually arrogant programmer who believes that he/she was not created to write certain programs or to do lowly jobs like testing or writing test cases. Does a good job like post-it notes, but cannot be used for anything else.
• The Erratic Programmer :- No matter what level experience he/she has, they will always write buggy code.
• The Pretending Programmer :- Pretends to work and thinks that he/she has achieved a lot, but in reality the work done is zero.
• The Cautious Programmer :- Will take forever to think about the program and discuss it forever, but will never make it into useful working code.
• The Cribbing Programmer :- Believes that every one else has better work to do than what he/she does. Such programmers always complain and are never happy with anything
• The Lazy Programmer :- Will waste away time until he/she can. Then at some point realize that wasting time is no longer feasible and starts working

To the professional

I purchased a book that addresses the professional as audience of the book. The solutions and the Instructors Manual is available only to professors and teachers. The question is -- why do the smart people get solutions. I can understand the students not getting the solutions, but why do the professors need it? Are they not already smart to figure out the solutions by themselves?

Need help with KDE

I have been trying to come up with a common uniform framework for detecting information about KDE windows. I tried using QObjects, QWidgets, KWinModule, KWinInfo. I was able to extract information about all active windows using QValueList iterator. I could not use the WId's further. I even tried dumping the objectTree associated with KWinModule, but with no luck.

New algorithms group at google

There is a new group a google on algorithms. Please visit http://groups-beta.google.com/group/compalgos
The idea is to discuss various algorithms, their math, books, exercises, solutions, etc. Of course all algorithms from all fields are welcome

My web page

I have had a web page for a long time now. I have not done too much with it so far, but I plan to get better at adding material and information.

Here is the link http://geocities.com/bsingharora/

Cheaper editions of books

I was wondering if it is possible to make published books cheaper by adding advertisements into them like magazines do. I spoke to a few friends and they all welcomed it, if it drives the price down. This should also push down piracy of books.

Low Price Edition of Pearson Education India

I was told by a book seller that the Low Priced Edition for sale only in the Indian subcontinent has made it's way back to the United States and other nations. That is a very bad thing to happen.

To give you an idea of the cost difference, lets take the example of

"The C Programming Language" by Kernighan and Ritchie.
The Indian edition costs Rs 95 (close to $2)
The American edition costs from $42

"The design of the Unix Operating System" by Maurice J Bach
The Indian edition costs Rs 195 (close to $4)
The American edition costs from $74

The pearson education web-site was brought down for a while and now all editions are going to be edited (chapters removed/added) and no Indian edition will be available for atleast one year after the original publication

TeX vs Troff

I have been using TeX for some time now, I used to use troff earlier. Books like those from Tanenbaum and Richard Stevens still use troff where as authors like Ullman have migrated to TeX/LaTeX. The troff authors mention that real authots still use troff. I am confused now. Troff is simple to use, but TeX is very powerful and fits well into the pdf, especially with context. I find it difficult to draw pictures using metapost, where as pic is quite simple.

If you guys have any suggestions or comments, please feel free to post them

Book review

I recently reviewed some parts of a couple of books for william stallings

1. OS 5th Edition
2. Computer Architecture 7th Edition

The first book is out and looks very good. The second book is going to be out later this year.

Languages

I have mostly ignored programming languages so far, but I intend to learn and talk more about C++, Java and C# in the future and join the OO revolution. I have been spending some time with the tiger compiler implementation.

Dinner with a friend and his girl-friend

I had dinner with a friend of mine and his girl-friend. It was a good experience today, but I think I ended revealing something about my friend (which my friend did not tell his girl-friend). All in all, they both seem to enjoy the outflow of information.

A Trip down memory lane

I visited my native place after a period of 8 years. I realised for the
first time, how deep routed relegion in my country (India) is. In the 10 days
I had, I travelled, travelled, met people, and travelled. Aah! what a good
break from my routine work!

Golden Ratio

Of late, I have read a lot about Golden Ratio and why it is also called
the devine number. For example, Golden Ratio hashing is among the best
known hash algorithms. Don Knuth, in chapter 2 of Metafont draws an
'A' the area of the upper half to lower half is 0.618. The same ratio
occurs all throughout our skeleton structure - see Dan Brown - "Da
Vince Code"

Infinite number of twin primes

I think I have a proof of the fact that there are indeed
an infinite number of twin primes. But I am not
a professional mathematician and shy about my proof.
The proof seems so simple, that I wonder why nobody else
discovered it so far (Am I correct about this one?). That
makes me doubt my proof.

Can anybody help review it?

Here comes the answer

The C99 draft specification says section 6.10.3.4

If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file s preprocessing tokens), it is not replaced.

Updates and the C question

Its been extremely long since I posted something. I have been extremely
busy with a lot of things. I think I found a proof for the fact that there exist
an infinite number of twin primes. I am not sure if this proof has been
discovered at all.

I have been working with mathematical analysis on my own and I am
stuck with Topology, Bolzano Weierstrass theorem.

Enough of mathematics, I found a very interesting thing about
the C PreProcessor

Lets say, you have the following code


#define a b
#define b a

int
main(void)
{
int a, b;
return 0;
}


What do you expect a and b to be replaced as?

Answer in the next blog