gentle introduction to mathematics for computer

Mathematics for Computer Scientists Numbers One problem we encounter is that there are numbers which are neither integers or rationals but something else. The Greeks were surprised and confused when it √ was demonstrated that 2 could not be written exactly as a fraction. Technically √ there are no integer values P and Q such that P/Q = 2. From our point of view we will not need to delve much further into the details, especially as we can get good enough approximation using fractions. For example 22/7 is a reasonable approximation for π while 355/113 is better. You will find people refer to the real numbers, sometimes written R, by which they mean all the numbers we have discussed to date. Notation As you will have realized by now there is a good deal of notation and we list some of the symbols and functions you may meet. If x is less than y then we write x < y. If there is a possibility that they might be equal then x ≤ y. Of course we can write these the other way around. So y > x or y ≥ x. Obviously we can also say y is greater than x or greater than or equal to x The floor function of a real number x, denoted by ⌊x⌋ or floor(x), is a function that returns the largest integer less than or equal to x. So ⌊2.7⌋ = 2 and ⌊−3.6⌋ = −4. The function floor in Java and Python performs this operation. There is an obvious(?) connection to mod since b mod a can be written b−floor(b÷a)×a. So 25 mod 4 = 25−⌊25/4⌋×4 = 25−6×4 = 1 Download free eBooks at bookboon.com 11 Mathematics for Computer Scientists Numbers A less used function is the ceiling function, written ⌈x⌉ or ceil(x) or ceiling(x), is the function that returns the smallest integer not less than x. Hence ⌈2.7⌉ = 3. The modulus of x written | x | is just x when x ≥ 0 and −x when x < 0. So | 2 |= 2 and | −6 |= 6. The famous result about the modulus is that for any x and y | x + y |≤| x | + | y | We met ab when we discussed integers and in the same way we can have xy when x and y are not integers. We discuss this in detail when we meet the exponential function. Note however – a0=1 for all a = 1 – 0b = 0 for all values of b including zero. 1.0.3 Number Systems We are so used to working in a decimal system we forget that it is a recent invention and was a revolutionary idea. It is time we looked carefully at how we represent numbers. We normally use the decimal system so 3459 isis shorthand 3 x 1000 + 4× 3459 shorthand for for 3 + 4 x 100+5+9. 100 + 5 x 10 + 9. The position of the digit is vital as it enables us to distinguish between 30 and 3. The decimal system is a positional numeral system; it has positions for units, tens, hundreds and so on. The position of each digit implies the multiplier (a power of ten) to be used with that digit and each position has a value ten times that of the position to its right. Notice we may save space by writing 1000 as 103 the 3 denoting the number of zeros. So 100000 = 105. If the superscript is negative then we mean a fraction e.g 103 = 1/1000. Perhaps the cleverest part of the positional system was the addition of the decimal point allowing us to include decimal fractions. Thus 123.456 is equivalent to 1 × 100 + 2 × 10 + 3 + numbers after the point + 4 × 1/10 + 5 × 1/100 + 6 × 1/1000 Multiplier digits . . . 102 101 100 ... 1 2 3 . 10−1 10−2 10−3 . . . . 4 5 6 ... ↑ decimal point However there is no real reason why we should use powers of 10, or base 10. The Babylonians use base 60 and base 12 was very common during the middle ages in Europe. Today the common number systems are Download free eBooks at bookboon.com 12 Mathematics for Computer Scientists Numbers Decimal number system: symbols 0-9; base 10 Binary number system:symbols symbols 0,1; base 2 Hexadecimal number system:symbols 0-9,A-F; base 16 here A ≡ 10 , B ≡ 11 , C ≡ 12 , D ≡13 E ≡ 14 , F≡ 15. Octal number system: symbols 0-7; base 8 Binary In the binary scale we express numbers in powers of 2 rather than the 10s of the decimal scale. For some numbers this is easy so, if recall 20 = 1, Decimal number 8 7 6 5 4 3 2 1 in powers of 2 = = = = = = = = 23 22 + 21 + 20 22 + 21 22 + 20 22 21 + 20 21 20 power of 3 2 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 2 Binary number 0 0 1000 1 111 0 110 1 101 0 100 1 11 0 10 1 1 As in decimal we write this with the position of the digit representing the power, the first place after the decimal being the 20 position the next the 21 and so on. To convert a decimal number to binary we can use our mod operator. As an example consider 88 in decimal or 8810. We would like to write it as a binary. We take the number and successively divide mod 2. See below Step number n xn ⌊xn/2⌋ xn 0 88 44 1 44 22 2 22 11 3 11 5 4 5 2 5 2 1 6 1 0 mod 2 0 0 0 1 1 0 1 Writing the last column in reverse, that is from the bottom up, we have 1011000 which is the binary for of 88, i.e.8810 = 10110002. Download free eBooks at bookboon.com 13