Introductory Computing, using Python as the high level language

The number system we're used to is called decimal. The base of the decimal system is 10. Number systems used in computing are

bit, wikipedia (http://en.wikipedia.org/wiki/Bit).

Computers crunch numbers. We (people) use the decimal number system. Computers only have bits and use these bits to make binary numbers. There are no decimal numbers inside a computer. Binary numbers are transformed by software to a decimal representation on the screen for us.

Before launching into binary numbers, lets refresh our memories on the positional nature of the representation of decimal numbers.

102=1*100  + 0*10   + 2*1
   =1*10^2 + 0*10^1 + 2*10^0

The value represented by each digit in the number 102 depends on it's position. The "1" represents "100". If the "1" was in the rightmost position it would represent "1". Each time a digit moves 1 place to the left, it increases the number it represents by a factor of the base of the number system, here 10. The left most digits represent the biggest part of the number.

binary numeral system, wikipedia (http://en.wikipedia.org/wiki/Binary_numeral_system).

In a binary number, the base is two, so the number prepresented by each position increases by a factor of 2 as you move left in the number. In binary, you need two numbers to represent all the available values. Here are the two numbers and their decimal equivalents.

binary decimal
   0  =  0
   1  =  1

Here's a binary number. What does it represent?

1101 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^1
     = 1*8   + 1*4   + 0*2   + 1*1
     = 13 decimal

As with decimal, the left most digit carries the most value (in 1101, the left most digit represents 8 decimal).

leading zeroes behave the same as for decimal numbers

00=0
01=1

Here's some more binary numbers

  binary decimal
      10=2
      11=3  (2+1)
     100=4
     101=5  (4+1)
    0101=5
00000101=5
    1001=9  (8+1)
    1011=11 (9+2,8+3))
   11011=27 (16+11, 24+3)
   11111=31

what is 1011 in decimal? ^[2]

Let's go the other way, decimal to binary

what is 7 decimal in binary? Do it by stepwise division.

Start with the power of 2 just below your number.
Take a guess. 2^3=8. This is bigger than 7.
Try next one down. 2^2=4. This is less than 7. Start there

7/4=1, remainder=3

do it again, the power of 2 just below 3 is 2

3/2=1, remainder=1

with the remainder being 0 or 1, we're finished

7=1*2^2 + 1*2^1 + 1^2^0

7 decimal = 111 binary

In the above exercise, would anything have gone wrong if you'd started dividing by 8 rather than dividing by 4? No, you would have got the answer 7 decimal = 0111 binary. The leading zero has no effect on the number, so you would still have got a right answer, you just would have done an extra step.

what is 15 decimal in binary? ^[3]

Here's python code to convert decimal to binary (http://www.daniweb.com/code/snippet285.html).

Here's bash code to convert binary to decimal. If you aren't already in a bash shell, start one up in your terminal with the command /bin/bash. On windows, click on the Cygwin icon to get a bash prompt. (comments in bash start with #). The code here is from Bash scripting Tutorial (http://www.linuxconfig.org/Bash_scripting_Tutorial) in the section on arithmetic operations. (Knowing that bash can convert binary to decimal, I found this code with google using the search terms "convert binary decimal bash").

declare -i result	#declare result to be an integer
result=2#1111		#give result the decimal value of 1111 to base 2
echo $result		#output the decimal value to the screen
15
# same code in one line
declare -i result;result=2#1111; echo $result
15

In the previous section, I showed bash code I found on the internet. When writing a new program, you'll often need some functionality that's already been coded up (after 50yrs of computing, there's not much that hasn't aleady been coded up) that's available in books or on the internet. Books on any computer language will have lots of worked examples. It's often faster to find debugged and working code, than it is to write it yourself from scratch. You're expected to do this and everyone does it. For a class exercise, you may have to nut it out yourself, but when it comes to writing working code, you borrow when you can. When you use someone else's code, you should document where you got it.

byte, wikipedia (http://en.wikipedia.org/wiki/Byte).

It turns out to be convenient (hardware wise) to manipulate bits 8 at a time. 8 bits = a byte(B). Most PCs (in 2008) are 32 bit machines, meaning that the CPU manipulates 4 bytes (32 bits) at a time. Since these machines are running at somewhere between 100MHz and 2GHz, then they are doing between 400 and 8000 million byte operations/sec.

some 1Byte numbers expressed in decimal

00001000=8
00001111=15
00010000=16
00100000=32
01000000=64
10000001=129
11111111=255

1 Byte can represent integers from 0-255

Bytes are always 8 bits. However data is shifted around according to the bus width of a computer. A 32 bit computer has 32 bit registers and 32 lines for addressing and fetching data. It can transfer data and instructions 4 bytes at a time. A term from the HPC (high performance computing or supercomputers) world, where 64 bit computing has been the standard for 30 yrs, the term word describes the width/size of a piece of data/instruction. In the HPC world, there are words of all sorts of lengths, including 128-bit. A 32-bit computer has a 32-bit (4 byte) word size.

Let's do some binary addition: The rules are similar to decimal. Here's the addition rules.

	0+0=0
	1+0=1
	1+1=0 with carry, 1+1=10

here's the addition rules in table form.

addition                carry
+ | 0 1              + | 0 1
-------              -------
0 | 0 1              0 | 0 0
1 | 1 0              1 | 0 1

	Note
	1+1=0 with a carry. 1+1!=10 (!= not equal). The extra leftmost digit, the "1" (as in "1+1=10") becomes the carry digit. It's handled separately by the computer. If you want it, you have to go find it. The equivalent table in decimal for a one digit computer would show that 8+7=5 (and not 15)

worked example, working from right to left, one bit at a time

 111		(what demical numbers are being added here?)
 010 +
 ---
  01
 1   carry

 001
1    carry

1001

What is 1001+0011 ^[4] ? What decimal numbers are represented?

	Note
	End Lesson 1

Algorithm, wikipedia (http://en.wikipedia.org/wiki/Algorithm).

Algorithm: A predetermined sequence of instructions (events) that will lead to a result.

e.g.the algorithm of right-to-left addition will lead to the sum of two numbers.

e.g.putting your books into your school bag in the morning will lead to them all being at school with you the next morning.

What country do we get the word "algorithm"? What does "al" mean? What other words start with "al" used in the same way? ^[5]

Some algorithms are better (faster, more efficient, scale better) than others. While computers are fast enough that even a bad algorithm can process a small number of calculations, it takes a good algorithm to process large numbers of calculations. Computers are expensive and it's only worth using a computer if you're doing large numbers of calculations. We're always interested in how an algorithm scales with problem size. So we're always interested in the goodness of the algorithm being used.

The measure of goodness of an algorithm is the rate at which the time for it's execution increases as the problem size increases (i.e. how the algorithm scales). If you double the size of the problem, does the execution time not change (independant of problem size), double (linear in problem size) or quadruple (scales as the square of the problem size)?

This change in execution time with problem size is called the Order of the algorithm.

Speed (Order) of the addition operation:

addition one bit at a time takes 8 steps for addition of 2 bytes. The Order of addition for addition, one step at a time, is O(n) i.e.time taken is proportional to n=number of bits.

There's a faster way: add the bits in parallel and handle the carries in a 2nd step

 111
 010
 ---
 101 add
 10  carry
 ---
1001

Addition done in parallel takes 2 steps, no matter how long the numbers being added (you need to increase the amount of hardware, but you only have to pay for the hardware once and the extra cost can be amortised over many addition operations).

The Order of parallel addition is O(1) i.e.is proportional to 1 i.e.addition takes the same time independant of the number of bits being added. The parallel addition algorithm is much faster than the stepwise mechanism.

Note

amortise: If one process is faster/better than another, but the faster process is more expensive but only has to be paid for once, and you can use the process as many times as you want, then you are are said to be amortising the extra cost over a the life of the machine. e.g. cost of stepwize adder=$10. cost of parallel adder=$20. If you're going to be doing 10^15 additions before you retire the machine, the amortised extra cost of the parallel adder is 10^-14$/addition. Most people will accept this extra cost because of the increased speed will save them money for each run of the program. The most common place that amortisation is used in computing is in the cost of writing a program. Writing a program is expensive; you have to pay the programmers salary, benefits, heating/AC, electricity and buy computers and lease a premises to do this. A program may cost $1k-$100M to write. However if the program is run millions of times, the cost/run for the end user may be insignificant compared to the cost of paying their staff to run the program. In this case the costs of the programmer's time is said to be amortised over the number of times the program will be run. Because writing programs is so expensive, you only write programs that are going to be run many times.

Here's the time/steps for the two types of addition for different problem sizes

	Stepwise	Parallel
1	2		2
2	4		2
3	6		2
4	8		2
.
.
16	32		2

We don't really care what the constant of proportion is, i.e.we don't care if each step takes 1usec, 1msec or 1sec, only how the time to completion scales with problem size. We know that if we scale the problem by some large number (e.g.10^6), that the constant of proportionality will be swamped by the problem size. Let's say that parallel addition took 8 steps instead of 2. Here's the new times for addition.

bits	Stepwise	Parallel
1	2		8
2	4		8
3	6		8
4	8		8
.
.
16	32		8

We only need to get to numbers of length 8 bits to be ahead with parallel addition.

say we have a 4bit computer, what is

 1010
 0110+
 ----
 0000 with 1 carry

? When you do this, a digit rolls off the left hand end.

This is called overflow Since you only have a 4bit computer, you'll get an erroneous answer. In some circumstances you'll get an error message on overflow and in other situations you won't. Since overflow is part of the design of a computer, it is expected and is not neccessarily regarded as an error. (e.g. a drinking glass will only hold so much fluid. If you put in more fluid, it will overflow. People accept overflow as part of the design of a drinking glass.)

With addition, you have to anticipate getting a number that is 1 bit longer than the two numbers being added, i.e. you'll get a 1 bit overflow.

the rules are similar to decimal - here's the 1 times table (there's no carry on binary multiplication)

* | 0 1
-------
0 | 0 0
1 | 0 1

3.9.1. left shifting (and overflow), multiplying by 10

Multiplication by 1,10,100 left shifts the digits by 0,1,2...n places (i.e. by adding a '0' on the righthand end). This is the same whether you're working in decimal or binary. Left shifting is a fast operation in a computer. When the computer detects that you're multiplying by a power of 2, it left shifts the number, rather than using the multiply hardware.

	Note
	both in binary and decimal 1*10= 10 11*10= 110 110*10=1100 what numbers are represented in each case?

Left shifting produces overflow. Assume a 4bit computer

1100*10 =1000 (not 11000) 1100*100=0000 (not 110000)

If a 0 overflows, you get the correct result.

 1010
   11 x
 ----
 1010
1010
 ----
11110 addition
 0000 carry
-----
11110

    1010
    1101x
    ----
    1010
   0000
  1010
 1010
 -------
 1110010
   1     carry (a couple of rounds)
 -------
100000010

the carries are done in parallel
multiplication is fast and is O(1).

It is not neccessary to have a separate set of hardware for subtraction. You could in principle add the negative of the number, but we don't have negative numbers (hardware only knows about 0-255 and has no concept of positive or negative numbers). (Software can interpret certain values of a byte as being negative, but we haven't got that far yet.) However we don't need negative numbers for substraction. Instead we add the complement (for binary, it's the twos complement: the twos complement instruction is fast - one clock cycle).

3.10.1. Tens complement

Let's look at subtraction by adding the complement using a decimal example.

Let's say we want to do

9-3=6

and we have a 1 decimal digit (dit) computer. Here's the addition table for a 1 dit computer.

+ | 0 1 2 3 4 5 6 7 8 9 ----------------------- 0 | 0 1 2 3 4 5 6 7 8 9 1 | 1 2 3 4 5 6 7 8 9 0 2 | 2 3 4 5 6 7 8 9 0 1 3 | 3 4 5 6 7 8 9 0 1 2 4 | 4 5 6 7 8 9 0 1 2 3 5 | 5 6 7 8 9 0 1 2 3 4 6 | 6 7 8 9 0 1 2 3 4 5 7 | 7 8 9 0 1 2 3 4 5 6 8 | 8 9 0 1 2 3 4 5 6 7 9 | 9 0 1 2 3 4 5 6 7 8

	Note
	remember, because we have a one digit machine, 9+9=8. (9+9!=18, the 1 overflows.)

If we're going to do the substraction 9-3=6, by adding some other number, what number do we add to 9 to get 6? Looking at the addition table, we find we have to add 7.

9-3=6 what we want 9+?=6 what we're looking for 9+7=6 the answer from looking up the addition table above

The ten's complement of 3 then is 7.

What if we want to subtract 3 from any other number, say 8? If we want to do 8-3=5, by adding a number to 8, on looking at the addition table, we have to add 7. So whenever we want to subtract 3, instead we add 7.

8-3=5 what we want 8+?=5 what we're looking for 8+7=5 the answer from lookup up the addition table above.

We find the ten's complement of 3 is 7 no matter what number we subtract 3 from. Making the complement of a number only depends on the number, not what we subtract it from.

What is the tens complement of 8?

9-8=1 9+?=1 9+2=1

the complement of 8 is 2.

What's the complement of 9?

9-9=0 9+?=0 9+1=0

the complement of 9 is 1.

What is the complement of 0,4? ^[8]

Overflow isn't an advantage or a disadvantage; it's just part of the design of a computer. Since we have overflow, we can use it to do subtraction by addition of the complement, rather than having to build a subtractor into the hardware.

Here's the decimal (10s or tens) complement table

number complement 0 0 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1

The complement is the number you have to add to get a sum of 0. Note that the sum is not really 0; it's 10 but the left digit is lost through overflow. The complement of a number then is

complement=(base of the system, here 10)-(the number).

But in a 1 dit computer you don't have two digits to make a 10. Instead if you want the ten's complement of 7, you ask the computer to come in 3 places from the biggest number (here 9), i.e.8,7,6 giving 6 and then you add 1 giving 7.

	Note
	Subtracting from 10 or marching in from 9 are the same to you, but if you're wiring up a computer, you can't subtract from 10, but you can count in from 9.

Summary: if we're going to do 9-3, we add 10 to the -3, giving +7. The answer we'll get by doing 9+7 will be 10 more than what we want. However the 10 will be lost through overflow (subtracting 10 from the result), giving us the correct answer.

what we wanted 9-3=6 what the computer did (added 10 to both sides) 9+(-3+10)=10+6 the answer the computer gave us 6

3.10.2. Twos complement

What is the (twos) complement of the 2 bit number 01?

find some number that when added to 01binary gives 00 (just start poking in numbers till you get the required answer).

01 #decimal 1 11 #decimal 3 ---- 00 Note: overflow is needed to get 00

See any connection between 1 and its complement 3, in a 2 bit system ^[9] ?

A 4 bit number system has base 16. See any connection between the values of the number-complement pairs and a 4 bit number system in the following examples? Using brute force, what's the twos complement of the 4 bit numbers

• 0110 ^[10] ?
• 1011 ^[11] ?
• 1001 ^[12] ?
• 1100 ^[13] ?

let's try an example in a regular 8 bit byte. Using brute force, what's the twos complement of 01000110? (for labelling, let's use the words minuend, subtrahend and difference.)

01000101 subtrahend 10111011 complement -------- 00000000

How do you make the complement in binary?

Following the decimal examples (above), to get the complement, you count in from the end number (1 or 0) by 1 number (i.e. you flip the bits), shown here

01000101 original subtrahend 10111010 bit flipped subtrahend 10111011 known twos complement

	Note
	By looking at the bit flipped number and the twos complement, you can see that you have to add 1 (as is done for the decimal example).

10111011 bit flipped subtrahend + 1

binary complement=(bit flipped subtrahend + 1)

we've found the complement (the -ve + the base number of the system)

01000101 subtrahend (decimal 69) 10111011 complement, (decimal 187)

What's the sum of the 8 bit subtrahend and its complement ^[14]

with the complement, we can do the subtraction.

10000000 minuend (decimal 128) 01000101- subtrahend (decimal 69) -------- 10111010 bit flipped subtrahend 10111011 bit flipped subtrahend +1 = complement of 69

Do the subtraction by adding the two's complement

10000000 minuend (decimal 128) 10111011 complement of decimal 69 --------- 00111011 difference (left bit rolls overflows on an 8 bit computer) result: binary decimal 10000000 128 01000101- 69- ------- --- 00111011 59

using the twos complement to do subtraction, what is

• 01101101 01100011- --------

  ^[15] ?

• 10110110 10001111- --------

  ^[16] ?

	Note
	End Lesson 2. Some kids didn't get the material on the complement and didn't complete the excercises. I added more exercises and started Lesson 3 at the beginning of binary subtraction.

Most people can only do 4bits of binary in their head. You either go to hexadecimal (below) or use a binary calculator. Fire up a terminal and try a few examples (you can recall the last line with the uparrow key and edit it without having to type in the whole line again).

bc (basic calculator?) is a general purpose calculator. Using a terminal, try some standard arithmetic e.g.(+-/*).

echo "3*4"  | bc
12

bc does all input and output in decimal, until you tell it otherwise.

Here's a few binary examples.

#input will be in binary, output is decimal since you haven't changed output
echo "ibase=2; 1100-101" | bc
7

#with obase explicitly set (not needed if obase is 10)
echo "obase=10;ibase=2; 1100-101" | bc
7

#same problem, output in binary
echo "obase=2;ibase=2; 1100-101" | bc
111

#convert decimal to binary
echo "obase=2; 17" | bc
10001

#other examples:
echo "obase=10;ibase=2; 1100+101" | bc
17

echo "obase=2;ibase=2; 1100+101" | bc
10001

Exercises: Hint - the number(s) you're processing are in the last instruction on the line. Before you run the instruction, figure out the base for the input and for the output and then decide whether you need to set obase and/or ibase.

The normal order is obase/ibase. What happens if you reverse the order of obase and ibase without changing their values?

echo "obase=10;ibase=2;01110001" |bc
113
echo "ibase=2;obase=10;01110001" |bc
1110001

bc defaults to decimal input. The first command interprets obase as 10decimal and ibase as 2decimal (i.e. binary). The input will be intepreted as binary and output will be in decimal. In the second command, obase says that all further input will be interpreted as base 2decimal (i.e. binary). Thus the obase value is 10binary (2decimal), i.e. the answer will be in binary.

To minimise suprises, use obase first, leaving the input decimal, then input the value for ibase in decimal.

For the length of numbers used in a computer, binary is cumbersome. Unless you really want to know the state of a particular bit, you use hexadecimal (a number system with base 16), which uses 1 symbol for 4 bits, and runs from 0..f (or 0..F)

binary  hex  decimal
0000 	0        0
0001 	1        1
0010 	2        2
.
.
1000 	8        8
1001 	9        9
1010 	a or A  10
1011 	b or B  11
1100 	c or C  12
1101 	d or D  13
1110 	e or E  14
1111 	f or F  15

When input to a computer is ambiguous as to its value, hexadecimal is represented as "OxF" or "Fh" (preceded by "Ox" or postceded by "h").

Here's conversion of hexadecimal to decimal using bash

declare -i result	#declare result to be an integer
result=16#ffff		#give result the value in decimal of hex ffff
echo $result		#echo $result to the screen
65535

#or all in one line
declare -i result;result=16#ffff; echo $result
65535

using bc

echo "obase=16;ibase=16; F+F" | bc
1E

	Note
	End Lesson 3. Spent some time in the first half of the class going through the twos complement exercises which I added after lesson 2. I asked the kids to try the following exercises for homework. They didn't do them so I started with the decimal/binary/hex table above and then worked them through the exercises below, at the start of the class.

Using any method

Programs don't usually do much arithmetic with integers. Integers are used as counters in loops and to keep track of the position in an executing program. Integers do come from digital sensors: e.g. images from digital cameras, digital audio, digital sensors. However most data, by the time it arrives at the computer, is reals.

In a 32 bit computer, an integer has a range of 0-4294967295 (2^32, this number is referred to, somewhat inaccurately as 4G, but we've all accepted what it means - it's the 32 bit barrier).

#in bash
#binary
declare -i result;result=2#11111111111111111111111111111111; echo $result
4294967295

#hexadecimal
declare -i result;result=16#ffffffff; echo $result
4294967295

Numbers needing more bits than the machine's register size are called Long (or long), e.g. a 64 bit number on a 32 bit machine. Arithmetic on long numbers needs at least two steps, each of 32-bit numbers, and requires an "add with carry" (ADC) instruction (found on all general purpose computers). Here's how addition of long numbers works. Let's assume a 2bit computer and we want to add a 4bit number.

0010
1011+
----
????

First split the problem into pieces managable by the hardware (here 2 bits) giving us the right hand half (the least significant bits) and the left hand half (the most significant bits).

LH         RH       
00         10         
10+        11+
--         --
??         ??  

Next a word about addition and carry: When doing addition by hand, there is never a carry for the rightmost digit, but a computer has a carry bit for the rightmost bit which is set to 0 at the start of addition.

RH
10
11+
----
?? sum
?0 carry

step 1: right column, add two digits + carry digit. The carry to the 2nd column is 0.
RH
10
11+
--
?1 sum
00 carry

step 2: left column, add two digits + carry digit. There is overflow
RH
10
01+
--
01 sum
00 carry (with overflow)

The computer has a FLAGS register (32-bits in a 32 bit computer), which holds, in each bit, status information about the executing program, including whether the previous instruction overflowed, underflowed or set a carry.

The addition above overflowed, but the computer doesn't know if the bit is required for Long addition, in which case the overflow is really a carry. The computer stores the overflow bit in the carry bit in the flags register just in case. If the computer is doing a Long addition, the next step will ask for the carry bit. If the computer isn't doing a Long addition, then then the carry bit will be ignored (and will be lost).

Here's what the calculation looks like now (only the state of the carry bit is shown in the FLAGS register). The computer will first add the right most digits in its 2bit registers, using the regular add (ADD) instruction, which only adds the two numbers and the information setup in the carry input to the adder.

before 1st addition

LH         RH        FLAGS
00         10         ?
10+        11+
--         --
??         ?? sum 
?0         ?0 carry

after 1st addition

LH         RH        FLAGS
00         10         1
10+        11+
--         --
??         01 sum 
?0         00 carry

Because of the overflow, the FLAGS register is now 1. The computer has been told that it's doing the 2nd step in a Long addition. It uses the "add with carry" (ADC) instruction, which transfers the carry bit in the FLAGS register to the adder, and then does a normal addition.

2nd addition. first step, copy carry bit from FLAGS to carry input for LH

LH         RH        FLAGS
00         10         1
10+        11+
--         --
??         01 sum 
?1         00 carry

2nd step, add digits and carry digits for LH numbers

LH         RH        FLAGS
00         10         1
10+        11+
--         --
11         01 sum 
01         00 carry

we now read out the sum digits

11         01

giving the required answer of 1101

You can chain addition to any precision (on a 32-bit computer, to 64, 96, 128-bits...) Standard calculations rarely need more than 64 bits, but some people want to calculate PI to billions of places and this is how they do it.

Long arithmetic is slower than regular arithmetic. You don't ask for Long operations unless you know you need them.

End Lesson 4

If we wanted negative integers, how would we do it? Pretend you're a 1 byte computer and you need to represent -1. You can do this by finding out the number which added to 1 gives 0.

00000001
????????+
--------
00000000

The answer is 11111111 binary, 255 decimal or FF hexadecimal (computers need overflow to work).

00000001
11111111+
--------
00000000

You've seen the computer version of -ve numbers before. They're called what ^[29] ? They are the (-ve of the number + the base) (in a 1 byte computer the base is 256).

What is -2 decimal in binary, hexadecimal? ^[30]

How do we know whether 255 should be interpreted as -1 or 255?

The level of primitive data types, is one level above a byte. Your program keeps a record of the primitive data type that each particular byte represents. When you write your program, your code will have descriptors stating whether this integer will have +ve only values (called an unsigned int) or both +ve and -ve values (called a signed int). Some programming languages will have already decided that you'll be using a signed int and you won't have any choice.

If you have a signed int, then integers with high order bit=1 are -ve while those with high order bit=0 are +ve.

binary     hexadecimal decimal
00000000       00         0
00000001       01         1
.
.
01111111       7F       127
10000000       80      -127
10000001       81      -126
.
.
11111100       FC        -4
11111101       FD        -3
11111110       FE        -2
11111111       FF        -1

Linux runs on 32 bit computers. What values is represented by 32x1's (or FFFFFFFF) in Linux bash. On a 32 bit machine we might expect this to be -1.

declare -i result;result=16#ffffffff; echo $result
4294967295

This is not a negative number. What's going on? Let's try a 64-bit number (just for reference, the biggest number that can be represented by 64 bits is 2^64=18,446,744,073,709,551,616=18.45*10^18).

declare -i result;result=16#ffffffffffffffff; echo $result
-1
declare -i result;result=16#7fffffffffffffff; echo $result
9223372036854775807
declare -i result;result=16#8000000000000000; echo $result
-9223372036854775808

bash in Linux rolls over to -ve numbers half way through the 64 numbers: the integers in bash on Linux on 32 bit machines are 64-bit signed integers.

	Note
	see long_numbers for 64-bit math on 32 bit machines.

Here is the range of values that various sized integers (int) can represent. To give an idea of the relative sizes, the table shows the time (stored as seconds) represented by that integer.

			8bit		16bit		32-bit		64-bit	
unsigned		0-255		0-65535		0-4294967296	0-18446744073709551616
signed			-/+127		-/+32767	-/+2147483647	-/+9223372036854775808

unsigned time		4mins		18hrs		136yrs		584,942,417,355yrs
signed time		2mins		9hrs		68yrs		292,471,208,677yrs

You'll see these numbers often enough that you'll start to remember them. For the moment be prepared to see numbers pop up that you've not previously seen much of.

The Y2.038K problem. In 1999 the computer world was in a flurry: programmers who'd prepresented years in their dates using 2 digits, realised that the year 00 would represent the year 1900. Paychecks would not be processed, elevators would stop working at midnight, trapping thousands (if not millions) of innocent people, and planes would fall out of the sky (except Japanese planes). A bigger calamity could not be imagined. The world's bureaucrats heroically spent millions$ of taxpayer's and consumer's money to prevent certain disaster. On 01 Jan 2000, none of the predicted misfortunes occured, for which we must thank the selfless and unacknowledged taxpayers and consumers of the world.

Unix represents time as a signed 32-bit integer of seconds, starting 1 Jan 1970, this date itself a major blunder ^[31] . If in Jan 2038, you're still using a 32 bit OS (not likely for desktop machines, but quite possible for embedded devices sitting in computer controlled machinery, which rarely need 32 bits, much less 64 bits), Unix time will overflow in Jan 2038. If in Jan 2038, your computer controlled refrigerator stops ordering food, it will be because the refrigerator is asking for food to be delivered in 1970. Jan 2008 was a good time to take out a 30yr loan for 250,000$; your monthly payments would be -1,600$ (a comment from slashdot in Jan 2008. http://it.slashdot.org/article.pl?sid=08/01/15/1928213).

A 32 bit computer can generate how many different different integers ^[32] ? This computer then is capable of generating that many different integers. If you use the integers to be labels or addresses, you can label that many different items.

A 32 bit computer addresses its memory in bytes using address lines in the hardware. The computer has to read/write a byte as one unit; it can't address individual bits in a byte in memory - it has to read or write the whole byte. Once the computer has read the byte into a register, then each bit within the byte is separately addressable. What is the maximum number of bytes a 32 bit computer can address, and how much memory is this ^[33] ?

Not too long ago, microprocessors had 4kbytes of memory. Now for many applications, computers need more than 4Gbytes of memory. These applications all have to be run on 64-bit computers. But if you wanted to increase the amount of memory available to 32-bit computers, how could you do it ^[34] ?

In fact most data and instructions in a 32-bit computer are 32 bits and are fetched 32 bits at a time, so changing the addressing to 32 bits would not be a big change. A char would now have to be represented by the byte of interest, followed (or preceded) by 3 empty bytes. The instructions that work on chars would have to mask off the 3 empty bytes. Since chars (in most programs) are a small fraction of the data held in memory, these unused bytes would not cause too much wasted space in memory.

I don't know why 32 bit computer manufacturer's didn't go to 32 bit addressing. Possible reasons might be

Harddisks read/write data to/from independantly addressable blocks (i.e. the computer cannot address individual bits or bytes within a block; it has to address and then read or write the block as one indivisible unit). Let's assume a blocksize of 512bytes. If the computer wants 1 bit off the harddisk, the computer has to know the address of the block, read the whole 512bytes into registers, manipulate the 1 bit and the write the 512byte block back to disk. What's the maximum number of blocks a 32 bit computer can address on a harddisk and how much can be stored on a disk with blocksize=512bytes ^[35] ?

If you wanted to put a bigger disk on a 32 bit computer, how would a harddisk manufacturer do it ^[36] ?

Harddisk manufacturers originally started with block size of 512 bytes and have incremented the size of the blocks continuously over the years. I don't know why hard disk manufacturers can change the blocksize whenever they want and not have programs fail, while at the same time microprocessor manufacturers have not been able change from 8bit addressing to 32 bit addressing. Possible reasons might be

My guess as why memory addressing stayed constant at the 1 byte granularity over decades, while disk block size (granularity) increased from 512 bytes to 8192 bytes, is that going to larger block size forgoes the chance of addressing a 512 byte block, which doesn't cause any problems (you don't ship disk blocks off the local machine), but choosing 32-bit addressing forgoes the chance to address a byte, which you do want to be able to move around (including sending to other machines or peripherals).

IPv4 internet addressing uses a 32 bit unsigned integer (IP) to uniquely identify each network device (e.g. no two devices/computers can have the came IP). How many devices can be simultaneously on the internet using an IPv4 IP ^[37] ?

The internet game "World of Warcraft" (reported in slashdot, http://games.slashdot.org/games/08/01/19/1321241.shtml) uses a 32 bit integer to store the amount of gold that players earn. Some players have reached that limit and can no longer receive gold from other players. If these players have 1c of gold for each bit, what is their wealth in $ ^[38] .

The world's telephone system carries voice data in 8bit form i.e. it converts your voice into bytes, each byte representing the amplitude of your voice at any instant. How many different amplitude levels can be expressed using 1byte ^[39] ? Since the phone system uses 8bits, it's simple to send bytes from computer data across phone lines. Hifi audio is usually 12bits (how many levels is this? ^[40] ) which has less noise than 8bit audio.

Digital cameras, and computer monitors use 8 bits to represent the intensity of each of the 3 primary lights of a picture; red, green and blue. This turns out to be more levels than the eye can differentiate, but not much more (the eye doesn't see the edge between one intensity and the next and only sees a continuous change in color).

A color picture from an 8 bit digital camera can have how many different colors ^[41] ?

Matte print (e.g. books, newspapers) can only reproduce about 100 levels of light, but glossy print (e.g. in fine books and magazines) can reproduce about 180 levels, which is why expensive advertisements are run in glossy magazines.

The human eye can accomodate a range of light from nightime to midday on a cloudless day, a range of 10^7 in intensity (I think). The eye can see features in a face in shadow and in the face of a person standing next to them in full sun, but an 8 bit digital camera will, according to the exposure, only see the face of one, while the other will be washed out (either dark, or light). To help in situations of high contrast, expensive digital cameras record 12bits, allowing range compression and expansion. These photos are post-processed to reduce the range to 8bits for display (or printing) but keeping constrast in both the light and dark areas (i.e. you can see the features of a face in shadow and a face in bright light in the same photo).

What other things could we use 32-bits for: How many -ve numbers could we have ^[42] ? How many prime numbers could we address ^[43] ?

End Lesson 5. At the start of the next class, I revised the number of items that a 32 bit computer could represent. The students had forgotten the number of integers that could be represented by 32 bits (not only the 4G value, but the concept of there being a limit associated with 32 bits). I went through the number of integers, computers on the internet, blocks on a hard disk etc again. The seemed to remember the concept after a few examples. My partner reminded me that you have to tell a student 3 times before you can expect them to start to remember a fact.

Now that we're at the level of primitive data types, we can use a language like python.

fire up python; you will be running python in immediate (interactive) mode, where it interprets each instruction one at a time, and returns to the prompt. (In normal operation a program keeps executing till it has to wait, say for a keystroke from you.)

You will get the python ">>>" prompt

Python 2.4.3 (#1, Apr 22 2006, 01:50:16) 
[GCC 2.95.3 20010315 (release)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 

	Note
	The following examples are based on Chapter 1 of the LiveWires tutorial "Introducing Python".

try a few subtractions, multiplications and divisions on your own.

>>> 12 + 13
25

>>> 123456 * 3
370368

How about this one?

>>> 7/3
2	#7,3 are integers. You're asking to do integer arithmetic. You get an integer answer.
>>> 

>>> 7%3
1	#'%' is modulo (remainder)
>>> 

>>> 7.0/3
2.333333333333333 #as long as one of the numbers is real, the answer will be promoted to real

you'll learn about real numbers soon.

	Note
	This went over the kid's heads, so I skipped to the next section (they don't need to know this right now)

Most programs (including python) use the machine's native libraries (e.g. math, string) (which are usually written in C). (No-one writes a library when a well tested one is already available.) The size (number of bits) for various primitive types in python will then depend on the native libraries. The documentation for python says there are two types of integers (see Numeric Types http://docs.python.org/lib/typesnumeric.html).

The Python documentation doesn't tell you the sizes for these two types of integers for any particular platform: you're supposed to be able to work it out yourself. What's the largest plain integer that python can represent? (for likely numbers, look at the table in integer_range) i.e. is it 32 or 64 bit? You won't have to remember the range of integers in python, but you'll need to understand enough about a computer to figure it out. You also should not be surprised if numbers become Long when they become big enough. (In the following, remember 65536 fills 2 bytes. For compactness, I'll use hexademical to illustrate what's happening.)

Python has no trouble representing any size integers. Here are some integers from 16-256bits (Long integers end with "L").

>>> 65536-1			#16bit FFFF
65535
>>> 65536*65536-1		#32-bit FFFFFFFF
4294967295L
>>> 65536*65536*65536*65536-1	#64-bit FFFFFFFFFFFFFFFF
18446744073709551615L
>>> 65536*65536*65536*65536*65536*65536*65536*65536-1	#128-bit  (32 Fs)
340282366920938463463374607431768211455L
>>> 65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536*65536-1 #256bit
115792089237316195423570985008687907853269984665640564039457584007913129639935L

From the above output, the 16bit number 65536 is a plain integer, but the 32 bit number is Long. To calculate 65536*65536-1, we would first have had to calculate the intermediate result 65536*65536 which would be a Long (needs 33bits). If you subtract 1 from a Long, you still have a Long (even if it could be represented as a plain), so FFFFFFFF could be a plain integer, but we wouldn't have found out doing it this way. Let's look around for a 32 bit limit. Remember that only half of the integer range is used in signed integers, so let's look at half of a 32-bit number.

#here we would need 33 bits to handle the multiplication overflow 
#so we already know that the answer will be a L number.
>>>65536*65536-1	# FFFFFFFF
4294967295L
#what's half of 65536?
>>> 65536/2 		# 8000       
32768
#The result will be 80000000H, which if a signed integer will be a -ve number
#It looks like python promotes the integer to a L
>>> 32768*65536		# 80000000
2147483648L
#Let's get below 80000000H to 7FFF0000H. 
Yes it's a plain integer
>>> 32767*65536
2147418112
#Let's try 7FFFFFFFH. Yes it's a plain integer.
>>> 32767*65536+65535
2147483647
#just checking 80000000H again, this time approaching from below.
#It's L
>>> 32767*65536+65536
2147483648L

The largest plain integer represented by python is 7FFFFFFFh or 2147483647.

This process above, of poking numbers (or different piece of code) into a program to see what it does is called noodling. It's a good way to learn.

What's the -ve most plain integer in python ^[44]

Python uses a signed 32-bit integer to represent plain integers.

We need to represent the characters in the alphabet, so the computer can type them on the screen and receive them from the keyboard. We need upper and lower case (52) + numbers (10), plus some punctuation and printer/screen control characters (move up/down/left/right, carriage return, line feed, end of file).

abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0123456789
,. !@#$%^&*()-_[]{};:'"<>;/?`~

This is more than 64, but less than 127. This number of characters requires 7 bits. A regular 8 bit byte is used with the top 127 generally unused. The mapping between the 256 possibilities in a byte and the symbols displayed above, as mandated by the USGovt, is called ASCII.

A table of ascii characters and their binary/decimal/hexadecimal equivalents is at wiki, ASCII (http://en.wikipedia.org/wiki/ASCII). The table of printable characters (http://en.wikipedia.org/wiki/ASCII#ASCII_printable_characters). shows that in ASCII, the characters are in alphabetical order.

	Note
	unlike some other character sets e.g.EBCDIC http://en.wikipedia.org/wiki/EBCDIC originally devised as an extension of Binary Coded Decimal (BCD) http://en.wikipedia.org/wiki/Binary-coded_decimal needed to handle money.

A table which better illustrates the hexadecimal organisation of ASCII is ASCII Chart and Other Resources (http://www.jimprice.com/jim-asc.shtml#table). (A slightly fancier table ASCII Table and Unicode Characters http://ascii-table.com/).

The numbers are 3hex+number. This allows easy conversion of a character representing a number into a number (you mask off the left 4 bits and add the right 4 bits into the output number).

bash converts the hexadecimal representation of a character to its ascii symbol using this command

echo $'\x41'
A

	Note
	The "41" is hex and the 'A' output is a char (not a hex number). The rest of the command is obscure bash magic.

How many letters down the alphabet is the character 'B' (try it at the prompt) ^[45] ? How many letters down the alphabet is the character represented by hex '51' ^[46] ? Knowing that the hex for 'A' is 41h, figure out the hex for 'Z' and then try it ^[47]

To change between upper and lower case, the 6th bit in the byte is flipped. What change in value (as an integer) does flipping the 6th bit represent ^[48] ?

echo $'\x5A'
Z

echo $'\x7A'
z

In a program. to differentiate a character from a number or variable do this

'c'	char
 c      the variable named c #better to use a longer descriptive name, eg computer_name
 7      the number 7
'7'	the character 7

Computers can scan text to test which characters are letters (A-Z,a-z), which are numbers (0-9) and which are punctuation. The computer can match characters (e.g. is the character an 'A' or a '9'?).

Note

Every keystroke on your keyboard is a character. If you type "3.14159" on the keyboard, the computer accepts it as a series of characters. If you want this to be a real, then you have to explicitely tell the computer to convert the string of characters into a number. If the computer asks you to input a number at the keyboard, your keystrokes will first be put into a string buffer and later you program will have to convert the string to a number. If you have "3.14159" displayed on the screen and swipe it with your mouse and put it into a buffer, it will be in your buffer as a string of characters. All normal input and output on a computer is characters and strings e.g. keyboard, screen, printer. (Some programs exchange data as binary, but you have to set that up.)

	Note
	The representation of real numbers take a bit of explaining. You don't need to understand how the are represented to use them (we'll do that later - look in Real Numbers)

"real" numbers (also called a "floating point" numbers) in computing are numbers like 3.14159 - anything with a decimal point. You do arithmetic on them.

>>> 3.0*6.0
18.0

You can mix integers and reals - the computer handles it for you, promoting the integer to a real.

>>> 3.0*6
18.0

Be careful how you mix integers and reals. The computer first evaluates (7/2) not knowing that ahead an evaluation of a real.

>>> 7/2*5.0
15.0

A minor rearrangement of this code gives

>>> 5.0*7/2
17.5

Minor editing of this code makes a big difference in the output (one is correct and one is not). Code where a minor edit (like rearranging the order of a multiplication, which should not change the result) gives a different answer. Such code is called fragile code. Someone (maybe you), years later, could be working on your code and not see the code bomb and will rearrange the line to trigger the bomb.

You should practice safe programming. When mixing integers and reals, explicitely promote the integers to reals, and don't expect the computer to do it for you. Don't rely on rules of precedence too much. Use brackets to make code clear for the reader. This is how the code should be written.

>>> (5.0*7.0)/2.0
17.5
>>> (7.0/2.0)*5.0
17.5

a string is a series of characters delineated by a pair of double or singe quote characters; e.g. "happy birthday!", "1600 Pennsylvania Ave", "temperature=32F, pressure=29.90in", 'I am "late"'

In principle it's possible to operate on strings as arrays of characters, but strings are the dominant form of input and output on a computer (all computers and people can read them), so all languages have instructions to search, match, read and write strings.

In situations where enormous amounts of data are involved, which will never be read by a human and only ever read by another computer (mapping, photos, MRI data), then data is written in the more compact binary form. You'll still need a team of programmers to write the code to allow each new generation of computer to read and write that format.

End Lesson 6

Until you get used to the rules, and familiar with the error messages, you will have to check each time what you have. Some interconversions are done without asking and others have to be invoked explicitely.

Here's some operations on numbers

>>> variable=3.14159
>>> 3*variable		#since you can multiply, it must be a number, the integer is automatically promoted to real
9.4247699999999988

			#how does python know 3.14159 is a number and not a string?
			#see below for variable=3.14159q	

>>> print variable	#you can print numbers
3.14159

			#the + operator joins strings
	                #but you can't print a string and number at the same time using a +
			#the error message is helpful
>>> print "the number is " + variable
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: cannot concatenate 'str' and 'float' objects

			#you have to turn the number into a string
>>> print "the number is " + repr(variable)
the number is 3.1415899999999999

			#you print numbers using a ','
>>> print "the number is", variable
the number is 3.14159

Here's some operations on strings

>>> variable="3.14159"
>>> 3*variable 
'3.141593.141593.14159'	#same string 3 times. 
	                #not real useful, and probably not what you want.
	                #no other language has this. 
	                #if you really need to do this, 
	                #use a construction common to all languages
	                #or no-one will be able to maintain your code.
			#
			#what would have happened if you'd done the following?
			#variable="3.14159 " 
			#or
			#variable="3.14159q"
			#or
			#variable=3.14159q	

>>> 3.0*variable	#the error message is not helpful
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: can't multiply sequence by non-int

>>> 3.0*float(variable) #float() converts a string to a real 
9.4247699999999988

>>> print variable      #you can print a string.
3.14159

Note the unhelpful error message resulting from the command 3.0*string. You should be prepared for error messages to be wrong and have to go to google to find out the real problem (don't expect the right answer to be available there either, it usually will be, but you'll still have to figure some out yourself). The interpreter knows that it has a string and not a number and could have told you. Unfortunately this is part of computing - it's always been this way. I wonder if the messages are designed to raise the cost of entry to being a programmer. The error messages from gcc, the GNU C compiler, have improved dramatically in the last 10yrs.

	Note
	One of the students commented that it was like having life boats that don't work.

The data types described so far are found in most languages. Others are common, but on knowing these four, the new ones will be easy to use when we need them.

What primitive data types do we know now ^[52] ?

	Note
	If you've been using an editor to do your binary math examples above (rather than pencil and paper) and you're happy with it, then you can skip to saving_files.

From the NCSA discussion mailing list (and other places) comes these suggestions for windows/Mac editors other than vi and emacs

When I had to code on windows (worst 3 days of my life), I installed cygwin and could pretend I was working on a unix machine. This is a reasonable approach if you already know the unix tools.

For this class pick any editor you like. Be prepared to try a few editors before finding one you like. Everyone is different and everyone likes a different editor. I like mine really simple. It seems that others like theirs complicated.

If you find yourself programming on a long term basis in a unix environment, and you expect you'll be sitting in front of a machine that someone else has setup (e.g. at work), that you should learn one of vi or emacs. It's quite disappointing to realise that the program you spend most of your time with, the editor, has such a bad interface and that no-one has designed an editor for unix like the much nicer ones available on the much dispised Microsoft platforms.

pick a name for your python files directory e.g. class_files.

Your files need to be in a place where no-one else is likely to run them accidentally. Until your files are well tested and of general use, they should be kept in your directories.

Make the file executable.

chmod 755 hello_world.py

At the command prompt, run it

# python hello_world.py
hello world!

Congratulations, you are now officially a computer programmer.

The above command works because python will have been installed in your $PATH.

You can invoke the interpreter from within your program using the shebang convention. Here's the new code (the "#!" is called a shebang)

#! /usr/bin/python 
print "hello world!"

You run it from the command line like this

# ./hello_world.py
hello world!

In windows you'll be in a command box at \Documents and Settings\UserName\class_files (or \My Documents\class_files which is the same thing). The python install sets up the registry so that you can directly execute the python program. You only need to do

hello_world.py

Congratulations, you are now officially a computer programmer.

You can execute the program by clicking on the filename using windows explorer, but the output window will open and close too fast for you to see what happened.

The unix execution options are still available, but you don't need them in windows