Implementation of Luhn algorithm

Question

I am trying to implement simple validation of credit card numbers. I read about the Luhn algorithm on Wikipedia:

1. Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
2. Sum the digits of the products (e.g., 10: 1 + 0 = 1, 14: 1 + 4 = 5) together with the undoubled digits from the original number.
3. If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.

On Wikipedia, the description of the Luhn algorithm is very easily understood. However, I have also seen other implementations of the Luhn algorithm on Rosetta Code and elsewhere.

Those implementations work very well, but I am confused about why they can use an array to do the work. The array they use seems to have no relation with Luhn algorithm, and I can't see how they achieve the steps described on Wikipedia.

Why are they using arrays? What is the significance of them, and how are they used to implement the algorithm as described by Wikipedia?

Answer 1

Compact Luhn validator:

var luhn_validate = function(imei){
    return !/^\d+$/.test(imei) || (imei.split('').reduce(function(sum, d, n){ 
            return n===(imei.length-1)
                   ? 0 
                   : sum + parseInt((n%2)? d: [0,2,4,6,8,1,3,5,7,9][d]);
        }, 0)) % 10 == 0;
};

Works fine for both CC and IMEI numbers. Fiddle: http://jsfiddle.net/8VqpN/

Answer 2

I worked out the following solution after I submitted a much worse one for a test..

function valid(number){
    var splitNumber = parseInt(number.toString().split(""));
    var totalEvenValue = 0;
    var totalOddValue = 0;
    for(var i = 0; i < splitNumber.length; i++){
        if(i % 2 === 0){
            if(splitNumber[i] * 2 >= 10){
                totalEvenValue += splitNumber[i] * 2 - 9;
            } else {
                totalEvenValue += splitNumber[i] * 2;
            }
        }else {
            totalOddValue += splitNumber[i];
        }
    }
    return ((totalEvenValue + totalOddValue) %10 === 0)
}
console.log(valid(41111111111111111));

Answer 3

Lookup tables or arrays can simplify algorithm implementations - save many lines of code - and with that increase performance... if the calculation of the lookup index is simple - or simpler - and the array's memory footprint is affordable.

On the other hand, understanding how the particular lookup array or data structure came to be can at times be quite difficult, because the related algorithm implementation may look - at first sight - quite different from the original algorithm specification or description.

Indication to use lookup tables are number oriented algorithms with simple arithmetics, simple comparisons, and equally structured repetition patterns - and of course - of quite finite value sets.

The many answers in this thread go for different lookup tables and with that for different algorithms to implement the very same Luhn algorithm. Most implementations use the lookup array to avoid the cumbersome figuring out of the value for doubled digits:

var   luhnArr   =   [0,   2,   4,   6,   8,   1,   3,   5,   7,   9];
//
//                   ^    ^    ^    ^    ^    ^    ^    ^    ^    ^
//                   |    |    |    |    |    |    |    |    |    |
//
// - d-igit=index:   0    1    2    3    4    5    6    7    8    9
// - 1st 
//    calculation: 2*0  2*2  2*2  2*3  2*4  2*5  2*6  2*7  2*8  2*9 
// - intermeduate
//          value: = 0  = 2  = 4  = 6  = 8  =10  =12  =14  =16  =18
// - 2nd
//    calculation:                          1+0  1+2  1+4  1+6  1+8
//
// - final value:    0    2    4    6    8   =1   =3   =5   =7   =9
//       
var luhnFinalValue = luhnArray[d]; // d is numeric value of digit to double

An equal implementation for getting the luhnFinalValue looks like this:

var luhnIntermediateValue = d * 2; // d is numeric value of digit to double
var luhnFinalValue = (luhnIntermediateValue < 10)
        ? luhnIntermediateValue           // (d    ) * 2;
        : luhnIntermediateValue - 10 + 1; // (d - 5) * 2 + 1;

Which - with the comments in above true and false terms - is of course simplified:

var luhnFinalValue = (d < 5) ? d : (d - 5) * 2 + 1;

Now I'm not sure if I 'saved' anything at all... ;-) especially thanks the value-formed or short form of if-then-else. Without it, the code may look like this - with 'orderly' blocks and embedded in the next higher context layer of the algorithm and therefore luhnValue:

var luhnValue; // card number is valid when luhn values for each digit modulo 10 is 0

if (even) { // even as n-th digit from the the end of the string of digits
    luhnValue = d;
} else { // doubled digits
    if (d < 5) {
        luhnValue = d * 2;
    } else {
        lunnValue = (d - 5) * 2 + 1;
    }
}

Or:

var luhnValue = (even) ? d : (d < 5) ? d * 2 : (d - 5) * 2 + 1;

Btw, with modern, optimizing interpreters and (just in time) compilers, the difference is only in the source code and matters only for readability.

Having come that far with explanation - and 'justification' - of the use of lookup tables and comparison to straight forward coding, the lookup table looks now a bit overkill to me. The algorithm without is now quite easy to finish - and it looks pretty compact too:

function luhnValid(cardNo) { // cardNo as a string w/ digits only
    var sum = 0, even = false;
    cardNo.split("").reverse().forEach(function(dstr){ d = parseInt(dstr);
        sum += ((even = !even) ? d : (d < 5) ? d * 2 : (d - 5) * 2 + 1);
      });
    return (sum % 10 == 0);
  }

What strikes me after going through the explanation exercise is that the initially most enticing implementation - the one using reduce() from @kalypto - just lost totally its luster for me... not only because it is faulty on several levels, but more so because it shows that bells and whistles may not always 'ring the victory bell'. But thank you, @kalypto, it made me actually use - and understand - reduce():

