October 26, 2010

Simplest Credit Card Validator

Searching for a simple credit card validation algorithm? The Luhn algorithm is a simple checksum that validates most identification numbers, mainly used in credit card ones. It's implementation is quite simple. Need one? Just come along!

This algorithm, written by IBM scientist Hans Peter Luhn in the early 50's, works at the digit level. Every even position (from right to left) doubles it's value, then a modulo 9 is applied to them. Finally, all the digits are added together. If the result modulo 10 equals 0, the initial number is correct.

Our first approach:

function checkCardNumber($cardNumber)
{
    $sum = 0;
    $even = true;
    for ($i = strlen($cardNumber) - 1; $i >= 0; --$i, $even = !$even) {
        $n = $cardNumber[$i];
        if ($even) {
            $n = ($n * 2) % 9;
        }
        $sum += $n;
    }
    return $sum % 10 === 0;
}

Not bad, uh? IMHO, even better than the one on wikipedia :)

But even in simple things like this little one, there's some room for improvement. Let's have a look at the ($n * 2) % 9 table of results:

01234 56789
02468 13579

As the next step is to calc module 10, we can modify the previous table adding 10 anytime we want and this will not change the results. Have a look to the next table, where I added 10 to every digit greater than 4:

01234 56789
02468 1113151719

This table can be seen as the next one:

01234 56789
(2*0)(2*1)(2*2)(2*3)(2*4) (2*5)+1(2*6)+1(2*7)+1(2*8)+1(2*9)+1

So every even digit can be replaced by (2 * $n) + ($n > 4). As every odd digit maintains it's value, the final expression is $n + ($odd ? $n + ($n > 4) : 0). Now the code:

function checkCardNumber($cardNumber)
{
    $sum  = 0;
    $even = false;
    for ($i = strlen($cardNumber) - 1; $i >= 0; --$i, $even = !$even) {
        $n    = $cardNumber[$i];
        $sum += $n + ($even ? $n + ($n > 4) : 0);
    }
    return $sum % 10 === 0;
}

The compressed code even fits in a tweet!

for($i=strlen($c)-1,$e=$s=0;$i>=0;--$i,$e=!$e){$n=$c[$i];$s+=$n+($e?$n+($n>4):0);}return $s%10===0;