Calculating the value of pi

18, September, 2010


Pi! What is π? How to prove its value is approximately 3.1415?

"Pi" is one of the fascinating numbers in mathematics history. I have seen some poems in Sanskrit whose character sequence gives the value of phi. It was great Indian heritage. Here I am providing my own proof.
There are more than 50 solutions found to prove phi value. They range from simple geometrical based proof to advanced Fourier series based proofs. Given below is one way, which I thought during my engineering (of-course that day the class was boring). Note that phi is irrational number. After our proof we can conclude it.

Note that when we increase the diameter of circle its Area and Perimeter will also increase. It is obvious by means of visual observation. What interests to a mathematician is, how much is the increase ratio? Is it constant?

How can we devise an algorithm or method that can be understood by school kid (may be 5^th standard)?

We trace phi value in two parts. PART 1 deals with calculating area of circle with infinitesimal pieces of radii. PART 2 deals with calculating area of circle using Pythagoras Theorem.

PART - I

The base for our proof is Pythagoras Theorem. The sum of areas of squares formed by adjacent sides to the right angle is equal to the square formed by opposite side.

Most of us know that Area of circle is A = πr², and Perimeter P = 2πr. Or we can write them in the following way.

Π = 2πr/2r = 2πr/D = P/D where D is diameter of circle. [Note it as equation 1]

It means, the ratio of perimeter of circle to its diameter is constant and it is π. I know it is poor derivation, after all we are trying for value of π. How much is its value? Can we make use of area of circle to find π value? Yes.

How can we calculate area of circle? Have a look at the following diagram.

You might have guessed. Just divide the circle into 4 parts as in Figure 1, and join them. We will not get perfect rectangle share. Try cutting the circle into further smaller pieces, and join them.

Now, cut the circle into multiple pieces of infinitesimal width and length will obviously be its radius. If we join all these pieces, we will get the rectangle as shown in the picture.

From the diagram we can calculate the circle area as A = Pr/2. [Note this as equation 2]

PART - II

We need bit patience. Consider upper right part of the circle in the Figure 1. We can find area of this piece using Pythagoras Theorem.

1. The area of rectangle triangle OAB can be easily found which is ½ r * r.
2. We left with area of the half convex formed by chord AB and perimeter of the circle. How can we calculate it? As usual, recurs.
3. Draw a perpendicular OC on to AB from the origin O. Join the lines AC and BC (those in red color). By symmetry, area of the part ADC and BDC are same.
4. In-order to find area of ADC and BDC, we need length of DC. We can easily calculate the lengths OD and DC. Also note that OD + OC = radius, and AD = DB = AB/2 by symmetry. We know AB from Pythagoras which is r² + r². From the figure we know that OD² + BD² = r² (Using trigonometry also we can find OD, try it).
5. After this step we can calculate OD and hence DC which is r * (SQRT(2)-1)/SQRT(2). AD and DB also known [r/SQRT(2)]. We need to repeat the above approach for pieces, ADC over the arc of circle and BDC over the arc of circle. After this step we will left with DC = r * (SQRT(2)-1)/SQRT(2), AD = r/SQRT(2), which gives us area of ∆ADC = ∆BDC = r²*(SQRT(2) - 1)/4.
6. Again draw perpendiculars on to AC and CB.
7. At this stage the process repeats from step 3.

We will stop after sufficient accuracy. By now, we can understand why phi is irrational, never ending and non repeating fraction (it includes lots of irrational numbers in calculation).

The area of the upper right part AOB of circle can be integrated over these small areas found by brute force method.

There will be one triangle ∆AOB that forms first term in the series is T1 = ½ r * r.

There will be two triangles (∆ADC and ∆BDC) that will form the second term (T2 = r²/sqrt(8)) in the series.

There will be four triangles that will form the third term (T3) in the series.

There will be eight triangles that will form the third term (T4) in the series.

So, area of the upper right part of circle is given by

Area of Upper Right = T1 + 2 x T2 + 4 x T3 + 8 * T4 + …

The above series leaves only ¼ of the area of actual circle. The area of circle can be found by multiplying it with 4.

Area of circle = 4 x [Area of Upper Right]

