Parallel algorithms series. Part 1: A little bit about sequential algorithms.

Introduction

If you are reading this post, I am pretty sure that you have already implemented some form of a sequential model. It can be a an algorithm for sorting, a function that returns a fibonacci sequence or something as simple as Adding all the items in a list.
Most of the algorithms that you have come across till now utilizes a single core.
And probably that is not what you are interested in. But to get into parallel algorithms, first look at the machine models that we use for sequential computations.

RAM Model

Lets talk about adding two numbers, each having d = 5 digits
e.g 23568 + 98321
What will be the cost of adding these two numbers ?
For this particular use case , you might have guessed "constant time" and you are probably right.
We have two numbers that can be easily contained in a 64 bit integer and the addition might happen in 1 or 2 operation cycles.

But thing changes if the number itself is too big, and does not fit into the 64bit . In that case, there will be a split, some carryovers and then we will get the result. One can say it depends upon the size the number of digits we are adding.
The analysis of the code will get complex if we start considering these cases as well, hence we need a standard to follow to make things easier for ourselves. Generally, we use RAM Model, a standard for sequential computation.

What is RAM Model then ?
RAM Model or Random Access Model is a machine model that has the following attributes
*Unlimited memory. Any size of input can be accomodated easily in memory cells.

• Fixed amount of registers. Registers are temporary storage sitting next to the processors. They cannot be unlimited, or else why do we even need memory ? Save everything in the registers. Hence, we have limited amount of storage to hold data at a time.
• memory cells and registers can save w size integers (or numbers from 0 to 2^w-1). Here w = logn. The size of integer will increase logarithmically wrt to the number.

In the RAM Model, the total cost is the number of instructions executed. These instructions are

1. Load into registers from memory, and vice versa.
2. Arithematic Operations (+,-, %, *, AND , OR , XOR etc)
3. conditional/unconditional jumps (Those if cases have some cost as well!)

So the next time, when you see a program with n iterations and multiple operations and if-else conditions, you can tell your friends that they aren't wrong, but they aren't right either. Here is an example below

    var i,n, sum int
    fmt.Print("Enter the value of n: ")
    fmt.Scan(&n)
    for i <= n {
        sum += i
        i++
    }
    fmt.Println(sum)

The time complexity here is O(n). But really, its 2n instructions. (add operation on sum and add operation on i).

I am trying to keep the articles short and sweet. In the Next One, we will dive into PRAM Model.