Mathematics for Computing 2016-2017. Lecture 1: Course Introduction and Numerical Representation презентация

Mathematics for Computing 2016-2017

Topics 2016-17 Number Representation Logarithms Logic Set Theory Relations & Functions Graph Theory

Assessment In Class Test (Partway through term, 31/10) (20% of marks) ‘Homework’ (3 parts for 10% of marks) Two hour unseen examination in May/June 2017 (70% of marks)

Lecture / tutorial plans Lecture every week 18:00 for 18:10 start. 1 – 2½ hours (with break) Tutorials (problems and answers) one week in two (~1½ hours) Compulsory In-Class Test, October 31st Lecture Notes etc. will appear on Moodle Class split in two rooms

Provisional Timetable

Course Textbook Schaum’s Outlines Series Essential Computer Mathematics Author: Seymour Lipschutz ISBN 0-07-037990-4

Maths Support http://www.bbk.ac.uk/business/current-students/learning-co-ordinators/eva-szatmari See separate powerpoint file.

Lecture 1 Rule 1 Communication is not easy, How do you tell a computer what to do?

Welcome Rule 1 We want to get the computer to do NEW complicated things We start by learning the basics of its language, Numerical Representation, Logic …

Memory for numbers We don’t know how our memory stores numbers We know how a computer does (we designed it) Full glass is 1, empty is 0

Great, we know how to store 1 and 0 in the computer memory Great, we know how to store 1 and 0 in the computer memory How do we store 0,1,2,3? We use two cups!

If we want extra numbers we add an extra cup! If we want extra numbers we add an extra cup! Each cup we add doubles the number of values we can store

We don’t need the cups now. We don’t need the cups now. Let’s understand how this works We shall look for repetitive patterns and see what they mean

Convert from Binary to Decimal When we translate from the binary base (base 2) the decimal base (base 10 – ten fingers) The first binary digit tells us whether to add 1 The second binary digit tells us whether to add 2 The third binary digit tells us whether to add 4 The fourth binary digit tells us whether to add ??

Convert from Binary to Decimal When we translate from the binary base to the decimal base The first binary digit tells us whether to add 1 Every digit afterwards tells us whether to add exactly two times as much a the previous digit Lets try this out

The binary system (computer) The way the computer stores numbers Base 2 Digits 0 and 1 Example: 110110112   msd lsd (most significant digit) (least significant digit)

The decimal system (ours) Probably because we started counting with our fingers Base 10 Digits 0,1,2,3,4,5,6,7,8,9 Example: 7641321910   msd lsd

Significant Figures Significant Figures: Important in science for precision of measurements. All non-zero digits are significant Leading zeros are not significant e.g.  = 3.14 (to 3 s.f.) = 3.142 (to 4 s.f.) = 3.1416 (to 5 s.f.)

Some binary numbers!!!

Convert from Binary to Decimal Lets make this more mathematical, We now use powers of 2 to represent 1,2,4,8,… Note that the power is the index of the digit, when the indices start from 0 (first index is 0) (digit with index 6 corresponds to 26)

Convert from Binary to Decimal Example of how to use what we learned to convert from binary to decimal

Idea for Converting Decimal to Binary Digit at position 0 is easy. It is 1 if the number is even and 0 otherwise Why? In a binary number only the least significant digit (20=1)

Convert from Decimal to Binary

What Happens when we Convert from Decimal to Binary

Decimal to Binary conversion Algorithmically: Natural Numbers 1. Input n (natural no.) 2. Repeat 2.1. Output n mod 2 2.2. n  n div 2 until n = 0

Convert from Decimal to Binary

Numbers we can already represent Natural numbers: 1, 2, 3, 4, … Alternative versions of the number six Decimal: 6 Alphabetically: six Roman: VI Tallying:

What’s still missing Fractional numbers (real numbers) Versions of one and a quarter Mixed number: 1¼, Improper fraction: 5/4, Decimal: 1.25

Decimal numbers (base 10) String of digits - symbol for negative numbers Decimal point A positional number system, with the index giving the ‘value’ of each position. Example: 3583.102 = 3 x 103 + 5 x 102 + 8 x 101 + 3 x 100 + 1 x 10-1 + 0 x 10-2 + 2 x 10-3

