The Saber

Just read this, again, from the Internet. Nice story to share. When things in your life seem almost too much to handle, When 24 hours in a day is not enough, Remember the mayonnaise jar and 2 cups of coffee. A professor stood before his philosophy class And had some items in front of him. When the class began, wordlessly, He picked up a very large and empty mayonnaise jar and proceeded to fill it with golf balls. He then asked the students, if the jar was full. They agreed that it was. The professor then picked up a box of pebbles and poured them into the jar. He shook the jar lightly. The pebbles rolled into the open Areas between the golf balls. He then asked the students again if the jar was full. They agreed it was. The professor next picked up a box of sand and poured it into the jar. Of course, the sand filled up everything else. He asked once more if the jar was full. The students responded with a unanimous 'yes.' The professor then produced two cups of coffee from un

Greatest Common Divisor (GCD for short) is the largest positive integer that divides two numbers. In other words, the greatest common divisor of a  and b  is, as its name suggests, the largest positive integer d  such that d  | a  and d  | b . In this post, we will see how we can calculate GCD efficiently using an algorithm that is known as Eucledian Algorithm . The key thing in this algorithm is division with remainder , which is simply the method of "long division" that you learned in elementary school. Thus if a  and b  are positive integers and if you attempt to divide a  by b , you will get a quotient q  and a reminder r . Below is the theorem used for this algorithm: Let a  and b  be positive integers with a >= b. The following algorithm computes gcd(a,b) in a finite number of steps. (1) Let r 0 = a and r 1 = b (2) Set i = 1 (3) Divide r i-1 by r i to get a quotient q i and remainder r i+1 , r i-1 = r i .q i + r i+1 with 0 <= r i+1 <= r i (4)