The Σ notation.

*Disclaimer*

Mathematics

In this one, I will talk a bit about the Capital Sigma notation:

You will probably see it being used as follows:

This is actually part of the ~third diagram you will see on its Wikipedia page.

What does it all mean? Here, n represents the upper bound of the summation, m is the lower bound of the summation and i is the index of the summation.

Let's now look at the complete Wikipedia diagram via some inline linking:

As you may have now guessed, the Σ is used to represent a summation (i.e. using addition) over a list of numbers (and other addable entities). The x_i represents how the sequence should be formed, replacing the _i with the current value of i in the present iteration.

Now it should be more clear as to what the upper/lower bounds mean. The upper bound n refers to when the sum should 'end' and m is used to represent where to 'start' the sum.

My terminology in the previous paragraph may be slightly incorrect, especially the part about start/end, so be weary.

If you've managed to get that, here's a more concrete example:

And another one:

You could have probably calculated the above in your head, but what if I gave you the following:

Can you find the sum of the numbers in the range 1 ≤ i ≤ 50 mentally? Fortunately, you don't have to because there is a formula you can use for that particular sequence of numbers:

So going back to the previous problem with the 50, we can now plug in the upper bound into the formula:

Therefore:

Let's get a bit more concrete. Say you have some coins running around and you form a triangle with them:

Without individually counting them, can you tell me the total number of coins that are currently forming the triangle? Or better yet, what if you added the fifth row...how many coins would there be then?

Simple, just use the formula. Let's find out how many coins would there be if we added the fifth row.

First we'll start by representing our problem in math notation which in this case is easy because the pattern is very trivial:

And now, the formula:

So if we add a fifth row, we would get a total of 15 coins:

---

How about this one?

Well thankfully, mathematicians also have a formula for that (and many others):

So, applying that to our latest problem, we get:

Therefore:

Programming

Now, some programming shall we? I will use JavaScript because I like it (talk about one hammer...well it's not the only one) although I have to admit that a solution written in a purely functional programming language like Haskell would have been much more elegant.

Now let's start applying this function to work out some summations, starting with the first one I talked about:

We can write something like this to workout the problems given with that pattern:

var simpleSum = function(upper) {
  return (upper * (upper + 1)) / 2;
};

What about the next one?

Something like this could work:

var squaredSum = function(upper) {
  var numerator = upper * (upper + 1) * (2 * upper + 1), 
      denominator = 6;
  
  return numerator / denominator;
};

But do we have to keep creating a new function for every pattern we need? Surely not!

We can write a function that does something like this:

If you're worried about the stack, you can use a for loop:

var sum = function (pattern, lower, upper) {
  var s = 0;
  
  for (; lower <= upper; ++lower) {
    s += pattern(lower, upper);
  }
  
  return s;
};

But you can also use recursion to create a more elegant solution:

var sum = function(pattern, lower, upper) {
  if (lower > upper)
    return 0;
  return pattern(lower, upper) + sum(lower + 1, upper, pattern);
};

As you can see, I kept it as concise as possible; I even didn't bother to add curly brackets for the if-construct. If you're hardcore on making slightly-less readable code, you can even remove that if-construct and check for the condition using the ternary operator.

I also added the possibility to start from a specified number given by the lower variable. The generic function comes with a price though, as everything does. The problem now is that we've transformed an algorithm of O(1) to one with O(n).

I will not go much into algorithm complexity in this post but basically with our previous 'simpler' functions, the execution time of the function depended mainly on how complex our formula was since all it's operation run in constant time, whereas with the new generic function, we will take a big performance hit because execution time depends mainly on the range of numbers we specify i.e. the bigger the range, the more time the function will take to return a result.

Another way to say this would be that the execution time scales proportionally to the number of elements in the specified range m...n.

Let us now apply the last function to create the previous two patterns:

var m = 1, n = 5;

sum(function (i) { 
    return i; 
}, m, n);

sum(function (i) {
    return i * i
}, m, n);

Now we can also write something like this:

sum(function(i) {
  return Math.pow(i, 5);
}, m, n);

If we wanted to write it using the O(1) algorithm, we would have had to turn the formula into JavaScript instead of using the i⁵. But, we can even up the ante a bit and make all of this even cooler and that's where partial function application will come in to do the job. This is the partial function we will use:

var partial = function(func) {
  var args = Array.prototype.slice.call(arguments).splice(1);
  return function() {
    var allArguments = args.concat(Array.prototype.slice.call(arguments));
    return func.apply(this, allArguments);
  };
};

I have already talked about partial function application for JavaScript in the other one so I won't go into any details here, but I will show you how we can use it to produce functions that have a smaller arity (number of arguments):

var simpleSum = partial(sum, function (i) { return i; }),
    squaredSum = partial(sum, function (i) { return i*i;});

In our current case, we reduced the arity of sum to produce functions that only require the lower and upper bounds since the pattern function will already be stored in the closure produced by the partial function. Usage is then simple:

simpleSum(1,5);  // 15
squaredSum(1,5); // 55