Quora

We all have various questions in our mind. They can be about anything and everything.They maybe ranging from neuroscience to philosophy. And most of the times these questions go unanswered, because you either get bored to look for the answers or you just forget them after a while.

Getting our attention to the first part, things sometimes get boring to look for because, for answers to different stuff , we have different sources. We end up wasting a lot of time. So a place where you can discuss everything was unknown to me. I’d never thought the same source where I would get my neuroscience or physics question answered, there would also be philosophical discussions there.

But then, I stumbled upon Quora.com. And I’ve been hooked since. Its a discussion platform for every topic possible. I mean it, its got everything. And its a really interesting community, filled with some smart and some ultra smart people and normal people too. I’ve read stuff on , how the brain works , whats it to get high on a drug, about computer science, a philospohical debate about Science and God and believers,  and lots more. The topics are diverse and the website is very informative. I havent been able to contribute any answers on my own, but in the future Ill contribute somewhere.

Some facts: It started in 2010 , and Quora’s valuation was rumored to be more than $1 billion in February 2011.Adam D’Angelo(CEO, age 27) was ranked number 22 among the smartest people in the technology industry by CNNMoney in 2010.

So if you have not checked it out, please do. You can follow people, and its kinda social too. A pretty smart concept , Quora is.

Post-Rock…. Pink Floyd and music.

My first post about music, and the first part of the title is pretty weird and most probably you havent ever heard of that term. Neither had I, until 2 days back when I heard a song(Do you call music without vocals , a song? I’m not sure) on youtube by the band ‘God Is An Astronaut’. And I pretty much became a fan of the band and I might probably become a fan of the genre, after I check out a few more bands. So, GIAA is a post rock band, and post rock is a sub genre of rock which consists of solely instrumentals. And the music is great. If you’re as much an avid listener as I am, and you prefer listening to entire albums rather than singles , you’ll love it. It just feels surreal. Its not really peaceful in the music sense, like it isnt slow, its got quite a lot of guitars and drumming , but it just seems quite. This is the kinda music, you would prefer to get yourself into a calm and deep thought. Listen to the single “zodiac” just as a check to see if you’d like the music or not.

The second part of the title is pretty much understood by everyone. Pink Floyd, who hasnt heard about them? The Psychedelic / Progressive rockers who need no introduction. I’ve been listening to Floyd since a long time, but only recently did I listen to entire albums of theirs in one go. And it feels amazing. Seriously, listening to an entire concept album is pretty much a completely different experience.(A concept album is an album with a central theme, and all songs are connected to it.)  Dark Side of The Moon has now become my favourite album . Its an album, about various phases of life and about passage of time, greed, money and mental illness . The latter part is dedicated to Syd Barret, the founding member of the band , who was there with them only on the first album. But due to excessive drug use, was not in a a healthy state of mind later on. The album has to be heard paying every bit of attention to its lyrics. They are wonderful, and the music is calm . Its no surprise, that its their biggest hit. The last 2 songs , Brain Damage and Eclipse, dealing with madness(mental illness) are my favourite tracks of the album (and overall too) along with Time.

I checked out The Wall , the concept on this one is social isolation. This ones pretty good too. But its long, and after the first listen , some of the songs get boring . Its got great songs like Floyd’s most famous  “Another Brick”, “Comfortably Numb”, “Hey you” and some more. And they are amazing, but as an album I’d say DSOTM is much shorter, and better.

Music is one of the things in life, which I’m most obsessed about. So I guess , I’d be writing about it a lot more often. I’m not really inclined to any one genre of music, I’m fine with anything good. But my most played music would be The Doors, Pink Floyd, Beatles, Led Zeppelin and recently The Velvet Underground in that order.  I’d have loved music to still be as it was in the times of these bands. Ill write more about them in later posts.

Allocation of memory and Processor Architecture

