# 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.