= 4 x [T1 + 2 x T2 + 4 x T3 + 8 * T4 + …]

= 4 x [½ r² + 2 x r²*(SQRT(2) - 1)/4 + 4 x T3 + 8 * T4 + …]

= 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … [Note this as equation 3]

From equations 2 and 3, we can conclude these two areas must be same. Therefore

Pr/2 = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

Pr/2r² = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

P/2r = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

P/D = 2 + 2 x (SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

Π = 2 + 0.8284 + 16 x T3 + 32 * T4 + … ---> from equation 1

Which leaves a fraction about 3.1415… when we include few more terms. Note that the actual value is never ending and non-repeating number.

Lengthy but interesting.

Qt (Cute) - An Advanced C++ Framework

18, September, 2010.

Qt - pronounced as cute, a cross platform C++ framework

I am working on new C++ framework called Qt. It is designed by a company called TrollTech and later acquired by Nokia. Qt is an open source advanced C++ framework targeting at multiple platforms including Embedded gadgets.

I am working with Qt from past few months and enjoying the work. You too, can try it.

Another cross platform advanced C++ framework under development is Boost. We can see the way C++ can be used for upcoming computing needs.

Hexadecimal string to Decimal integer conversion

17, Sep, 2010.
Question:
Given a string that contains hexadecimal number, write a function htoi() that returns the equivalent integer.

// Here is one function

int getValue(char const* hexString, int const radix)

{

    int         loopIndex;      // Loop iterator

    int         signFlag = 1;   // Keeps track of sign

    signed int  retValue = 0;   // Final value

    int         currentDigit;   // Current digit under process

    int         len = strlen(hexString);    // Lenght of string

    // Check for sign

    if(hexString[0] == '-')

    {

        // Advance the base

        hexString++;

        // Remove '-' from count

        len--;

        // Sing is -ve

        signFlag = -1;

    }

    // Iterate from left to right

    // Accumulate the weight of each digit upon occurance of next digit

    for(loopIndex = 0; loopIndex < len; loopIndex++)

    {

        currentDigit = toupper(hexString[loopIndex]) - ASCII_ZERO;

        // Is the digit between A through F?

        if(currentDigit > 9)

        {

            // Adjust numerical value

            currentDigit -= (ASCII_A - '9');

        }

        // Based on Horner's principle

        retValue = retValue * radix + currentDigit;

    }

    // Flip the sign, if required

    retValue *= signFlag;

    // This is the final value

    return retValue;

}
Examples:


getValue("1011", 2);    // Binary string to integer
getValue("12345", 10);  // Decimal string to integer
getValue("ABCDE", 16);  // Hexadecimal string to integer


Error handling is omitted.

1. Overflow and underflow (if string contains more than 10 characters on 32 bit machines, i.e. length = [32*log(2) + 1] digits in general, which is the characteristic).

2. Invalid String (containing unexpected characters).

3. String not terminated with NUL character.

4. String is NULL.

5. What if a kernel space buffer is passed as hex string?

6. Is it reentrant?

7. Who will be the consumers of the function, and possible ways of misusing it?

8. What changes are required if wide character buffer (Unicode) is passed (portability issue).

9. Any optimizations without compromising on the functionality.

Find the total number of squares and rectangles in an NxN chessboard.

12th, September, 2010

Asked here http://geeksforgeeks.org/forum/topic/interview-question-for-software-engineerdeveloper-about-puzzle-4#post-7819

Solution:

For example, consider 8 X 8 chess board.

Note that we need 9 integers to represent one side (say x-axis) of the chess board. Similarly we need 9 integers on other side (say y-axis).

Rectangles:

Every square is a rectangle. A rectangle requires two co-ordinates (horizontal line) on x-axis and two co-ordinates (vertical line) on y-axis. The horizontal line needs two integers out of these 9 integers on x-axis. Similarly the vertical line needs two integers out of 9 on the y-axis. Hence we can draw the horizontal line in 9C2 different ways, and same with vertical line. Overall we can have (9C2)*(9C2) = (36)*(36) = 1296 rectangles on the chess board.

Squares:

There is simple approach to figure out squares.

Draw one simple rectangle with consecutive integers. We can have only one rectangle.

Take any two consecutive integers on x and y axis, there will be 1 (outer) + 4 (individual) squares.

Take any three consecutive integers on x and y axis, there will be 1 (outer) + 4 (dual) + 9 (individual) squares.

Take any four consecutive integers on x and y axis, there will be 1 (outer) + 4 (triple) + 9 (dual) + 16 (individual) squares.

Note that there is a pattern. So, for 8 consecutive integers on x and y axis there will be

1 + 4 + 9 + ... + 49 + 64

= n(n+1)(2n+1)/6 (where n = 8)

= 204 Squares.

I think there is simple approach using binomial co-efficients. Try it.

You can generalize the approach for N X N chess board.

Find right-most set bit in an integer

September 11, 2010

I recently posted one the following solution. Question is, given an integer (other than 0) find right most set bit in that integer.

You can see the post in the following link

http://geeksforgeeks.org/?p=555&cpage=1#comment-2174

The solution is given below,

// Position of rightmost set bit

An order of log(X) algorithm. We can conclude from 2's complement form that "a number can be converted to 2’s complement form by complementing each bit from right most set bit". For example, -7 can be obtained in the following way (assuming 8 bit size)

7  = 00000111

-7 = 11111001

8  = 00001000

-8 = 11111000

5  = 00000101

-5 = 11111011

If we perform ANDing between x and -x we left with right most set bit. All this takes O(1) time. Now use binary search [ O(log(x)) ] to figure out which bit is set. Given below is code.

int getPosition(unsigned x)

{

    // ASSUMPTION: x will not be zero

    // left, right and mid position

    int l = 0, r = 33, mid = 0;

    // temp value

    unsigned temp;

    // Iterate till we find the bit position

    while(l < r)

    {

        // ((r - l) >> 1) + l - Is more effective??

        mid = (l + r) >> 1;

        // Set the most possible significant bit

        temp = (1 << (mid - 1));

        if(temp == x)

        {

            break;

        }

        else if(temp < x)

        {

            // Bit is in the higher half

            l = mid;

        }

        else

        {

            // Bit is in the lower half

            r = mid;

        }

    }

    // Return mid itself if bits

    // are positioned from 1 to 32

    return (mid-1);

}

int getRightMostSetBit(unsigned x)

{

    // Return 0 if x is zero

    int position = 0;

    // Avoid multiple return statements

    if(x != 0)

    {

        // Make the integer passes as least power of 2

        // Call the position locator

        position = getPosition(x & -(signed)x);

    }

    return position;

}

If you find any errors, please let me know.

Counting bits in an integer

September 11^th, 2010

I have simple approach as it was mentioned in the bit reversal algorithm. We can add the adjacent bits in each one bit position, two bit positions, four bit positions, etc… until we reach the number of bits in integer. I am providing pseudo code,

1. Add bits in positions (0, 1), (2, 3) so on (30, 31)

2. Add bits in positions (01, 23), (45, 67) so on (28 29, 30 31)

3. Add bits in positions (0123, 4567).....

4. Add bits in positions (01234567, 8 9 10 11 12 13 14 15)

5. Add the bits in first half and second half of the integer.

The algorithm takes log(N) steps to count the bits in integer.

An example will clarify it more clearly

Let us take 0x12345678, the corresponding binary representation can be written easily (it has 13 set bits)

00010010001101000101011001111000

00 01 00 10 00 11 01 00 01 01 01 10 01 11 10 00

After step 1 we get

00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00

After step 2 we get

00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00

0001 0001 0010 0001 0010 0010 0011 0001

After step 3 we get

0001 0001 0010 0001 0010 0010 0011 0001

00000010 00000011 00000100 00000100

After step 4 we get

00000010 00000011 00000100 00000100

0000000000000101 0000000000001000

After step 5 we get

0000000000000101 0000000000001000

00000000000000000000000000001101 – (13) Which is required result

The algorithm can be implemented using shifts and addition operation. There are multiple algorithms out there to compute number of set bits in an integer. For few of such algorithms see the following link

http://geeksforgeeks.org/?p=1176

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Depending on context we can choose right algorithm.