Yesterday I happened to read a post by a friend where he had mentioned a problem in a certain program.  He had mentioned that his code worked correctly only up till a certain number of digits(it was 5). The compiler he was on was “Turbo C”, which is a very old compiler (to be precise was introduced in 1987) and should not be used by anyone right now.  When I ran the same code on my laptop, on “Microsoft Visual C++ Express 2010(MVCE)”, I noticed that the code worked perfectly for numbers containing 11 digits. So, then I began to wonder what exactly is causing this problem.  After searching for quite a while , and reading up a lot of stuff about how memory allocation is done in C, how information is stored in general on the computer memory, I was able to understand why this was happening.

I knew that the problem he was facing was because of the declaration of his variable of the type “int”, which like all other data types has a certain range of permissible values.  But I was not able to figure out why it was working for a larger range of values in MVCE !

This search led to me knowing the meaning of processor architecture, and how it affects the various applications. The basics of memory allocation lie in the meaning of processor architecture.

In this post , I will try to explain how memory is allotted to different data not just in C, but in general. I will explain what exactly is the meaning of processor architecture.I will not go into too much detail like how a computer stores/fetches memory on/from the different storage devices like caches, RAMs, ROMs , hard disks, etc. For that, I’ll include some links which you can look into, if you are interested. After understanding this, its evident why this problem was occurring.

16,32,64-Bit Processors and Memory Allocation:

All information is stored on the computer in the form of 0’s and 1’s. This, as we know is the binary number system and a digit in this system is called Binary Digit . Thus information is stored in the form of bits. So all letters, symbols and numbers that we type are first converted into a pattern of bits and are then stored in memory as a computer can understand only bits.

So if we enter a number say 18(base 10) , it will be converted to base 2, which would be :

18 = 16 + 2

18 = 1*(2^4) + 1*(2^1)

18 = 1*(2^4) + 0*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)

Thus 18 = 10010

Hence 18, will be stored as 10010. Similarly, the letters and symbols on the keyboard are assigned certain numerical values which are based on the ASCII(American Standard Code for Information Exchange) or UTF schemes. In ASCII, A is assigned the value 65. Thus when “A” is typed on the keyboard, the computer converts 65 to binary and stores its value in memory. All symbols have such values(including space bar).

So how is this binary value stored?

For this we need to understand, what is called a “word size” of a computer. The word size is the computer’s preferred size for moving units of information around; technically it’s the width of your processor’s “registers”, which are the holding areas your processor uses to do arithmetic and logical calculations. Basically “word size” means the size of the maximum binary value the computer is able to store in a single register(register can be visualized as a box where each character/letter/number is stored in its binary form)  . 

This word size depends on your processor. This is what is meant by 16-bit/32-bit / 64-bit processors. The bit part refers to the width of the processors register, how many binary digits it can store . Hence, a 16-bit processor can store values ranging from  00000..(16 0’s) to 11111…(16 1’s). Thus the number of combinations of 0’s and 1’s in this arrangement would be (2^16). This is called the “Dynamic Range” of a system. Thus the highest integer value that can be stored in a register would be 1111…(16 times 1). In base 10 this number would be 

1*(2^15) +1*(2^14) + ……+ 1*(2^1) + 1*(2^0) 

= 1 + 2 + 4 + 8 + 16….. + 2^15 

This sum calculated  by using the GP sum formula gives (2^16) – 1 = 65,535

Hence an int data type would store the maximum number to the base 10 as 65,535. Integer values are stored in “GPR’s – General Purpose Registers”. The floating point limit is much higher as they are stored in “FPR’s – Floating Point Registers”. These work on a different principle , which at this point I haven’t looked into.   

Thus now we know what the max size an integer value can take on a certain processor. We discussed that registers store this value . Registers are a storage unit, they cannot perform any operations on the numbers. For operations, these values are passed to the ALU(Arithmetic Logic Unit). The register is the fastest accessable memory storage for an ALU. But registers store values only temporarily  as their size is limited due to their high cost. Whenever the value is not needed, it is passed on to the RAM. Data is stored on the ram on “addresses” . Addresses are basically numbers. An example would be: Address #1, address #2,etc (In actuality only bits(#0, #1, #10, #11,etc.) will be allowed not #1, #2..). Thus the number of addresses possible on the ram is the number of  integer values possible. Thus on a 32-Bit processor , number of addresses would be 2^32 = 4.3 billion . Each address stores 1 byte of data, thus this means 4.3 Billions bytes = 4 GigaBytes . Hence a 32-bit processor supports a maximum RAM of 4GB.  What this means is it can store 4.3 billion addresses , each address might contain numbers(data) or operations(+, -, *, /)(code).  