function luhnValid2(cardNo) { // cardNo as a string w/ digits only
    var d = 0, e = false; // e = even = n-th digit counted from the end
    return ( cardNo.split("").reverse().reduce(
                 function(s,dstr){ d = parseInt(dstr); // reduce arg-0 - callback fnc
                     return (s + ((e = !e) ? d : [0,2,4,6,8,1,3,5,7,9][d]));
                   } // /end of callback fnc
                ,0 // reduce arg-1 - prev value for first iteration (sum)
                ) % 10 == 0
           );
  }

To be true to this thread, some more lookup table options have to be mentioned:

• how about just adjust varues for doubled digits - as posted by @yngum
• how about just everything with lookup tables - as posted by @Simon_Weaver - where also the values for the non-doubled digits are taken from a look up table.
• how about just everything with just ONE lookup table - as inspired by the use of an offset as done in the extensively discussed luhnValid() function.

The code for the latter - using reduce - may look like this:

function luhnValid3(cardNo) { // cardNo as a string w/ digits only
    var d = 0, e = false; // e = even = n-th digit counted from the end
    return ( cardNo.split("").reverse().reduce(
          function(s,dstr){ d = parseInt(dstr);
              return (s + [0,1,2,3,4,5,6,7,8,9,0,2,4,6,8,1,3,5,7,9][d+((e=!e)?0:10)]);
            }
         ,0
         ) % 10 == 0
      );
  }

And for closing lunValid4() - very compact - and using just 'old fashioned' (compatible) JavaScript - with one single lookup table:

function luhnValid4(cardNo) { // cardNo as a string w/ digits only
  var s = 0, e = false, p = cardNo.length; while (p > 0) { p--;
    s += "01234567890246813579".charAt(cardNo.charAt(p)*1 + ((e=!e)?0:10)) * 1; }
  return (s % 10 == 0);
 }

Corollar: Strings can be looked at as lookup tables of characters... ;-)

A perfect example of a nice lookup table application is the counting of set bits in bits lists - bits set in a a (very) long 8-bit byte string in (an interpreted) high-level language (where any bit operations are quite expensive). The lookup table has 256 entries. Each entry contains the number of bits set in an unsigned 8-bit integer equal to the index of the entry. Iterating through the string and taking the unsigned 8-bit byte equal value to access the number of bits for that byte from the lookup table. Even for low-level language - such as assembler / machine code - the lookup table is the way to go... especially in an environment, where the microcode (instruction) can handle multiple bytes up to 256 or more in an (single CISC) instruction.

Some notes:

• numberString * 1 and parseInt(numberStr) do about the same.
• there are some superfluous indentations, parenthesis,etc... supporting my brain in getting the semantics quicker... but some that I wanted to leave out, are actually required... when it comes to arithmetic operations with short-form, value-if-then-else expressions as terms.
• some formatting may look new to you; for examples, I use the continuation comma with the continuation on the same line as the continuation, and I 'close' things - half a tab - indented to the 'opening' item.
• All formatting is all done for the human, not the computer... 'it' does care less.

algorithm datastructure luhn lookuptable creditcard validation bitlist

Answer 4

Alternative ;) Simple and Best

  <script>
      // takes the form field value and returns true on valid number
    function valid_credit_card(value) {
      // accept only digits, dashes or spaces
        if (/[^0-9-\s]+/.test(value)) return false;

        // The Luhn Algorithm. It's so pretty.
        var nCheck = 0, nDigit = 0, bEven = false;
        value = value.replace(/\D/g, "");

        for (var n = value.length - 1; n >= 0; n--) {
            var cDigit = value.charAt(n),
                  nDigit = parseInt(cDigit, 10);

            if (bEven) {
                if ((nDigit *= 2) > 9) nDigit -= 9;
            }

            nCheck += nDigit;
            bEven = !bEven;
        }

        return (nCheck % 10) == 0;
    }

    console.log(valid_credit_card("5610591081018250"),"valid_credit_card Validation");
  </script>

Best Solution here

• http://plnkr.co/edit/34aR8NUpaKRCYpgnfUbK?p=preview

with all test cases passed according to

• http://www.paypalobjects.com/en_US/vhelp/paypalmanager_help/credit_card_numbers.htm

and the credit goes to

• https://gist.github.com/DiegoSalazar/4075533

Answer 5

the array [0,1,2,3,4,-4,-3,-2,-1,0] is used as a look up array for finding the difference between a number in 0-9 and the digit sum of 2 times its value. For example, for number 8, the difference between 8 and (2*8) = 16 -> 1+6 = 7 is 7-8 = -1.

Here is graphical presentation, where {n} stand for sum of digit of n

[{0*2}-0, {1*2}-1, {2*2}-2, {3*2}-3, {4*2}-4, {5*2}-5, {6*2}-6, {7*2}-7....]
   |       |        |         |        |        |       |         |  
[  0  ,    1    ,   2    ,    3  ,     4   ,   -4  ,   -3   ,    -2  ....] 

The algorithm you listed just sum over all the digit and for each even spot digit, look up the the difference using the array, and apply it to the total sum.

Answer 6

If you want to calculate the checksum, this code from this page is very concise and in my random tests seems to work.

NOTE: the verification algorithmns on this page do NOT all work.

// Javascript
String.prototype.luhnGet = function()
{
    var luhnArr = [[0,1,2,3,4,5,6,7,8,9],[0,2,4,6,8,1,3,5,7,9]], sum = 0;
    this.replace(/\D+/g,"").replace(/[\d]/g, function(c, p, o){
        sum += luhnArr[ (o.length-p)&1 ][ parseInt(c,10) ]
    });
    return this + ((10 - sum%10)%10);
};

alert("54511187504546384725".luhnGet());​

Here's my findings for C#