GCU Maths Computing Worksheet 2

for incoming Cyber Security & Software Development students

Summer 2021

Why is the computer still thinking?

How easy it is to make a computer to think forever

When writing computer code there are many languages available, but for the most part they all provide you the same thing. They all offer you the chance to write instructions for the computer to later execute in some specified sequence when you run your code. The problem is that computers aren’t as clever as you and will just follow the instructions given. So you have to be careful to keep the number of operations you ask it to perform within the time limits of the universe!

Here’s some basic code in C/C++:

int i = 1;
while (i < 26) {
  i = i + 1;
}
\\ When this line is reached i is no longer less than 26

Although this code is only three lines long the computer will perform far more than 3 operations.

  • It first sets i equal to 1.
  • It then checks if i is less than 26 (it finds this to be TRUE)
  • It then adds 1 to i (storing the answer overwriting i, so i is now 2)
  • It then goes back and checks if i is less than 26 (it finds this to be TRUE)
  • It then adds 1 to i (i is now 3)
  • It then goes back and checks if i is less than 26 (it finds this to be TRUE)
  • It then adds 1 to i (i is now 4)
  • It then goes back and checks if i is less than 26 (it finds this to be TRUE)
  • It then adds 1 to i (i is now 5)
  • These steps continue until i equals 26, at which point…
  • When it checks if i is less than 26 (it finds this to be FALSE)
  • The code then finished the while loop and reaches the end.

This code doesn’t do anything really other than increase i gradually until it reaches 26.

Task One

  • How many times in the above code does the computer have to check whether i is less than 26?
  • How many times does it add 1 to i?
  • If we call these two things operations then what is the total number of operations performed in this code?

Task Two

This code only stopped because, at some point during its running, i reached a point where i < 26 became FALSE.

  • What edit could you make to the i < 26 bit of code so that the code would run half as many operations?
  • What edit could you make to the i < 26 bit of code so that the code would run ten times as many operations?
  • Can you think of an edit to the i < 26 bit of code which would cause the code to run forever, and never stop?

Now let’s introduce another type of loop, the for loop.

In Javascript the syntax for a loop looks like this:

for (let j = 1; j < 6; j++) {
  \\ Do stuff here!
} \\ Closing bracket from for loop

Here’s a brief summary of this code: (if you know how for loops work you may skip this part)

  • It begins by setting j to 1
  • Then it checks the condition j < 6. If this is FALSE it jumps to the closing bracket of the for loop
  • Otherwise, it steps inside the for loop and does stuff
  • After finishing the contents of the loop it returns to the first line and performs j++, which is shorthand for add 1 to j
  • Then it checks the condition j < 6 and repeats from line 2 above.

Suppose you wished to add together the first six integers (i.e. 1+2+3+4+5+6), obviously you could just type x=1+2+3+4+5+6 to store the answer into x. However, perhaps another time you need the first seven integers, or a hundred integers. A for loop offers a flexible way to write the code once.

Consider the following Javascript code:

let total = 0;
for (let j=1; j<6; j++) {
  total = total + j
}

Task Three

  • What value should total have when this code has finished running?
  • How could you modify the code to add together the first 4000 integers?
  • If you count any comparisons and any adding as an operation, how many operations are performed when adding the first 4000 integers?

All this obsession with counting operations is important because the main limiting factor when asking a computer to process some code is the time it takes to perform the code (there is also the issue of having enough memory/space too but we shan’t worry about that today). Every operation performed will take a certain (short) amount of time, so as code gets longer and more complex it can become very important that your code is efficient and doesn’t take a million operations to perform a job that can be done in 1000.

There are dangers with using loops, however, you may have encountered some already above. One solution to this problem is to use functions and recursion. We end with an alternative way of adding lots of integers together. For this example, we shall return to some C/C++ code.

int subtotal(int n){
  if(n == 0) return(0);
  int x = n + subtotal(n-1);
  return(x);
}

int y = subtotal(2);

This code is a bit more complex, so here’s a brief explanation:

  • The first five lines create a function in C++
    • The function is called subtotal
    • The function accepts an integer input, which the function will call n while running
  • When ‘used’ (the technical term is called) the function first checks if its input equals 0, if it does equal 0 then the result is an immediate exit with value 0 (return means exit now)
  • Otherwise, the function creates a variable called x into which it tries to store the result of adding the input (called n) to the value of subtotal(n-1)
  • This is where the code gets exciting, the function knows what n is at this point, but it needs to go and work out subtotal(n-1)
  • After working out subtotal(n-1) the code adds it to n, and stores the answer in x
  • Finally it returns the value of x

Notice, that one of the steps here involves running the subtotal function again. i.e. To find the function value subtotal(n) we need to calculate subtotal(n-1) as part of the calculation. This is called recursion and can get very time-consuming.

Let’s see what happens to calculate subtotal(2): first let’s repeat the code for easy viewing.

int subtotal(int n){
  if(n == 0) return(0);
  int x = n + subtotal(n-1);
  return(x);
}

int y = subtotal(2);
  • First the input of 2 is stored into n
  • This n is checked against 0 (they are not the same), so the code continues.
  • Next the computer tries to store 2+subtotal(1) into x, however it doesn’t know what subtotal(1) is yet. So it needs to go and work it out.
    • To work out subtotal(1) it needs to run this same function but with input n=1.
    • So this calculation is started in the background, to find subtotal(1).
    • However, during this calculation it needs x = 1 + subtotal(0), but it doesn’t know what subtotal(0) is yet.
    • So it needs to go and work out subtotal(0)
      • subtotal(0) is easy, because the input is now 0, so the first line of that calculation will immediately return 0
    • So subtotal(0)=0 and in our calculation of subtotal(1) we now have x=1+0 so x=1.
    • So in our calculation of subtotal(1) we now reach the final line and return the answer subtotal(1)=1.
    • The answer to subtotal(1) is then returned to the original calculation which was trying to work out subtotal(2).
  • We’re now back in our subtotal(2) calculation, in this calculation x = 2 + subtotal(1) becomes x = 2 + 1 so x equals 3.
  • Yikes! We’ve finishing calculation subtotal(2)!

To calculate subtotal(4000) involves needing to calculate subtotal(3999), which in turn requires subtotal(3998) etc.. all the way down to subtotal(0) which itself doesn’t need to know anything else, because it’s just 0.

So here are the steps used to calculate subtotal(2):

  1. Set n=2
  2. Check if 2 equals 0
  3. Try to set x equal to 2 + subtotal(1)
  4. (inside subtotal(1) calculation) Set n=1
  5. (inside subtotal(1) calculation) Check if 1 equals 0
  6. (inside subtotal(1) calculation) Try to set x equal to 1 + subtotal(0)
  7. (inside subtotal(0) calculation) Set n=0
  8. (inside subtotal(0) calculation) Check if 0 equal 0
  9. (inside subtotal(0) calculation) Return value 0 (to step 6), so x=1+0=1
  10. (inside subtotal(1) calculation) Return value 1 (to step 3), so x=2+1=3
  11. Return the value 3

Task Four

Here’s your final task.

  • Noticing that it took 11 steps to find subtotal(2) can you work out how many steps subtotal(3) would take?
  • Can you spot the pattern to ask how many steps subtotal(4000) would take?

Extension

If you’d like to put your understanding into practice. See if you can find somewhere to run some code online. Perhaps an online C/C++ code engine, or Javascript engine. Then copy out the samples of code from Tasks One or Two. Then edit the key target values to make them really large and time how long the code takes to run!