I’ve never really appreciated homework assignments that have page after page of background information that I have no concern in whatsoever. I always think them as a way professors use to intimidate students and show off their knowledge. Until a few days ago, when I was scratching my head and looking for something on scientific computing to post on our class blog, I came across with one of my previous homework assignments from CS 113.  

In the assignment, we are required to compute the value of pi. As written by my professor in the handout, many pi-computing algorithms have been developed so far, but the one I need to implement is the one discovered by Ramanujan in the early 20^th century:

The algorithm goes:

1. Let x = 0.5, y = root(2), and i = 1.

2. Compute (1-root(1-y^2))/(1+root(1-y^2)) , and store the result in y.

3. Compute x*(1 + y)^2-2^i * y, and store the result in x.

4. Let p = 1/x and i = i + 1.

5. Goto step 2.

As iteration progresses, p converges to pi. Here is the C program that implements the algorithm:

int main(){double x=0, y=0, p;y = sqrt(0.5); x = 0.5;for(int i=1; i<20; i++){y = (1-sqrt(1-y*y)) / (1 + sqrt(1-y*y));x = (pow((1+y),2)*x)-pow(2, i)*y;p = 1.0/x;printf(”As of iteration %d, pi= %lfn”, i, p);}return 0;

}

Unfortunately, the most precise floating-point type in C is double, which only has about 15 decimal digits on most machines. So the provided C codes above can only give 13 to 14 digits after the decimal point. So we won’t be able to get a more precise result no matter how many iterations we run.

Then in the handout, the professor proposes an alternative solution, which is to store numbers as strings. For example, instead of storing the number 322 in a variable of type double, one could store it as the string “322”. The pro of this representation is that we can store as many digits as we want in the string. And the limitation of this representation is the amount of memory on a machine.

How do we do arithmetic operations on strings, you may ask? To implement addition, subtraction, multiplication, and long division, we can use the techniques taught in grade school. For example, to add two numbers, you need to process the strings from right-to-left, computing the sum of each column and add carry to the next column.

To implement square root function, one could use Babylonian method which is:

1. Initialize x to 1.0.

2. Let y equal ½ *(x+n/x)

3. If x = y stop; otherwise let x equal y and then goto step 2.

If you are interested in coding the above algorithm, just throw you one fact, the solution provided by my CS 113 professor has about 500 lines of C codes. So only do it when you are really free.

Here is the end of the technical part of my post. Now I’d like to reflect a few words on handouts with long background information. From now on, maybe I should appreciate this type of handouts more and give up my cynical view on professors who give long handouts. The next time before I leave any bloody scratching marks on my head, maybe I’ll first think through the long assignment sheets I’ve read in the past.

Reference:

1.Part 2 of the attached assignment is what I am talking about:

CS 113 Assignment 3

http://www.cs.cornell.edu/courses/cs113/2008sp/a3.pdf

2.Want to learn more about Babylonian method? go to:

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

3.Want to know more about pi? Go to:

http://en.wikipedia.org/wiki/Pi

4.The following forum has an interesting discussion on floating-point type in C++

http://www.codeguru.com/forum/showthread.php?t=323835