|This forum is proudly powered by Scientific Linux 6||SL website Download SL Help Search Members|
|Welcome Guest ( Log In | Register )||Resend Validation Email|
Posted: Jun 28 2011, 03:28 PM
SLF IRC Team
Member No.: 180
Joined: 15-May 11
This assumes you have read Lesson 1, if not please go back and read lesson 1.
Now that you have a good grasp of maths and data structures its time to extend that knowledge to a bit how computers work and a little more python hopefully this will help you with understand why programming needs different data structures especially between for example int's and floats. Lets get stuck in!
Binary & Storing
First off, Binary! I'm sure you have heard of this but if not don't fear! I shall explain what it is, how to use it and why. Some of this isn't directly to do with python some of this is computer science theory but its to aid your understand concepts which underpin python and programming.
Binary is a counting system, it uses 1's and 0's only. This is called base 2. We are use to something called base 10 which means its got 10 different states 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 .. cearful, not 10 because 10 is 1 + 0. 0 - 9 is base 10 and I'm sure that seems easy counting, we learnt it when we were a toddler right? super well hopefully you'll be able to catch on with this binary malarkey!
As I said binary only uses 0 and 1 and its a very basic idea and it works exactly the same as normal (base 10) counting. In base 10 the lowest number is 0 and the highest number without combing them is 9 (because 10 is 1 & 0). Okay so why is this important? Well as you know 09 is the same as 9, but the way we get 10 is we add 1 to the column to the left and then change the rest of the numbers to 0. so 9 goes to 10 and 99 goes to 100. In binary this happens too
0 = 0 in binary
1 = 1 in binary
10 = 2 in binary
Woah okay so how did we get there. Since binary only has 0 and 1 when you get to 1 or 01 (the same number i just put a 0 in-front of it) you have to add 1 to the number to the right and make the rest of the numbers go to 0 so 01 goes to 10, then as you would to get from 10 to 11 you do the same again you go tho the left and if you are less than 9 you add 1 right? so 10 becomes 11 and 12 and so on until you get to 19 and because its 9 you go to the right and add one (unless thats 9 and then you go to the right of that and add one).
so in binary 4 is:
Can you guess what 5 is ?
so lets go through it again we had 11 we wanted to add 1 so we look at the very right of it and we see 1 so its the highest i can we so we change it to 0 and try and add it to the next position thats also 1 so we make that 0 and add it to the next remember that 11 is also 011 so thats adding 1 to 0 making it 100.
0 = 0
1 = 1
10 = 2
11 = 3
100 = 4
101 = 5
110 = 6
111 = 7
1000 = 8
1001 = 9
1010 = 10
1011 = 11
1100 = 12
1101 = 13
1110 = 14
1111 = 15
And so on, hopefully you can see how we do that relating it to our own counting scheme which we are comfortable with.
Now to work out what a binary number is in base 10 we use what are called the "Headings" we used these in base 10 too when we learnt to count.. In base 10 when we got use to big numbers, we started with columns the units column was the first then tenths then hundredths, etc... so
1 in the hundredths column
7 in the tens column
2 in the units column
meaning 100 + 70 + 2 = 172
Binary also has these Headings except they aren't units, tens, hundreds, etc.. they double so the first column is the 1's column, second 2's column, third is 4ths column, forth is 8th column and so on soon you get very big numbers and on your hand which is 10 you can count up to 1023 from 0.
1111111111 = 1023
okay so how can say that? well we use the columns thing lets lay out the 10 columns:
512, 256, 128, 64, 32, 16, 8, 4, 2, 1
1 1 1 1 1 1 1 1 1 1
so you add up all those column headings like i did with the base 10 172 you do it here:
512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1023
remember i got those headings by doubling them. You might be wondering hold on a second why am i writing them so the big number is first, its how our base 10 numbers read remember the number which has the most magnitude is at the far left and they decrease from left to right.
Okay so we got that sorted. This is also how computers store integers, notice integers because with just 1's how can you store decimals right? this is why its so important to have this difference so the computer knows how to store it it needs to make the most out of these bit pattens. Now hold on a second bit pattens? Yep most of you will have heard of bits and bytes and kilobytes and megabytes, gigabytes maybe even terabytes well a bit is ether 1 or 0 its just 1 number in base 2 (binary). a byte is 8...
8 bits = byte
1024 bits = kilobyte
8388608 bits = megabyte
8589934592 bits = gigabyte
8796093022208 bits = terabyte
thats a lot of bits! This does bring 1 very important point though, in all of these there is a finite number you can represent, for example if i have 4 bits
1111 = 15
15 is the highest possible number i can represent using those 4 bits so if integers used only 4 bits they couldn't only store between 0 and 15 now obviously computers don't use 4 bits infact python uses 64 bits (1 is reserved for something special which we will get onto) so that leaves the number up to:
we can represent, this is huge but okay so lets say we are working with huge numbers and that simply isn't big enough then what do we do? Well there is another sneeky data type called a long. This isn't a set length in python it simply uses the number of bytes it has to to represent the number you wish until you run out of RAM (which don't worry, won't happen). This datatype we can see when we do:
Okay so lets figure out what this special bit is then i was referring to above, why can't we use the 64th bit? Well if we do 5 - 6 we want it to give -1 don't we, because it is? Lets check it does
So that's fantastic but hold on a second we know binary, how do you represent -1 the lowest we can go is 0 isn't it? Well in pure binary yes however computers found a clever way to represent negative numbers using only 0's and 1's.
The people when they hit this problem years ago thought okay lets say the most left bit is a sign bit if its 1 its negative if its 0 its positive. simple so -1 you just need to know what 1 is:
and then you just put a 1 at the far left
Okay! But if i want to add -1 to 2
we want it to work, now we haven't covered adding binary yet but it works the same as normal adding, when you take a value you add it to the lower one and the result if it can't fit in the current column is carried and that is applied until it can fit... So! lets try adding -3 with 7:
Okay you see what we did there we 1 + 1 = 0 so we put that in the column, 1 + 1 + 1= 3 but we don't have 3 so we put a 1 in that column so we have 2 left, that must be carried forward, since there is the carried 1 and the existing 1... 1 + 1 = 2 we don't have 2 so it must be carried so we put a 1 there, we have the carried 1 so we add it to the current 1... 1 + 1 = 2 which again we don't have so we put 0 and the 1 is carried now since there isn't a column we make one and its then 1 + 0 = 1 so we put a 1 in the last column. This because the far left bit is a 1 means its negative, the rest of the number is 0010 which is really 10 which we know to be 2 now so -2 now is that the answer:
1011 = -3
0111 = 7
-3 + 7 = 4
So our answer of -2 is wrong!. Good that we can have negative numbers but the reason we have numbers is to do maths on them and we can't do that with this so we need a better solution, lucky a very clever one came up called 2s complement. This is used in computers to this day. the most significant bit is reserved but not to say if the number is negative or positive (the sign) it goes back to the headers earlier, its the negative of the header so if we had
normally the headers would be 8, 4, 2, 1 in 2s complement they would be -8, 4, 2, 1 so lets try -3 + 7 again
-3 is 1101
7 is 0111
okay so lets do the same maths we did above
Now instead of adding this extra column for the 1's (as there is the carry for the last column) you simply ignore it. so how did i do this
1 + 1 = 2 so i carry and place a 0 in that column
1 + 1 = 2 so i carry and place a 0 in that column (1 is from the carry)
1 + 1 + 1 = 3 so i carry 2 and place a 1 in that column (1 is from the carry)
1 + 1 = 2 so i would carry however i have run out of bits so i ignore that and place a 0 in the column like i would
0100 is 4
-3 + 7 = 4 so it works!
This is quite complicated i understand and its not the end of the world if you don't get this as you don't really use it in python but its good to know how integers both positive and negative are stored and also why integers miss the far left bit out and ergo what size integers are.
Now we have gone that we have even more advanced binary to represent these decimal numbers or what python calls floats. Now so far you know we can represent integers be them negative and positive and you can do this with floats however you need a way of representing the other bit to the numbers, there are two ways and both work with maths and both have their advantages and disadvantages, since one is quite complicated I'm going to put that as an Extra at the bottom so if you're an extra smart cookie you might want to look there but i'll put the basic one here:
This is called fixed point (the other is called floating point hence float). This is where numbers are formatted so there are so many bits allocated to representing the number to the left of the . so in the example 9.4 it would the 9 portion and then certain amount dedicated to the 4 how it works is about the headers again.
Lets assume we have the number 2.5 to make it easy and we use 4 bits for each side of the point so:
Okay so thats the representation but why? Well we should know by now 0010 is 10 and 10 is 2 now the other bit have headers like all binary numbers except these headers are fractions so the first is 1/2, 1/4/, 1/8, 1/16 etc... why did i put a 1 in the first one after the point, well 1/2 = 0.5 and i want to represent .5 so thats it! if i wanted to represent .75 its 1/2 + 1/4 and we can check this in python
so for example 1.75 is:
Now in the computer it doesn't store the . in the number it just knows how many bits are used for each portion of the number.
A cool thing you can do in python. If you want to convert numbers into pure binary (no negative numbers or decimal) you can use
the start 0b just mean its binary .. also if you wish to convert binary to base 10 like want to check 1111111111 is 1023 like i said before you can you do you do 0b then the number so 0b10 is 2
This is brilliant eh !
Now remember we were doing maths before with + and - you can also use << and >> to do whats called a bitwise shift this is just technical jargen for ether moving every bit 1 to the right or 1 to the left ether doubling the number or halving it so for example
This is simply moving the thing to the left of the << or >> the number of places as the number after the >> and << so i had 1 there so it shifted it 1 position but i could shift it 2 so doubling it and then doubling it again its
This is because it doubles 4 to 8 and then 8 doubled is 16, lets see how this works with bits:
00100 = 4
01000 = 8
10000 = 16
this is pure binary not dealing with negative numbers or floats.
Okay so what are variables? Well they are things which variable and these are one of the main things used in programming! Why you might think? well we do maths and we can represent numbers and strings but we might want to store these and use them later or store them while we modify them, who knows but there are so many things we can do with them.
So imagine a box in this box i can put a integer, float, string, bool or long. Now i want to maybe put 7 in this box. Okay so 7's now in the box, now i can look in the box and see 7 or i can take 7 out, add 1 and put the answer back in (8)
i can leave 7 in there and do some other maths and then look back at 7 after. but 7 in there. Well this box is like a variable, its got a value in and it will stay there until you change it, you can look at it and things. In python you choose a variable name and then you perform whats called an Assignment this is a technical term for putting something in a box so:
Now hold on a second there, i had my box i put 7 in it, i added one, it told me it was 8 and then i looked in my box but 7 was still there what gives? well what you did is you put 7 in a the box, you then looked in the box and saw 7 and then added 1 to 7 and got 8 but you never put 8 in the box 7 is still there, now you need to use python's assignment or method to put it in the box
Great! okay so you have got the idea of variables i can put all sorts of datatypes in them or call them whatever i wish!
Okay so this has been a pretty intense especially with all the binary stuff (i will post the floating point stuff in a separate post below) Now i can't emphasis enough so long as you get basic binary that should be enough! The tasks below, if you can do 1 - 5 without looking up at the top you are know enough to move on if you wish. 6 - 10 are really for those smart cookies amongst us. Please ask for help below if you're struggling with any of it, I'm happy to try and help.
1) Convert 0110 to base 10 (normal counting)?
(to check you can do 0b0110 in the python interpreter)
2) Convert 5 to binary?
(to check use bin(5))
3) How many bits would it take to represent 500?
(to check do bin(500) and then count the bits)
4) Store "Bonjour" in a variable called hello
(to check simply type hello and it should say "Bonjour")
5) Store 9.4 in a variable and then add 0.1 to it and store it back in the same variable
(to check type the variable name to check 9.4 is in it then add 0.1 and check you stored it by typing the variable name again)
6) Double a number only using << or >>
check a number has been doubled
7) Try and store "Bob" in a variable and check what type it is using type() (check the type of the variable not "Bob"
8) What number is 1101 in 2s complement?
(to check your right check Lesson 3)
9) Whats the number 1011.0100?
(to check your right check Lesson 3)
10) Whats the number 1011.101?
(to check your right check Lesson 3)
Posted: Jun 28 2011, 03:50 PM
SLF IRC Team
Member No.: 180
Joined: 15-May 11
Floating point Binary
Okay this comes with the warning its hard however its quite interesting. Now with fixed point you have a . in 1 place and that was that we were doing 4 bits for each side so like 0000.0000 but in computers its just 00000000 it knows where the . should be, now with floating point instead of the . being in a set place a certain amount of bits are to whats known as the exponent and mantissa like we use standard form in maths like:
4 x 10^6
which means 4000000
we can do that with floating point numbers to allow us to represent really large and really small numbers, with 0000.0000 we can represent from 0 to 15.9375 which is okay but we want to represent more so we could use 3 of the bits to represent the exponent and the other 5 to represent the mantissa the main bit of the number!
that means because its positive (it uses 2s complement) you move the . to make the magnitude larger so you float the . to the right this 2 places
011 = 2
so it becomes
this can then be converted to be 2.875
now you might ask whats the point but we can represent larger numbers and much smaller so instead of just like 0.125 (lowest besides 0 number) we could do
100 = -4 (2s complement remember)
so you move the . to make the number smaller because its negative so you move the . to make:
which in base 10 is 0.03125 much smaller than we use to be able to represent
when you scale it up so you don't just use 5 bits here and 3 there and you use a lot you can represent really really really tiny and really really really huge numbers with very little space at all but it comes at the cost of procession.
Posted: May 30 2012, 03:37 AM
Member No.: 1588
Joined: 30-May 12
How would I go about doing something like this?
The first parameter is an arbitrary integer that you can think of as
being base 10. The second parameter is an integer that specifies a
digit in the first parameter. This function returns that digit. Digits
are counted from right to left, so that 0 represents the 0s digit, 1
represents the 10s digit, 2 represents the 100s digit and so on. So
nth_digit(123,0) should return 3, nth_digit(123,1) should return 2,
and nth_digit(123,2) should return 1.
You can assume the first number is positive, and the second number
refers to a digit that is explicitly written. So you will not need to
handle something like nth_digit(123,4)
Posted: Jun 10 2012, 03:02 PM
Member No.: 611
Joined: 5-August 11
This is a crosspost to a really old thread, man... (d.d)
Its impolite to post the same thing in two forums, so be nice in the future.
Anyway, I answered your question over here.
Posted: Jun 10 2012, 06:19 PM
Member No.: 928
Joined: 15-October 11
He sure didn't steal his username.