Sunday, November 30, 2008

Sieve of Eratosthenes

This is a famous algorithm, typically used for generating prime numbers from 1 to N.

This algorithm is attributed to Eratosthenes, a Greek Mathematician who lived around 200 B.C. - I have described the algorithm and how it works:

A non-zero, postive integer (natural number) is prime if it has no other factors other than 1 and itself. 1 is neither prime nor composite. And 2 is the only even-prime number. 

So, multiples of 2 cannot be prime (they have 2 as one of their factors) - Similarly, multiples of 3 also cannot be prime. And so on. So, the idea is multiples of a number cannot be prime. 

So, let's consider numbers 1 to 100. 

Create an array of 100 numbers and set them all to 1. 

Let's start from 2 and mark all the multiples of 2 till 100 as non-prime (a.k.a composite). To do this, let's set the value in the array as 0.  [The index should go till 100 / 2]

Then, let's start with 3, and again mark all the multiples of 3 till 100 as non-prime. 

Next you reach 4. But, this is 0 already. So, the multiples of 4 should already be set to 0. (Since all multiples of 4 are already multiples of 2) - So ignore 4. [And ignore multiples of those numbers which are already marked as 0]. Then start with 5.  

So, how far should you go? Some people choose to go till N / 2 (50) - But this is sub-optimal. It is sufficient if we check for all multiples till square root of N. This is because, any factor greater than SQRT(N)  should have a partner that is less than SQRT(N) and hence would have already been marked 0. [Please re-read this para-graph :-) if this sounds confusing]

Now iterate through the array and print all indices where the value is non-zero. Voila! You have generated prime-numbers in O(nloglogn). 

I wrote an implementation in Python. It was quite cool :o)

#!/usr/bin/env python
# Sriram V Iyer
# Implements the eratosthenes sieve program

# Initialize an array for 100(+1) 1s
# +1 is to accomodate the cases 2 * 50, ...
l = [ 1 for i in range( 100+1) ]

# make the multiples as 0
[ l.__setitem__(i*j, 0) for i in range(2,10) for j in range(2,(100/i)+1) if l[i] != 0 ]

# print indices of the list that are still 1
print [ i for i in range(2,100) if l[i] == 1 ]

I had a discussion with Tejaswi (my Beceem colleague) on an equivalent C code.

Btw, I used the C/C++ compiler feature that initializes unitialized elements of a a partially initialized array to 0. This way, I changed the polarity to 0 -> Prime and 1 -> Composite in the C code. [This way, I needn't write code to initialize the array to 0]

    Sieve of Etatosthenes in C/C++
#include "stdio.h"
#include "math.h"

int main()
    int N = 100, i = 0, j = 0;
    int nArray[100+1] = { 0 };

    for( i = 2; i < (sqrt((double)N)); i++ ) {
        if(nArray[i] == 1) continue;
        for( j = 2; j <= (N/i); j += 1 ) 
            nArray[i * j] = 1;
    for( i = 2; i <>
        if(!nArray[i]) printf( "%d ", i );

There is one more possible optimization - If you can initialize nArray[4] = 1 in the code before the first loop, you can start the inner loop from 3 :-)

PS:- Looks like the "<<" in cout can confuse blogger. So, I rewrote the program without using cout, endl :-)

Thursday, November 27, 2008

Sri Krishna

There are regular people, and then there are people who test the limits. 

As for as this Universe is concerned, (with no offense to anyone else), the limit with which Divinity can express in a form, IMHO is Sri Krishna. 

Ishwarah Paramah Krishna:
Satchidananda Vigrah: |
An-Adir Adir Govindah:
Sarva Kaarana Kaaranam ||

Limit of Divinity is Krishna
He is Absolute 'Truth - Consciousness - Bliss' in Form
He is Govinda, One without Beginning or End
He is The Cause of all Causes.

Law of Karma or even the Third Law of Newton says Every Action has a cause. (An action is a reaction to some event)  - When you keep tracing back, everything traces back to the Initial Cause - This Cause is Sri Krishna. 

People who are exposed to Carnatic music will know that when the pitch of the tones increase, it is called 'Aarohanam' and when it decreases, it is 'Ava'rohanam. So when the Unknown Divine, decides to 'Come Down', it is called an 'Avatar'. Avatar is now an English word, which means 'Another form' - But this is not technically the true sense of the word. To take an Avatar means, to step down (or) descend to a Form. 

Sri Krishna was a Purna Avatar - i.e. A complete Avatar. He took His Form with all His Original Glories. When such an Avatar is around, miracles are a daily event. 

I have always wondered how it would feel to be Sri Krishna - Absolute Power with No restraints. 

Whenever Sachin Tendulkar is at the crease, batting, I see every ball with trepidation. I am afraid if he would be out. He is truly a Hero, but fear is there in my mind.

However, if there is one hero whom I can count on to succeed everytime, it should be Sri Krishna. He simply never loses or fails.

Whenever I get time, I'll try to reflect on His Life, His Teachings. They have brought solace to me whenever I was in trouble - It should undoubtedly help you too! 

Sarvam Sri Krishnarpanamastu!


Wednesday, November 26, 2008

Space, time and relativity - Part 3

I really should be sleeping now :-) - But, I thought I'd write this part and then go to sleep. 

