Branch-free detection of sign

I found something wrong in the following video,

https://www.youtube.com/watch?v=Z59REm2YKX0

The branch free code by author is,

bool OppositeSign(int a, int b) {

    return (a ^ b) < 0;

}

But the compiler can internally convert the statement "return (a ^ b) < 0;" into conditional code.

Here is a branch free code, if the processor provide bit manipulation instructions (most of the processors provide)

// except inputs every thing is compile time constant

bool OppositeSign(int a, int b) {

    unsigned const shift = sizeof(int)*8-1;

    unsigned const mask  = 1 << shift;

   

    return unsigned((a&mask)^(b&mask)) >> shift;

}

Online Median Tracing Algorithm

Given a stream of integers (flow read from disk or some other resource, like a sensor counting some events). How can we find the median of elements read so far?


It is an interesting online algorithm. Online, we mean the algorithm that can output result after any instance of input processing. For example, after reading i-elements we should be able to tell the median of i-elements read till now.


I read the question on Gulli blog, and came up with some solution. I have posted the algorithm on Geeksforgeeks.


http://www.geeksforgeeks.org/archives/14873


Again, it is just for my reference of link. Any comments, please post on Geeksforgeeks.

Operating Systems - A Fun

August 13, 2011
I read “operating systems” during my academics, and fortunately got an opportunity to work on a commercial OS development for embedded systems. The following list of resources will help to understand the OS internals,

1. Minix – the foundation behind Linux implementation. The source code is available from the book Operating Systems Design and Implementation, 3e, by Tanenbaum and Woodhull.

2. Micro C OS - II and Micro C OS – III. If you want simple OS implementation for embedded system, it is the book for you. The recent updated kernel (µCOS - III) supports virtual memory management. Code is free for educational purpose, get from “http://micrium.com/page/home”. The story behind Micro C OS is interesting, an example of what passion and need can do, read the story in the book, the same was available on their website.

3. eCos is another RTOS written in C++. However, it seems it is now defunct.

4. RTEMS – The first (IMHO) open source kernel implementing rate monotonic scheduling. Written in C++.

5. pintos – created by a Stanford student, available for free. Check their website.

The above links help to navigate real code. But for the concepts behind the code, we need to consult relevant books or papers.

For example, read this paper for Linux O(1) scheduler implementation, you need to be aware of priority arrays, complexity basics, etc. Similarly, for practical use of linked lists in Linux read Robert Love book.

Decision Trees - Fake Coin

30-July-2011

I have pending post from few months. It is on application of decision trees to analyze algorithms.

The puzzle is given below,


"We are provided a two pan fair balance and N identically looking coins, out of which only one coin may be defective. How can we trace which coin, if any, is odd one, and also determine whether it is lighter or heavier in minimum number of trials in the worst case?"


Try to solve the puzzle on your own, and then read my systematic solution on the following link

http://geeksforgeeks.org/?p=9411".

There are other applications of decision trees, like analyzing comparison based sorting routines. We may think that comparison is cheap operation, however, in reality we deal with large objects than simple integers, where comparison is costly  operation. We need decision trees to analyze lower bounds of comparison sorting.

There are other advantages of trees like solving game of Nim, probability problems, etc...

Again the link is for my reference. Any comments post on Geeksforgeeks.org site.

Text Search Engine

6-June-2011

Given huge text file or collection of documents. How will you search for a word in that collection?

Lucene is an open source library that indexes text for efficient information retrieval. Here is the project home page. Lucene can be effectively used to index words in any document format, that makes it flexible to adopt web applications. The story behind Lucene is interesting to read. The name Lucene is the name of better-half of the creator of Lucene software, named Dogg Cutting.

Lucene was originally implemented in Java, and there are port to other languages like CLucene in C++. Lucene can be used as information retrieval on small sites.

The Qt library includes Lucene port to Qt C++ under 3party libraries. We can experiment with the Qt code for information retrieval on small documents.

Connecting Capacitances - Project Euler Problem#155

8 - May - 2011

I came across an interesting problem. Given N capacitors (or inductors, resistors) of same value say C (unit is Farad). How many difference capacitances can be derived from these N capacitors connected in series, parallel and series-parallel combination.

For example if N = 1, only one way it can be connected. If N = 2, they can be connected in two different ways of series and parallel. If N = 3, they can be connected in 7 different ways. That means we can derive 7 different capacitance values from given 3 capacitors of same value. These 7 combinations can be found pictorially on the Project Euler page.

Can we generalize it? Yes. Say the total possible capacitances are represented as S(n). If we observe, only the difference between S(n-1) and S(n-2) will participate using next capacitor. For example to calculate S(n) we need the difference DELTA = S(n-1) - S(n-2), and all combinations upto S(n-1). The new capacitor C(n) can be connected in series and parallel with every combination of DELTA..

With an example it will be clear. We know S(1) = 1, S(2) = 3 and S(3) = 7. To calculate S(4) we need DELTA = S(3) - S(2) = 4. We can connect the 4-th capacitor in series and parallel with these 4 combinations, overall it adds 4 * 2 = 8 more combination to the existing 7 combination upto S(3). So, clearly S(4) = 2 x DELTA + S(3) = 15. There is a recursive formula. It is evident from the recursion tree given below for S(5).

Solution can be generalized as

         S(n) = 2 x (S(n-1) - S(n-2)) + S(n-1)

              = 3 x S(n-1) - 2 x S(n-2)

Base case S(1) = 1, S(2) = 3 and S(3) = 7.

We can code above formula using recursion easily.

int totalPossibleCapacitances(int n)

{

    static int S[] = {1, 3, 7};

    if(n > 3)

        // Non trival case

 return 3*totalPossibleCapacitances(n-1) - 2*totalPossibleCapacitances(n-2)

    else

        // Trivial case

        return S[n - 1];

}