This is what defines a computer at the basic level :  Manipulation of data through the use of code, which is stored in the computer’s memory and fetched from the computer’s memory.

The above statement defines all  tasks that a computer does!

Now coming back to the main problem:

Not all application can take advantage of the higher bit processors. Each application is coded for a certain type of processor. The Windows OS is available in 32-bit and 64-bit editions. The latter is only useful for 64-bit processor. A 32-bit OS would treat a 64-bit processor as a 32-bit one , and would not take the extra advantage of the extra “dynamic range” that we saw.

Now, Turbo C  is an application that was built for the 16-bit DOS operating system. Thus it is a 16-bit application. This means that its dynamic range is limited to 2^16 values. Hence the max value of an integer would be 1111…(16 times 1), which in base 10 will be 65,535 as we saw before. Hence the 5 digit limit on integers . 

MVCE, on the other hand is a 32-bit application . Thus while it wont use a 64-bit processor’s full capability, it will give us the “dynamic range” of 2^32 numbers. Max value of integer would be 1111…(32 times 1), which in base 10 would be 2^32 – 1 = 4.3 * 10^8 . Thus the extra number of digits possible in MVCE.

I have only mentioned some basic stuff here, this topic is vast and quite interesting. So here I will quote my references which are really good and informative reads:

Classic.Ars: Understanding the Microprocessor : http://archive.arstechnica.com/paedia/c/cpu/part-1/cpu1-1.html

Classic.Ars: An Introduction to 64-bit Computing and x86-64: http://arstechnica.com/features/2008/09/x86-64/

Bits and bytes , how they work: http://computer.howstuffworks.com/bytes.htm

How does my computer store things in memory? : http://en.tldp.org/HOWTO/Unix-and-Internet-Fundamentals-HOWTO/core-formats.html

How computer memory works : http://www.howstuffworks.com/computer-memory.htm

Clarification : The int values I have given will be possible only if we declare an “unsigned int”, as for an int variable , 1bit is reserved for the number sign. Hence max value of  a normal int would be 2^15 – 1 = 32,767 on 16-bit compiler and 2^31 – 1 for a 32-bit compiler.

The C Diaries: Week 1

After being comfortable in loops, there are a whole lot of problems you can solve in C. I’ve been solving quite a few and here are some I found interesting. For these you need to be comfortable with the basic syntax and loops.

Problem 1:

f(x) be a function that calculates the trailing zeroes of x!(x factorial).  So we need to write a program to :

1. Take input for number of test cases.
2. Enter first case(x).[input]
3. Output f(x).
4. Enter next case(x)
5. Output f(x).

• This goes on till the last test case, and then the program stops.

Example

Sample Input:

6
3
60
100
1024
23456
8735373

Sample Output:

0
14
24
253
5861
2183837

Solution:

The basic idea behind computing number of zeroes in x! is to find the number of times 10 comes in the factorial’s factors. Which basically means checking the number of times 2 and 5 come (as 2*5=10) . So for this the easiest straightforward method is to find the factorial first, then keep on dividing factorial by 10 untill number(mod)10 != 0. We can define a counter for this. But the problem with this is , the limit of x is 10^9 , whose factorial will be extremely large. The datatypes in C wont be able to handle such a large number. Another problem is execution time for such a program will be enormous.

If we think a bit more closely, we see that x = x.(x-1).(x-2)….3.2.1 . So here we can count individual 2’s and 5’s from x, x-1, x-2 … uptill 1.  But we see that the number of 2’s will always exceed number of 5’s in any number. So we will check for only number of 5’s, and this will give us 10’s which will give us zeroes.

