I am trying to implement simple validation of credit card numbers. I read about the Luhn algorithm on Wikipedia:
- Counting from the check digit, which is the rightmost, and moving left, double the value of every second digit.
- 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.
- 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 (archived).
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?
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.