How to refer to "equivalent" algorithms

Question

This is a bit of a "soft question", so if this is not the appropriate place to post, please let me know.

Essentially I'm wondering how to talk about algorithms which are "equivalent" in some sense but "different" in others.

Here is a toy example. Suppose we are given a list of numbers list of length n. Two simple ways to add up the numbers in the list are given below. Obviously these methods are exactly the same in exact arithmetic, but in floating point arithmetic might give different results.

add_list_1(list,n):
    sum = 0
    for i=1,2,...,n:
        sum += list[i]
    return sum

add_list_2(list,n):
    sum = 0
    for i=n,...,2,1:
        sum += list[i]
    return sum

This is a very common thing to happen with numerical algorithms, with Gram-Schmidt vs Modified Gram Schmidt being perhaps the most well known example.

The wikipedia page for algorithms mentions "high level description", "implementation description", and "formal description".

Obviously, the implementation and formal descriptions vary, but a high level description such as "add up the list" is the same for both.

Are these different algorithms, different implementations of the same algorithm, or something else entirely? How would you describe algorithms where the high level level description is the same but the implementation is different when talking about them?

Answer 1

The following definition can be found on the Info for the algorithm tag.

An algorithm is a set of ordered instructions based on a formal language with the following conditions:

Finite. The number of instructions must be finite.

Executable. All instructions must be executable in some language-dependent way, in a finite amount of time.

Considering especially

set of ordered instructions based on a formal language

What this tells us is that the order of the instructions matter. While the outcome of two different algorithms might be the same, it does not imply that the algorithms are the same.

Your example of Gram-Schmidt vs. Modified Gram-Schmidt is an interesting one. Looking at the structure of each algorithm as defined here, these are indeed different algorithms, even on a high level description. The steps are in different orders.

One important distinction you need to make is between a set of instructions and the output set. Here you can find a description of three shortest path algorithms. The set of possible results based on input is the same but they are three very distinct algorithms. And they also have three completely different high level descriptions. To someone who does not care about that though these "do the same" (almost hurts me to write this) and are equivalent.

Another important distinction is the similarity of steps between to algorithms. Let's take your example and write it in a bit more formal notation:

procedure 1 (list, n):
    let sum = 0
    for i = 1 : n
        sum = sum + list[i]
    end for
    sum //using implicit return

procedure 2 (list, n):
    let sum = 0
    for i = n : 1
        sum = sum + list[i]
    end for
    sum //using implicit return

These two pieces of code have the same set of results but the instructions seem differently ordered. Still this is not true on a high level. It depends on how you formalise the procedures. Loops are one of those things that if we reduce them to indices they change our procedure. In this particular case though (as already pointed out in the comments), we can essentially substitute the loop for a more formalised for each loop.

procedure 3 (list):
    let sum = 0
    for each element in list
        sum = sum + element
    end for
    sum

procedure 3 now does the same things as procedure 1 and procedure 2, their result is the same but the instructions again seem different. So the procedures are equivalent algorithms but not the same on the implementation level. They are not the same since the order in which the instructions for summing are executed is different for procedure 1 and procedure 2 and completely ignored in procedure 3 (it depends on your implementation of for each!).

This is where the concepts of a high level description comes in. It is the same for all three algorithms as you already pointed out. The following is from the Wikipedia article you are referring to.

1 High-level description

"...prose to describe an algorithm, ignoring the implementation details. At this level, we do not need to mention how the machine manages its tape or head."

2 Implementation description

"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level, we do not give details of states or transition function."

3 Formal description

Most detailed, "lowest level", gives the Turing machine's "state table".

Keeping this in mind your question really depends on the context it is posed in. All three procedures on a high level are the same:

1. Let sum = 0
2. For every element in list add the element to sum
3. Return sum

We do not care how we go through the list or how we sum, just that we do.

On the implementation level we already see a divergence. The procedures move differently over the "tape" but store the information in the same way. While procedure 1 moves "right" on the tape from a starting position, procedure 2 moves "left" on the tape from the "end" (careful with this because there is no such thing in a TM, it has to be defined with a different state, which we do not use in this level). procedure 3, well it is not defined well enough to make that distinction.

On the low level we need to be very precise. I am not going down to the level of a TM state table thus please accept this rather informal procedure description.

procedure 1:

1. Move right until you hit an unmarked integer or the "end" 
//In an actual TM this would not work, just for simplification I am using ints
    1.e. If you hit the end terminate //(i = n)
2. Record value //(sum += list[i]) (of course this is a lot longer in an actual TM)
3. Go back until you find the first marked number
4. Go to 1.

procedure 2 would be the reverse on instructions 1. and 3., thus they are not the same.

But on these different levels are these procedures equivalent? According to Merriam Webster, I'd say they are on all levels. Their "value" or better their "output" is the same for the same input**. The issue with the communication is that these algorithms, like you already stated in your question return the same making them equivalent but not the same.

You referring to **floating point inaccuracy implies implementation level, on which the two algorithms are already different. As a mathematical model we do not have to worry about floating point inaccuracy because there is no such thing in mathematics (mathematicians live in a "perfect" world).

These algorithms are the different implementation level descriptions of the same high level description. Thus, I would refer to different implementations of the same high level algorithm since the idea is the same.

The last important distinction is the further formalisation of an algorithm by assigning it to a set for its complexity (as pointed out perfectly in the comments by @jdehesa). If you just use big omicron, well... your sets are going to be huge and make more algorithms "equivalent". This is because both merge sort and bubble sort are both members of the set O(n^2) for their time complexity (very unprecise but n^2 is an upper bound for both). Obviously bubble sort is not in O(n*log[2](n)) but this description does not specify that. If we use big theta then bubble and merge sort are not in the same set anymore, context matters. There is more to describing an algorithm than just its steps and that is one more way you can keep in mind to distinguish algorithms.

To sum up: it depends on context, especially who you are talking to. If you are comparing algorithms, make sure that you specify the level you are doing it on. To an amateur saying "add up the list" will be good enough, for your docs use a high level description, when explaining your code explain your implementation of the above high level, and when you really need to formalise your idea before putting it in code use a formal description. Latter will also allow you to prove that your program executes correctly. Of course, nowadays you do not have to write all the states of the underlying TM anymore. When you describe your algorithms, do it in the appropriate form for the setting. And if you have two different implementations of the same high level algorithm just point out the differences on the implementation level (direction of traversal, implementation of summing, format of return values etc.).