Friday, July 25, 2008

Casting Out Nines

I'm working on a project at the moment that involves the verification of credit card numbers. This has led to running checksums on the numbers to validate them including Luhn's algorithm.

Simply stated, Luhn's algorithm doubles every second digit (starting from the right) and then adds together all of those digits which it then mods against 10 to check for success. So if you had the sequence 2568 it would be transformed into 4-5-12-8. You would then add each digit together, the 12 would become 3 (1+2) and not be a 12. So your total is 4+5+1+2+8 = 20. Mod this against ten: 20 % 10 = 0 and if 0 then it passed the test.

In code, when computing the algorithm, you may end up with a 2-digit number after doubling it. Although you could convert it to a string and then convert each digit back to a number to add them together it's easier to subtract 9 from the doubled number which will give you the same result. 12 - 9 = 3 as does 1 + 2 = 3. This, I have just learned is called "Casting Out Nines." Cool term, I like it.

Here is the C# code that I came up with:

int total = 0;
bool even = false;
for (int i = digits.Length - 1; i >= 0; i--)
{
int current = digits[i];
if (even)
{
current *= 2;
if (current > 9)
{
current -= 9; // cast out nines
}
}
total += current;
even = !even;
}