# Implementing the Luhn Algorithm

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:

- Sum the odd digits (first, third, etc.).
- 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.
- 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.