To check for 5’s we can first caluculate the number of mutiples of 5 which are less than or equal to that factorial. So lets say x = 100, the multiples are 5,10,15…100.  So there are 100/5 = 20 5’s present. After this we’ll check number of multiples of 25 in the number. These are 25,50,75,100 i.e 100/25 = 4. We have to add these to our total count of 5. 25 is 5^2 , which means it contains two 5’s. But we already have accounted for one 5 in the first step, hence we just add 4 directly to our previous answer. so number of 5’s uptill now : 20 + 4 = 24. Now we consider number of multiples of 5^3=125. But 125 > 100, hence no multiples. Thus our loop must stop when 5^n > x(our number).  Thus we get number of zeroes.

#include<stdio.h>
int main()

{
int t, a, d, c, b;  //t is the number of test cases, a is the input number, d is the counter for total number of 5’s, c is used for incrementing powers of 5, b is used for number of 5’s in one cycle of the loop.
scanf(“%d”, &t); //Enter number of test cases.
for(; t > 0; t–)
{
scanf(“\n%d”, &a); // Enter input number
d = 0 ;
c = 1 ;
for (; c <= a ; )
{
c = c * 5 ;
b = a / c ;
d = d + b ;
}
printf(“%d\n”, d) ; // Output number of 5’s = zero.

}

return 0;
}

Problem 2:

There is a job to fill n vacancies. But number of applications(x) are more than n. So the people are made to stand in a line, and are named serially from 1 to x. Then the odd numbered people are elminated. Then next again odd numbered people are eliminated. In this way the elimination continues. Compute a program (with number of test cases counter) to calculate the position in which a man should be in, so that he’s most probable to get the job.

Example

Input:
2
5
12

Output:
4
8

Solution:

The question says that only even numbered positions are entitled to go ahead. So only the 2nd, 4th, 6th …. positions will go ahead after 1st elimination. Now these terms respectively take the 1st, 2nd, 3rd…  positions. Next elimination 2nd, 4th,6th… positions of this  new series will go ahead(which are respectively 4th, 8th,12th terms of the original series). This will continue untill for a certain input, only 1 number is remaining.

Lets take an example by considering n = 10.

• 1  2  3  4  5  6  7  8  9  10                   Position of the number 8 in the series  =  8                      Total terms = 10
  
•     2       4       6       8       10                  Position of the number 8 in the series  = 8/2 = 4         Total terms = 10/2 = 5 (intdiv)
  
•                4                8                             Position of the number 8 in the series  =  4/2 = 2         Total terms = 5/2 = 2(intdiv)
•                                   8                             Position of the number 8 in the series  = 2/2 = 1           Total terms = 2/2 = 1

As odd cases are being elminated in every round, the successive position of a number is equal to previous position /2 .  The most favourable case will last untill the end, which in this case is 8. Hence the key to this problem seems to be to keep on successively dividing the number of people(n) by 2(n/2) untill n = 1.  Hence we can setup a counter (i = 0) to count the number of times n can be divided by 2 untill n = 1.  And then we can back calculate the number by continuously multiplying by 2, i times, i.e 2^i. 

In this case i = 3. Hence number is equal to 2^3 = 8.

Code:

#include<stdio.h>
#include<math.h>

int main()
{
int t;   //Number of test cases
int i, n, k; // i = counter that describes number of times n can be divided by 2 , n = number of persons(terms), k = final answer
scanf(“%d”, &t);
for(; t > 0 ; t–)
{
scanf(“%d”, &n);
for(i = 0 ; n > 1; i++)
{
n = n / 2;
}
k = pow(2,i);
printf(“%d\n”, k);
}
return 0;
}

The C Diaries: Intro

I’ve been thinking of this for a long time , to have posts about interesting stuff related to programming in C, like good problems, the way to work them out through different algorithms, and probably some basic tutorials explaining some concepts which people find a bit hard at first. So I will be posting a new post(s) weekly, and name them accordingly. The readers could try solving the problem(s) and look at the code later. It could also serve as a kind of database for me, where I would store my progress in learning the language right from the start. And if probably I need some concept later on which I had used before, I could look it up here.

