Report Blog Entry
Day 4:
Ok, so as promised, today we do some coding.
Something that usually is difficult at one's start of "coding experience" is ordering an array. I remember two/three years ago i was starting with c++ (my first language), and i wanted to learn more, so i asked a friend who was already good and he wanted to test me to see at what point i was, so the very first thing he asked me to do was "write a code that takes an array and puts it in ascending order". When he said it i thought it would have been easy, but that day i wasn't able to do it. Honestly today i am able to do it, but i still recognize it's not that automatic, unless you have already done it before.
Learning how to do this task will help us understand how logical operators works and how to do "decisions" (if-else, while etc...)
The thing about computers (and programming them in particular) is that the thing that makes them so useful, is also what holds them down: They do EXACTLY what you tell them.
Sorry for the whole storytelling but i will tell also another thing. My professor that started my coding (in c++ as said before), he said "if the program doesn't work, i don't want to hear nobody saying 'the computer made a mistake', because the computer did what you told to it, you made a mistake!".
---------------------------------------------------------------------------------------------------------------
Task:
So the task is, we will have a starting array like
array[10] = {2,5,1,75,13,94,3,8,15,1}
and we want the program to give us back this:
array_ordered[10] = {1,1,2,3,5,8,13,15,75,94}
[Note: this will be extremely difficult in INTERCAL]
So what i usually do is think about "how do you (human) do this?" and then you have to break your flow of thought into single, simple, executable actions that you can tell the computer.
So what do we do to order an array?
- Read the array
- Find the lowest number
-put the lowest first in the new "ordered_array"
- search the lowest number that is not the same as the one we already counted
- repeat until we did all the elements
Now, this is something you can tell to another human, however the reason why i told you those things before is because (talking to non programmers obviously) you should realize that these 5 instructions are too elaborate to tell them directly to the machine, for example
"put the lowest first" ...now, you and me already know how to tell wich one is the lowest, but the computer? oh no, he have absolutely no idea, in fact, usually programming languages give you instruments like "<" or ">" to compare numbers, but actually there is still somebody who already told the computer what to do when you type "x<y", in fact even though we consider this a basic logical operation, actually it is not, it is like calling a function.
So the challenge we are up to with intercal is understanding how all those basic things are done deep down at memory level (literal bit level), how does the computer do this, and then apply the operators we learnt yesterday.
I'm going crazy.
So, i'm having a lot of troubles both with understanding logical operators, and both with finding out what's the correct syntax to use in INTERCAL.
So, just like the other time, i made a program to understand what the f*** is happening.
1 | DO .1 <- #0
2 | DO .2 <- #1
3 | DO .4 <- #1
4 | (1)DO READ OUT .4
5 | DO (1000) NEXT
6 | DO .4 <- ?.4
7 | PLEASE READ OUT .3
8 | DO .1 <- .3
9 | DO %80 (1) NEXT
10| PLEASE GIVE UP
OUTPUT:
1:I
2:XXXMMDCCLXIX
3:XVICCCLXXXV
4:LVIICCCXLV
5:IVXCVII
-------------------------------
The code does this:
assign value 0 to variable .1
assign value 1 to variable .2
assign value 1 to variable .4
assign logical line lable (1) and output variable .4
do subroutine at logical line (1000), wich is .1 + .2 and assign the result to .3 (cycle number)
assign the result of (XOR .4) to variable .4
output variable .3
assign value of variable .3 to variable .1 (thus increasing the count of cycle)
80% chance of going back to logical line (1) [wich is line 4 actually], by doing so the cycle is repeated
give the f*** up bro please
[As you noticed, in order to do the 'while', since we don't know how to use logical operators yet, we're still using the messed up method of %]
Logical operators
Usually logical operators take two arguments, in INTERCAL is more complicated than that, in INTERCAL the operation is done between the argument and itself but shifted.
XOR:
XOR (exclusive or) is a logical operation that does this: takes 'a' and 'b', if a == b returns 0 else it returns 1.
However we have to take in account the INTERCAL process of using the operator on the "itself" but shifted.
To better understand, let's evaluate the example done in the manual:
#77 in binary is 1001101
if we shift it by 1 position to the right we get
>>#77 = 0100110 with overflowed bit 1
Now doing the comparison bit by bit, of these two binary numbers, and putting the XOR result to the right we get: 1101011
So to this we have to add 0s to the left until we have a 16-bit number, so 0000000001101011
However the manual says that the result is
1000000001101011
Wich is basically the same, but with a starting 1 bit. So this makes me think that it performs a Circular shift, meaning that >> #77 is not 0100110 with overflowed 1, but the overflowed 1 goes back to the first position on the left. However to do it correctly, we can't use the form 1001101, because we would end up with 1100110 wich is the wrong shift result, we have to consider the whole 16-bit number, so
0000000001001101 and shifting this we get 100000000100110
Wich now we use in the XOR operation with the original number, so what we actually have is:
100000000100110 XOR 0000000001001101 wich results in:
10000000011011 wich is exactly what the manual says it's the result.
AND and OR:
Regarding the comparison bit by bit, it is the same as with XOR, so we have the circular shift to the right, and the operations done between the result of the shift and the original value, but with AND or with OR this time.
Bit Shifting is FUN!!
I'm not even joking, bit shifting is very fun. Now you have to know a little bit about how an Aritmethic and Logic Unit does math operations in your computer.
Sum:
Sum is done by following these 4 rules:
-) 1+0 = 1
-) 0+1 = 1
-) 0+0 = 0
-) 1+1 = 0 with remainder of 1
So let's see 0101 + 0001 (wich means 5+1), bit by bit (from right to left) we have 1+1 = 0 remainder of 1, so 0 becomes 1 and we so have 1+0 = 1, then 1+0 = 1 and finally 0+0 = 0, so the result is 0110 wich is 6 (wich is the correct result of 5+1)
Subtraction:
For subraction, we take the second operand, we "filp" every bit, add 1 to it, and then we do the binary sum just saw above. So 0101-0001 (wich is 5-1), we take 0001 and we "flip" every bit, so it becomes 1110, then add 1 so it becomes 1111, now we do the normal sum 0101+1111 and what we get is 0100* wich is 4, the correct result.
---------------------
*At the bit in position 3 (from the right) we had 1 with remainder of 1 + 1, so the 1 flipped to 0, transferring the remainder to the next (to the left) bit, and so the 3rd bit operation became 0+1 = 1, and the 4th bit operation took the remainder 1 and became 1+1 = 0 with remainder, the remainder now goes to the 5th bit, but we only have a 4-bit number, so that "excessive" bit is truncated (it overflowed), wich is not an exception, it's the correct normal procedure, i just wanted to be clear about what just happend and why a remainder 1 disappeared
--------------------
Product and division - BitShifting:
Ok so, if you take a number in bits, and you shift it to the left, the number is multiplied by 2, if you shift it to the right, it gets divided by 2 (without remainder). So 4 decimal is 0100 binary.
4 *2 = 8 in fact 0100 shifted to the left is 1000 wich is 8.
instead 4/2=2, in fact 0100 shifted right is 0010 wich is 2
However for the division, remember it is without remainder, so 3 in binary is 0011, if you shift to the right you get 0001 wich is 1, wich is 3/2 = 1 with remainder of 0.5 that is truncated [if you do the circular shift, you get something even worse, you get 1001 wich is 9]
And for multiplication we have to take in account the overflow "mistake", if you have a 4-bit number, let's say 8, wich is in binary 1000, you shift to the left, you want to get 8*2=16, but instead you get <-1000 = 1<-0000 so basically you get 0000 with an overflowed bit 1, so the result of the shift is decimal 0, wich is wrong [also here, circular shift gets you in different trouble, 1000 shifted left becomes 0001 wich is 1]
---------------------------------------------------------------------------------------------------------------
Recap:
AND operator: (if both are 1 returns 1, else return 0)
bit a | bit b | AND result
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
OR operator: (if both are 0 return 0, else return 1)
bit a | bit b | OR result
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
XOR operator: (if the bits are equals returns 1, else return 0)
bit a | bit b | XOR result
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
---------------------------------------------------------------------------------------------------------------
WEIRD VICTORY
My mind is in fragments, my eyes burn, my sanity has disappeared, the compiler even sent me the following message at some point:
"PROGRAM REJECTED FOR MENTAL HEALTH REASONS"
And i'm not even joking, he really said that to me.
However, even though the task was at first to order an array, then it came down to detect wich of two number is higher...then, with desperation...it came to see if two number are equals at least? not even that, but we do have something, the code of today tells if both .1 and .2 are even or odds, so if .1 is odd and .2 is odd too, the result is _ (wich means 0) if .1 is odd and .2 is even result is I (wich means 1), and it's true the opposite, i mean .1 even and .2 even = _, .1 even and .2 odd = I
It's not such a great accomplishment, i understand, but little steps...we can do it little step by little step, we will slowly understand the logic, also we can build brick over brick, today we end with this thing, tomorrow we can build upon what we built today...So with the code:
1 | DO .1 <- #1
2 | DO .2 <- #2
3 | PLEASE DO (1000) NEXT
4 | DO .4 <- .3 ~ #1
5 | DO READ OUT .4
6 |PLEASE GIVE UP
"EXPLENATION":
in line 1 and 2 we decide the numbers to compare.
at line 3 we do .1 + .2, Now the trick here is that if they are both odd, they will both have a 1 at the most right position (that bit is called te LSB, wich stands for Least Significant Bit), and for the sum rules we talked about before, this will cause them to have LSB = 0 as result of the sum, wich is stored in variable .3 by the subroutine. Also if they are both even the LSB of both is going to be 0 and so the result of the sum is still 0, but if one is even and the other is odd, then only one of them will have LSB = 1 and so the result will be 1
at line 4 we finally start to use some operator, we use the ~ select operator, that i remind you, takes from the left operand the bits that are in the positions where the 1s are in the right operand. So with the select, with right operand #1 wich is all 0s except for the LSB wich is 1, we basically only take the LSB of the left operand and assign it to the variable .4
Then at line 5 we display the variable .4 as output
At line 6 we ask kindly to the compiler to give up.
Now for the logic we just explained, if the .4 is == 0, it means the result of the sum has LSB = 0 and so the numbers were of the same "kind", either both odd or both even, instead if .4 == 1, only one of them was odd, and so they were of different "Kind".
Conclusion:
I had much higher hopes for today honestly, but tomorrow i will have much more reasonable hopes. In order to not start with overwhelming tasks that lead me to waste all my day to, in the end, only do 1% of what i aimed for (like today), i will try to take on more reasonable tasks, so i consume less of my precious time, and you can have a shorter and funnier episode.
So for today it's the end, Goodbye! I don't hope you had fun, but maybe it was for you as interesting as it was for me.
Comments
Displaying 0 of 0 comments ( View all | Add Comment )