# MSc/PGDip Computer Science: A refresher course on some basic arithmetic

We 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 minuses

A 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 8
```
With 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
```

### Modulo

An 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
```

### Powers

```32, "three squared", is 3 * 3, which is 9.
33, "three cubed", is 3 * 3 * 3, which is 27.
34, "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 squared (i.e. 2 to the 2nd power) 4 2 cubed (i.e. 2 to the 3rd power) 8 2 to the 4th 16 2 to the 5th 32 2 to the 6th 64 2 to the 7th 128 2 to the 8th 256 2 to the 9th 512 2 to the 10th 1024

21 = 2, and 20 = 1. In fact, x1 = x, and x0 = 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 32, 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 logarithms

If 64 tennis players played a knockout tournament, how many rounds would it take to have a champion?

 32 would be knocked out in round 1 16 in round 2 8 in round 3 4 in round 4 (the quarter-finals) 2 in round 5 (the semi-finals) 1 in round 6 (the final)

Do the numbers in the left-hand column look familiar? They ought to. They are the powers of 2. You need 6 rounds for 64 players; 64 is 26. If you had a tournament beginning with 1024 players, you would know that you would need 10 rounds because 1024 is 210.

The base2 logarithm of some number x is simply the power to which 2 must be raised in order to give you x. 3 is the base2 logarithm of 8 because 23 gives 8. The base2 logarithm of 8 is written as `log28`. What is `log264`? It's 6 because 64 is 26. If n is the number of players in a tournament, then the number of rounds is `log2n`.

You can have logarithms to bases other than 2 — base10 logarithms, for example — but the base2 ones are the most common in computing, so that you can generally assume that, if people in computing write just `log n`, they mean `log2 n`.

These base2 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 `log2n`. Though this can seem mysterious if you have never heard of logarithms, there is nothing very complicated about it.

### Simplifying fractions

In an exam question that I once set, I suggested that students begin their answer by calculating the following:

```18 / 48 * 23
```
(eighteen over forty-eight 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.

```(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) * 8
```
you 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.)

 1 What is (a) –4 + 7 (b) 7 – –4 (c) –5 – –9 2 What is (a) 4 * –6 (b) –4 / 8 (c) –12 / –6 3 What is (a) 17 % 5 (b) 35 % 7 (c) 4 % 5 4 What is (a) 28 (b) 21 (c) √144 5 What is (a) 24/39 (b) (35/14) * 22 (c) `log2128`

```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
```