Sieve of Eratosthenes

This is a simple and ancient algorithm for finding all prime numbers up to a given number, say n. Although it is a very, very old algorithm, it works fairly efficiently for numbers under 10 million. As the name suggests, this algorithm was created by a Greek mathematician by the name of Eratosthenes…

The following is the algorithm he suggested:

Simply make a list of consecutive numbers from 2 up to the number n. Now, take each number from the front of the list (first 2, then 3 and so on) and remove the multiples of each of these numbers from the rest of the list starting from the square of the number.  At the end of this procedure, all remaining numbers are prime…

Therefore, in essence, we keep removing elements over and over using one number at a time to choose the numbers that must be removed.

Here’s a working version of the algorithm. Say we want all prime numbers from 1 to 20.

Step 1: Make a list of all numbers from 2 to 20

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Step 2: Take the first number i.e. 2 and remove all its multiples from the list starting from 4.

2  3  5  7  9  11  13  15  17  19

Step 2: Take the next number (2nd number) i.e. 3 and remove all its multiples from the list starting from 9

2  3  5  7  11  13  17  19

Step 3: Take the next number (3rd number) i.e. 5 and remove all its multiples from the list starting from 25. But, since 25 is greater than our n = 20, the process stops at this step.

Therefore, our final list of prime numbers is:

2  3  5  7  11  13  17  19

And yay! that’s the right answer… and computationally easy and efficient!

Squaring Numbers Close to 100

So, here’s another math trick and this one may be a little less intuitive to follow. It’s about squaring numbers close to 100 without that piece of machine called the calculator.

Example: Squaring 108 i.e. Calculating (108) * (108)

Now, we know that 108 differs from 100 by a +8. We make use of this and add this 8 to the number we have.

108+8 = 116

Now, we leave 116 as the left most digits of the answer and take the square of just 8. We get  8*8 = 64.

Therefore, our answer is : 11664

And voila, your calculator agrees!

Damn, I love math tricks.

Lavenshtein Distance – Distance Between Words

I recently had a conversation with a friend about the distance between words. Yes, it sounds absurd but it is a rather interesting concept and ended up being my “CS fact of the day”

Lavenshtein Distance is the most commonly used technique to determine the distance between two words and it basically measures the minimum number of changes required to transform one word into the other.It can be used to check for possible spelling errors etc. by minimizing the distance.

Let’s say word A is ‘meteor’ and word B is ‘enter’. There isn’t any spelling mistake here per se, but we can still measure the distance.

Transforming A into B involves identifying the minimum number of changes. In this case, it is LD(A,B) = 3.

This is because we can make the following changes:

meteor
eteor (delete m)
enteor (insert n)
enter (delete o)

There are obviously infinite number of sequences that will go from A to B, but the objective here is to calculate the minimum one (sort of like the linear distance concept because linear distance is the shortest)

Interestingly enough, this LD (or Lavenshtein Distance) happens to form a metric space. That is, if LD(A, B) = x and LD(B, C) = y, then LD(A, C) = z and (x+y) >= z. This is basically the triangle inequality. So, it enables you to build spacial partitioning trees.

Pretty neat, huh?

So, there’s more than a difference between words… there is a distance… 😀

Squaring of Numbers Close to 100

So, here’s just another math trick:

Suppose, we have a number like 106 and we want to square it. So,we’re taking 100 as the number we compare to and 106 = 100 + (6)

Now, we add 6 to 106. This gets us 106+6 = 112

Now, we keep 112 as the leftmost three digits of the answer.
We square 6 and get 6*6 = 36.

36 will be the right most 2 digits of the answer.

Therefore, our answer is 11236.

Now, we’ll try the same thing with a number less than 100. Let’s take 92 for an example.

100 + (-8) = 92  So, the difference from 100 is that  of (-8). So this is the number we will play with.

We add -8 to 92 : 92 + (-8) = 84. Now, we take these as the left most digits and then add the square of (-8) as the right more TWO digits.

Therefore, the answer is 8464

This is applicable for numbers much greater than 110 as well. But, with a difference.

Suppose we take 111 and try to square it. We will need to add 11 to it first and we get 122.

For the next step when we square 11, we get 121. But, we can only take upto 2 right-most digits. So:

122 and 121 combined together when we can only take 2 digits from 121 gives us:

122 + 1 (from the 121 carrying over) and add the 21 to the right.  = 12321

Squaring Numbers Ending With 5

Here’s a really easy way to calculate the squares of numbers ending with a 5… suppose we are taking the square of 85:

85 * 85 = 7225

Now, the easiest way of doing this is by taking the part of the number without the last “5” in it.. which in this example would be simply 8. Now, multiply 8 by the next number, which is 9. We get a 72… just add a 25 at the end of it and you get the answer: 7225

Therefore, as a general equation we have:

105 * 105 = (10 * 11) with a 25 at the end = 11025