Complexity: What will be the complexity? If we observe the recursion tree, the problems are overlapped. Similar to the Fibonacci series. The characteristic equation of generalized solution can be written as

x ^ 2 - 3*x + 2 = 0 whose roots are x1 = 1 and x2 = 2. The solution is in the form

S(n) = A(x1)^n + B(x2)^n where A and B are constants that depends on initial conditions. After substitution of S(2) and S(3) we get,

S(n) = 1.2 * (2)^n - 3 which is exponential.

So, the above function runs with exponential complexity. Can we do better? Yes, the well known technique "Dynamic Programming".

If we observe from S(4), every number is depending on past two numbers only. S(n) = 3*S(n-1) - 2*S(n-2), i.e. we need to store only the past two values to find next number. A three element array will be sufficient. Given below pseudo code,

int totalPossibleCapacitances(int n)

{

    // For efficiency purpose

    // static

    int S[] = {1, 3, 7};

    if(n > 3)

    {

        // Non trivial

        int activeIndex = 0;

        for(int i = 4; i <= n; i++)

        {

            S[activeIndex] = 3*S[ (activeIndex + 2) % 3 ] - 2*S[ (activeIndex + 1) % 3 ];

            activeIndex++;

            activeIndex %= 3;

        }

        if(activeIndex)

            activeIndex--;

        return S[activeIndex];

    }

    else

    {

        // Trivial

        return (n > 0 ? S[n - 1] : -1);

    }

}

Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.

Facebook - Friends Search

3 - May - 2011

When you type a name in friends list, the list automatically displays those filtered names containing typed-in characters. What data structure suites well in such situation? I will provide few links for the same in JavaScript.

Yet to update.

Next Higher Number with Same Number of Set Bits

1 - May - 2011

Given a number say, N - an integer. Find the next larger number with same set (logic 1) number of bits.

For example consider N = 156 which is 10011100 in binary. It has 4 bits set to logic 1. The next immediate number with 4 bits set to logic 1 is 163.

Try out the solution and compare it with my post on Geeksforgeeks. Again I am posting it as a reference to Geeksforgeeks link.

If any clarification needed, post your comments there. They will be helpful to many engineers visiting Geeksforgeeks.

Opaque Pointer and Binary Compatibility

23, April 2011

Binary Compatibility:
When you compile a small application that prints "hello, world", we are implicitly depending on third party libraries usually developed by compiler vendor. If there is bug, or upgraded software from the vendor, can we run our application without recompiling? If yes, we say that the library is binary compatible.


Or in-other words, let us say we supplied a library, and later we come up with great ideas that requires changes in many classes layouts, how can you ship the upgraded libraries without recompiling client code? The solution is Handle/Body idiom (refer Advanced C++ book by Jim Copelin).


Binary compatibility depends on various factors Application Binary Interface definition, source compatibility opaque pointer in code.


Opaque Pointer (Also referred as Handle/Body Idiom, Pimpl Idiom, Cheshire Cat etc.):


To achieve binary compatibility we separate implementation from interface, so easy to say? The interface will have an indirection (pointer or Handle) to implementation (Body). An excellent article on Qt d-pointer (a.k.a. data pointer) is available on Qt developer page and KDE developer page.


Note that the concept of Opaque Pointer or Pointer to Implementation (PIMPL) is used extensively in many software libraries. I came across PIMPL in mobile software, Qt, Boost, many more. I am preparing an article for GeeksforGeeks, soon it will be published.


Also note the concept of q-pointer (pointer back to Handle class) that references the API class for any functionality defined in API class hierarchy.

Layout Engines - WebKit, Gecko, ...

22, April 2011

Layout Engine:

If we want to display an image on screen, how can we do it? We need an entity that paints the screen with the image content. These links helps as digital diary.

The traditional software frameworks like Windows Form, Qt widget, Java Swings etc. provides functionality to render the screen using static information called objects. There are more sophisticated rendering engines that are part of web browsers. The concept of layout engine came from early development of web (Netscape navigator).

Layout engine is the heart of any web browser; examples are WebKit (Chrome, Safari, Konqueror browsers) Gecko (Firefox, Epic browsers), Presto (Opera browser), Trident (Internet Explorer browser) etc. are few examples of well-known layout engines. Almost all of these layout engines are written in advanced C++.

The concept of layout engines is not limited to browsers. One can use it to design applications that needs screen rendering. For example, the outlook mail client, Winamp player display, RealPlayer displays are based on Microsoft propriety Trident engine. Gecko is also used in Thinderbird email client, Google Picasa, and other Internet application suites.

Examples of Webkit layout engine other than browser application can be found in Qt example code. The Qt documentation application is based on Webkit layout engine. It is interesting to imagine the applications of these layout engines. If we are handy with the engine design and few web standards, we can adopt the engine alone for variety of applications.

With the advancement of Cloud Computing Technology, the computer geeks need a thin client application that connects to a server in cloud. Brower based thin clients are going to play major role in future. Chrome design (see Webkit2 also) and development is one example. IE9 also very interesting. Time will answer well.

Script Engine:

Well, the layout engine itself can’t help much. It should be flexible to program for dynamism. The client side scripting languages like JavaScript play a critical role here. But one needs to parse these scripts in the browser at runtime. The parsing entity is called Script Engine. For more details read about Chakra and V8 script engines. Firefox uses optimized SpiderMonkey as script engine. The performance of script engine contributes to overall performance of browser considerably.

For details on Gecko see this link. For details of WebKit see this link. WebKit wiki. The code is free, start exploring their design and implementation. We can see the practical use of C++, design patterns, advanced C++ idioms, etc.