MSc/PGDip Computer Science: A refresher course on some basic arithmeticWe do not require any qualifications in mathematics for the MSc, but lecturers do use arithmetic from time to time. Here is a brief reminder of some aspects of arithmetic which you might come across in the MSc and which you will be expected to know about. Pluses and minusesA negative number, say –3, behaves as in these examples: 5 + –3 is the same as 5 – 3, which is 2 whereas 5 – –3 is the same as 5 + 3, which is 8With multiplication and division, the result is positive if the signs are the same, negative if they are different, thus: 5 * 3 = 15 (the multiplication operator is generally written as * in computing) 5 * –3 = –15 –5 * 3 = –15 –5 * –3 = 15 3 /–5 = –0.6 –3 /–5 = 0.6 ModuloAn integer is a whole number, a number such as 12, –5, 0, 2001, without any decimal point or fractional part. When you do integer division, i.e. dividing one whole number by another not using fractions or decimals, there ought really to be two parts to the result – the quotient and the remainder. For example: 13 / 5 = 2 remainder 3 24 / 6 = 4 remainder 0 5 / 7 = 0 remainder 5 (7 into 5 "won't go", so the quotient is 0)If you do integer division on a computer, however, you generally get only the first part as the result. (Computers can of course do the sort of division that produces a result with a decimal point in it, but I am talking here about integer division.) It will compute the result of 13/5 as 2; the remainder 3 seems to get ignored. But sometimes you want to know the remainder, and you can get it by using the "mod" operator ("mod" is short for "modulo"). 13 mod 5 is 3, i.e. 3 is what is left over after dividing 13 by 5. In the C and C++ programming languages, the character % is used to mean "mod". So: 13 % 5 = 3 24 % 6 = 0 5 % 7 = 5 Powers3^{2}, "three squared", is 3 * 3, which is 9. 3^{3}, "three cubed", is 3 * 3 * 3, which is 27. 3^{4}, "three to the fourth (power)", is 3 * 3 * 3 * 3, which is 81. and so on. The powers of 2 keep cropping up in computing and it is worth remembering the first few:
2^{1} = 2, and 2^{0} = 1. In fact, x^{1} = x, and x^{0} = 1 for any value of x. Along with squares come square roots (there are also cube roots etc, but we'll settle for square roots for now). 9 is 3^{2}, so 3 is the square root of 9, written as √9. The square root of some number x is that number which, when squared, gives you x. The square root of 49, for example, is 7. Base 2 logarithmsIf 64 tennis players played a knockout tournament, how many rounds would it take to have a champion?
Do the numbers in the lefthand column look familiar? They ought to. They are the powers of 2. You need 6 rounds for 64 players; 64 is 2^{6}. If you had a tournament beginning with 1024 players, you would know that you would need 10 rounds because 1024 is 2^{10}.
The base_{2} logarithm of some number x is simply the power to which 2 must be
raised in order to give you x. 3 is the base_{2} logarithm of 8
because 2^{3} gives 8. The base_{2} logarithm of 8 is written
as
You can have logarithms to bases other than 2 — base_{10} logarithms, for example — but the base_{2} ones are the most
common in computing, so that you can generally assume that, if people in computing
write just
These base_{2} logarithms are often used in analysing the
performance of an algorithm. For example, you might have an algorithm
that searches for an item in an ordered list of items — like a name
in a phone book — and it might be claimed that, for a list of n items,
the number of steps the algorithm needs to go through is Simplifying fractionsIn an exam question that I once set, I suggested that students begin their answer by calculating the following: 18 / 48 * 2^{3}(eighteen over fortyeight times two cubed) The arithmetic is pretty simple if you remember how to simplify fractions. A fraction such as 27/36 can be simplified by dividing the top part (the numerator) and the bottom part (the denominator) by the same number. If you divide these both by 9 you get 3/4. If you have two fractions to multiply together, such as (14/36) * (6/7), you can often make things easier if you can find a number that goes into one of the top parts and one of the bottom parts. They could be the top part and bottom part of the same fraction or the top of one and the bottom of the other. Say you had (5/12) * (8/15)You can't do anything with the 5 and the 12 or with the 8 and the 15, but you can do something with the 5 and the 15; 5 goes into 5 and into 15 so you can rewrite the problem as (1/12) * (8/3)You can also do something with the 12 and the 8; 4 goes into both 12 and 8, so you can rewrite the problem as (1/3) * (2/3)Now you multiply the two numerators (1*2) and the two denominators (3*3), giving you 2/9. To apply this method to the problem I mentioned at the beginning (18/48) * 8you have to remember that 8 is the same as (8/1). In other words, an 8 on its own is a top part. 8 goes into 8 and into 48, giving (18/6) * (1/1)and 6 goes into 6 and into 18 giving (3/1) * (1/1)which is 3. A few questions for you to answer(Answers below, but try them first.)
S c r o l l d o w n w h e n y o u w a n t t o s e e t h e a n s w e r s Answers