Representing Decimal numbers in Binary We can use two binary numbers to represent a fraction by letting the first number be the enumerator and the other be denominator Problem: we want operation such as addition and subtraction to execute fast. This representation is not optimal.

Representing Fractions in Binary Use a decimal point like in decimal numbers There are two binary numbers the first is the number before the (radix) point and the other after the point

Representing decimal numbers in binary

Convert fractional part from Decimal to Binary To convert the decimal part:

Negative numbers First bit (MSB) is the sign bit If it is 0 the number is positive If it is 1 the number is negative Goal when definition was chosen: Maximize use of memory Make computation easy

Negative Numbers – Calculate two’s Complement The generate two’s complement Write out the positive version of number, Write complement of each bit (0 becomes 1 and 1 becomes 0) Add 1 The result is the two’s complement and the negative version of the number

Negative Numbers – Two’s Complement (examples) 3bit 8bit 011 310 00011101 2910 number 100 11100010 complement + 001 00000001 +1 === ======== 101 -310 11100011 -2910 2’s complement

Negative numbers – Two’s Complement(3 bits) First bit (MSB) is the sign bit If it is 0 the number is positive If it is 1 the number is negative Goal when definition was chosen: Maximize use of memory Make computation easy

Negative numbers – Two’s Complement (4 bits)

Computer representation Fixed length Integers Real Sign

Bits, bytes, words Bit: a single binary digit Byte: eight bits Word: Depends!!! Long Word: two words

Integers A two byte integer 16 bits 216 possibilities  65536 -32768  n  32767 or 0  n  65535

Signed integers

Real numbers ‘Human’ form: 4563.2835 Exponential form: 0.45632835 x 104 General form: m x be Normalised binary exponential form: m x 2e

Real numbers Conversion from Human to Exponential and back 655.54 = 0. 65554 * 103 0.000545346 = 0. 545346 *10-3 0.523432 * 105 = 52343.2 0.7983476 * 10-4 = 0.00007983476

Real numbers 2 For a 32 bit real number Sign, 1 bit Significand, 23 bits Exponent, 8 bits

Types of numbers Integers: …, -3, -2, -1, 0, 1, 2, 3, … Rational numbers: m/n, where m and n are integers and n  0. Examples: ½, 5/3, ¼ = 0.25 1/3 = 0.3333… Irrational numbers, examples: 2  1.414,   22/7  3.14159 e  2.718.

Other representations Base Index form Number = baseindex e.g. 100 = 102 Percentage form Percentage = number/100 e.g. 45% = 45/100 = 0.45 20% = 20/100 = 0.2 110% = 110/100 = 1.1

Other number systems Bases can be any natural number except 1. Common examples are : Binary (base 2) Octal (base 8) Hexadecimal (base 16) We’ll show what to do with base 5 and 7 and then deal with the octal and hexadecimal bases

Convert from Decimal to Base 7

Convert from Base 7 to Decimal

Convert from Decimal to Base 5 and back

Octal Base eight Digits 0,1,2,3,4,5,6,7 Example: 1210 = 148 = 11002 100110111102 Binary

Convert from Binary to Octal and back

Hexadecimal Base sixteen Digits 0,1,2,3,4,5,6,7,8,9,A(10), B(11), C(12),D(13),E(14),F(15). Example B316 = 17910 = 101100112 110101012 Binary

Convert from Binary to Hexadecimal and back

Writing down the hexadecimal conversion table

Extra Slides 1 0 1 0 0 1 1 +1 1 1 0 1 1 1

End of Lecture

Extra Slides The following slides present the same information already appearing in other slides, in a different manner.

Decimal to Binary conversion 1: Mathematical Operations n div 2 is the quotient. n mod 2 is the remainder. For example: 14 div 2 = 7, 14 mod 2 = 0 17 div 2 = 8, 17 mod 2 = 1

Decimal to Binary conversion 2: Natural Numbers 1. Input n (natural no.) 2. Repeat 2.1. Output n mod 2 2.2. n  n div 2 until n = 0

Decimal to Binary conversion 3: Fractional Numbers 1. Input n 2. Repeat 2.1. m  2n 2.2. Output m  2.3. n  frac(m) until n = 0 m  is the integer part of m frac(m) is the fraction part.

Some hexadecimal (and binary) numbers!!!

End