Its been about 1 month or a little more since i first started with C, and so far its been great! I’m now confortable with loops, and planning to start Arrays soon.

“Hello World\n”

My first blog post, and I’m doing this at 2:21 am , when tomorrow I have my Chemistry exam. That would tell you how interested I am in Chemistry.  I have 2 chapters and I have barely gone through the first one,  and I’m planning to do the next one tomorrow morning.

Chemistry has always been one subject I never liked. Not all of chemistry, I do like physical chemistry, atleast some of it. But organic chemistry has always been a mood killer. I just dont get the reason as to why we are supposed to learn stuff(reactions, and various other facts)  without understanding it , just for reproducing it on paper for the exams. And this is not limited to chemistry, I have this opinion about some other subjects too. I mean, whats the purpose of rote learning?

Last year, during my preparation for IIT-JEE, I would say I had a great time preparing Physics and Mathematics and well, some part of Chemistry too. JEE tested your concepts , and it went deep. We solved books which explained every detail possible at our level.  Then, we applied these concepts on problems. Problems which you could get only if you had thoroughly grasped the concepts involved. These required mostly logic and tested ones intelligence quite well. But the exact opposite can be said about the state exam, and CET. Most of the stuff in our state text books were half cooked details. Theorems with no proofs, and direct statements, and then facts. Facts which we are supposed to learn and present on paper in the exam. Numericals based on just substituting the values in a direct formula. What I feel about state exams is , you spend time, doing the same thing again and again, at a point it eventually gets learned. But its hardly understood.  I’m not saying that I was intelligent(hell, I did not even clear JEE, and nor did I score exceptionally well anywhere, but that I attribute to my Chemistry marks, which were pathetic everywhere. I never studied chemistry, and still dont.I cant categorize myself into a certain type, but Ill fit in the category between average and intelligent, if you were to ask people who know me.), and I found this system too easy,  just that I’m against this concept. I’m glad that after our batch, the syllabus has been revised, and the state textbooks have been given an overhaul based on the NCERT books, which are much more complete.

Basically this is my point, why study stuff blindly, when its not going to help you do anything after some days. I dont think someone will be able to remember some formula or reaction after somedays if he has studied them this way. It will be in his mind only till the exam, and then, gone! So this is how it has always been with most of the students, study just to get marks. They have just one thing in mind, score a certain X number of marks. Thats it, nothing else.

I have been strongly against this, and so right now, I’m writing this instead of sleeping or roting local textbooks to get marks in tomorrows exams(Pune University does not even take efforts to change mathematics questions , so anyone whos solved the problems again and again will score, well thats intelligence I guess ) . Because I’m not one of those kinds who wants to score marks this way. Yes sure, I do want marks , but I guess ill get 50%  in tomorrow’s paper. Rather, I’m concentrating on subjects I like , and which are actually going to be with me for the rest of my life. Those would be maths, and computers. I want to be a software engineer, why should I waste my time roting things , that I’m gonna forget anyway? Rather, I would spend time developing my programming skills , algorithms, etc which I will need in my whole career.  Its a big risk. I’ll suffer academically, probably getting 60% or so in my first year. And people say companies look at your FE marks for jobs, and it matters for higher ed too. Maybe it does. I hope I cross that barrier of 60-65%  with this attitude(Im too confident ill score awesomely well in maths, computers and electrical). Ill find out this sem, if I find myself going below 60% Ill have to devote more time to these subjects, even if I hate them. I cannot change the system, though I would like to see it change. Give students flexibility to choose subjects, optional ones, compulsary ones. I would rather have taken Economics and studied it properly , because im genuinely interested in it, and could consider it as a future option sometime in my career, than Chemistry which I sure as hell know, I’m not doing anytime in my life.

I guess this is enough for the first post as its about 3, and I’m too sleepy haha. These are my views about education and learning. Many would disagree, as everyone has different opinions. This is just mine, and you are free to choose yours.