I should call this part - 'Illusion of Time' 

I said space and time varies whenever you move. (There are other questions like how do you define 'not moving' :-) - For e.g., I could be sitting in a couch but am moving very fast along with earth! But these questions, I'll save for later or leave it to you for pondering - What is meant by absolute rest?)

How does time vary with speed? Actually, time slows for the person who is traveling. As I have mentioned before, if you have two accurate stop clocks with a huge resolution, and you decide to go around travelling while your friend stands still, when you meet him again, you'll definitely find that you spent less 'time' - i.e., your stop watch will show less time than your friend who is standing! [I find this result so amazing and unbelievable!]

I don't want to get into the math of how time varies when you start moving. (Not that I remember it well :-) ) - For the object / person moving at the speed of light, time stands still. i.e. If you are traveling at light-speed your stopclock will stop ticking while your friend's will be ticking in all glory!

I want you to imagine how it feels when your time stops. Only yours. 

Assume you are going around the earth in light speed - For people and animals on earth, time keeps passing. Time flows from the past, to the present and to the future. For you, time doesn't pass. You keep staring at people being born, living and finally, kicking the Holy Bucket. While these events seem to be separated by time for those people, for you, all these things happen at the same time! You see people's past, present and future all at once. 

For you, every 'event' (if I can call it so) happens in the 'Now' - There is no past nor future for you. Only Presence. How can you not know the past nor the present nor the future, since you are seeing it *ALWAYS*?

You'll seem to know everything - Right from when I'll get my Audi R8 to Sachin Tendulkar's cricket record when he retires in the future. You'll know how I fell into a gutter few days ago and how I felt happy when no one noticed! My (and everyone's) past and future are your Presence. (Present Tense)

You will concur with Mandukya Upanishad when it thunders in its first verse that God is beyond Past, Present and Future. 

As you slow down, time seems to catch up with you. When you think you've traveled for hardly a second, when you land back in earth, it is 29000 AD. Almost 27000 years since you left. You have no friend and there are strange structures in places where your house and your garden stood. 

You really get frustrated and decide to go back to watching things. You decide to become The Witness.

You go back to traveling at light speed. You are One with God. You are God.

-------------------------------- The End ------------------------------

PS:- That is the end of the revelation I got last Friday midnight while thinking about Einstein's Special Theory of relativity. For people who give a sigh of relief, I'll want to tell you that this is the end of the revelation and not my writing :-) - You have more to grieve

As appendix, I'll write more - Esp on How almost entire Hindu and Buddhist Philosophy can fit into this, along with teachings of the current Masters like Eckhart Tolle. If you think only Time is an illusion, I'll be glad to update you that 'Space' is also an Illusion :-) [Appendix - I] - 

After this series, I'll try not to go to Philosophy and stick to Physics and Maths (I'll try my best, but, you know, I can't promise that!)

Btw, I have '0' comments in my blog - THAT'S TRUE! Not a single comment for any of my articles! So, please pass on your esteemed comments :-)  - Otherwise, I'll keep writing!

Monday, November 24, 2008

Space, time and relativity - Part 2

Last time we discussed, Einstein concluded that space and time are not absolute, thus throwing away long held and cherished results of Sir Isaac Newton. 

Light was studied in detail by Maxwell who established the speed of light as 300,000 km/sec. But this speed is with respect to whom (or what)? Whatever the reference point is, light's speed is always same! 

Speed is defined as distance travelled divided by time. Since light's speed is constant irrespective of the speed of the observer, Einstein concluded that notion of time and space is different for different observers!

To explain this further, let us use an example. 

