Implementing the Luhn Algorithm

2011-02-17

In my previous professional life, I processed a lot of credit card numbers. When reading credit card numbers from an unknown source, it helps to have a fast way of checking basic validity — to filter out bogus input. Such a method exists: the Luhn algorithm. I developed a very fast implementation of the algorithm a few years ago, and I keep seeing it pop up other places.

This algorithm is a family tradition: my parents both work in the credit card industry, and my dad had developed a fast implementation years ago. I refined it into what you see here back in 2005, and posted it on my then-blog.

The Luhn algorithm dates back to before the information age. Like algorithms of yore, it was designed to be evaluated not by a computer, but by a person. When accepting a credit card in person or over the phone, a person can work through these steps to ensure that the number is not incorrect or transposed:

1. Sum the odd digits (first, third, etc.).
2. Take each even digit and double it. If the result is more than 10, add the digits of the result together. Then, add all the doubled-summed values together.
3. Make sure the result is evenly divisible by ten.

This is pretty easy for a person, but computers don’t deal well with base-10 digits. It’s easy to create a slow implementation of the Luhn algorithm.

Most systems store credit cards as ASCII digits, one byte per digit. My dad’s implementation avoided the double-and-sum stage by precomputing:

int doubled_and_summed[10] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };

My implementation goes a step farther. The idea: sum all the digits, and then apply a correction factor to fix the even ones. Here’s an implementation in C:

int double_sum_delta[10] = { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };

bool luhn_check(const char *ccnum, size_t len) {
  int sum = 0;
  for (size_t i = 0; i < len; i++) {
    sum += ccnum[i] - '0';
  }
  for (size_t i = 1; i < len; i += 2) {
    sum += double_sum_delta[ccnum[i] - '0'];
  }
  return (sum % 10) == 0;
}

Depending on your compiler and target processor, it may be faster to replace the two inner loops with one:

for (size_t i = 0; i < len; i++) {
  int d = ccnum[i] - '0';
  sum += d;
  if (i & 1) {
    sum += double_sum_delta[d];
  }
}

Similarly, if your compiler is bad at strength reduction, you may be able to nudge the - '0' around to improve throughput.

This implementation works with 15- and 16-digit card numbers, but doesn’t handle invalid input, such as letters or whitespace. In particular, for folks storing credit card numbers in a SQL CHAR(16) field, it won’t handle a 15-digit number with a trailing space. I leave input validation as an exercise for the reader.

#algorithm #software