Optimized Combination Function: Part 1

Let me start this blog off by diving into the combination function itself and how we can optimize it for speed. When used within a larger program, it is essential we squeeze as much out of each clock cycle as the main program could be calling this function an enormous amount of time.

In the initial part in this series, I'll jump right in and create an non-optimized algorithm just so we have a base to work against. If you recall, a combination has the following formula:

Condition	Result
r <= n	C(n,r) = n! / r!(n - r)!
n < r	C(n,r) = 0

Let's transform the formula into psuedocode:

Function Factorial(i)
  If i < 0 Then
    Return 0
  End
  j = 1
  While i > 1 Then
    j = j * i
    i = i - 1
  Loop
  Return j
End

Function Combination(n,r)
  If n < r or r < 1 Then
    Return 0
  End
  Return Factorial(n)/(Factorial(r) * Factorial(n-r))
End

Now we have our first combination function written. While it works, it is not the most efficient algorithm, and has some problems when converted to a computer program. So, lets convert it to a 'C' programming language code:

#include <stdio.h>
#include <ctype.h>

long factorial(int i) {
    if( i < 0 )
        return 0L;
    long j = 1L;
    while( i > 1 ) {
        j *= (long)i;
        i--;
    }
    return j;
}

long combination(int n, int r) {
    if( n < r || r < 1 )
        return 0;
    return factorial(n) / (factorial(r) * factorial(n-r));
}

int main(int argc, char **argv) {
    if( argc == 3 ) {
        int n = atoi(argv[1]);
        int r = atoi(argv[2]);
        printf("C(%d,%d) = %ld\n",n,r,combination(n,r));
    }
    return 0;
}

Let's put some values in to verify:

n	r	C(n,r)
12	4	495
10	4	252
8	4	70
6	3	20
8	9	0
-1	-3	0
50	4	0

Hmmmm. Everything looks good, but the last calculation. Can you guess why?

In the next part of this series, we'll find the answer to this question and dive deeper into optimizing the combination function.

Introduction

Welcome to my new blog, which is devoted to discussing mathematical/computational algorithms and how they can be optimized both for resource speed/size and minimizing of cost.