You ask your dear friend to moderate an experiment. You decide to race with light using your super vehicle (let's call it 'Viman') - You get on your vehicle and rush at 100,000 km/s and the light rushes out at 300,000 km/s

Your friend sees light moving 300,000 km every second, while you move 100,000 km every second. So, he thinks you must be seeing light moving at 200,000 km/second. When the race is stopped after some time, your friend checks with you, and you are totally disappointed. Howmuch ever you try, even reaching a speed of 200,000 km /s, light continues at the same 300,000 km/s

This is because, your notion of distance and time is different from the notion of distance and time from the point of view of the stationary observer. 

Since speed of light is constant irrespective of the speed of the observer, the great Einstein concluded that space and time are not fixed but are relative to that of the observer.

The speeds that we move in this world are not comparable to speed of light at all. The fastest rocket, EVER had a top speed of 3km/s. So, in this world, we are not able to observe the difference in  space and time. If you were able to move in speeds that are comparable to speed of light, then you'll be able to see the difference in space and time. 

For e.g., if you take a stop-clock in your hand and rush out at say 1/10 the speed of light. Your friend is standing in the same place and uses a different stop-clock. When you return and check your time, you'll be surprised that your clock shows less time has passed compared to your friend's!!!

Who is correct? The answer is both are! This is because space and time are relative. 

Contrary to popular opinion, Einstein did not want his theory to be called 'Theory of Relativity' - He wanted it to be called 'Theory of Invariance (of space-time)'

I think by the next installment, I'll be able to conclude with my paradox - It is not a paradox really! Just to whet your appetite, I am going to describe how the whole creation stuff would appear to God, and why he is Omniscient and why He *HAS* to travel at light speed only. (Any thing less, he loses his Omniscience!)

It has been a great feeling to imagine how God sees the whole stuff happening. It should be an exhilarating feeling for God! And, I can relate to numerous texts (Mandukya Upanishad, Sri Yoga Vashishta, A New Earth, Tripura Rahasyam etc) - I'll quote from these on Installment 3 or 4 and compare to this theory of relativity. 

It also explains why I like speed :-) - Any point of time, I put all my money in the fastest possible vehicle that I can afford at that time (comfort next!) - Getting to higher speeds, means I am getting closer to God!

People who don't like philosophy please skip the postscript!
(1) I don't mean to be arrogant when I say if God travels at speed less than light, he cannot be Omniscient. It is just a side effect of the conditions that I have spoken about. Someone said 'God Defined is God Defiled' - God cannot be defined by words, thoughts, pictures or any other human medium of communication. 
(2) People who want to get closer to God are advised to buy their own R-15 and not borrow mine. :-) [By meaning closer to God does not mean or imply getting closer to Mr. Yama Dharmaraj :-D

Friday, November 21, 2008

Space, time and relativity - Part 1

I should have probably called it space-time and relativity, but, even 'Space, time and relativity' should be ok :-) 

For people who are new to the subject, I'd like to give a small intro before before we discuss the details...

According to Sir Isaac Newton, space is absolute. i.e., irrespective of the observer, space exists. 

To make this statement more clear, consider two places - Chennai and Bangalore.  Also consider the following dialog

Dialog #1
Me: What is the distance between Chennai and Bangalore?
Newton: 350 kms
Me: Thanks a ton.

Life becomes more complicated with Einstein...

Dialog #2
Me: What is the distance between Chennai and Bangalore?
Einstein: For whom?
Me: Holy crap!

In a Newtonian world, space is absolute. For Newton, distance between Chennai and Bangalore is same irrespective of who measures it. 

It is not so for Einstein. For him, Space and Time are relative. For an observer who is travelling at a good speed, the distance will appear less! The difference in the distance observed between a stationary and mobile observer will be more as one of the observers travels closer to speed of light (300,000 kms per sec)

Einstein published this result in 'Special Theory of Relativity'. This was a direct inference of his result that ‘Speed of light is constant irrespective of the speed of the observer’ 

For people who are not surprised by my previous paragraph, I would like to explain it further. 

Consider that a train is moving towards you at 50 kms/hour. The first thing you should do is to get off the track (he he)

Joke apart, consider you are feeling suicidal (which you shouldn’t) and standing on the track with train approaching you at 50 kmph. You’ll see that the train is approaching you at 50 kmph. 

If you are anxious to meet Mr. Yama Dharmaraj, you can choose to run towards the train, at say 10 kmph (the best I can do :-) ), the train will appear to come to you at 60 kmph. 

Suppose a dog starts chasing you, and you start running away from the train at 20 kmph, it will appear that the train is approaching you at  30 kmph. 

So far so good. Now, since you understand this, you got happy and jumped off the track and the dog got ran over by the train. Lets get back to Physics.

Now, you decide to chase light. Mr. Light Bheem is traveling at 300,000 km/sec. You decide to get on your super vehicle, and chase it at 100,000 km/sec [The fastest rocket on earth travels at less than 3 km/sec - You can now guess how fast light is!]

Since you are chasing Mr. Light Bheem at 100,000 km/sec, you expect his speed to be 200,000 km/sec (300,000 – 100,000). When you measure the speed of Mr. Light Bheem, you find that his speed is still 300,000 km/sec!!!! 

You get frustrated and increase your speed to 200,000 km/sec. And then you measure light’s speed – It is still 300,000 km/sec. You finally decide to give up and go back to railway track. You measure the speed for light for one last time after stopping your super vehicle. It is still 300,000 km/sec.

So, whatever the speed of the observer might be, the speed of light is Holy Constant. 

This observation led Einstein to derive that space and time are not absolute. 

I’ll explain more on Einstein’s conclusion next time… I have to step out now. 

Comments are welcome!