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 = ;
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 = ; bool
Depending on your compiler and target processor, it may be faster to replace the two inner loops with one:
Similarly, if your compiler is bad at strength reduction, you may be able to
- '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