Question

99

Implementation of Luhn algorithm

rated 0 times [ 104] [ 5] / answers: 1 / hits: 37810 / 12 Years ago, fri, september 7, 2012, 12:00:00

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?

Answers

Only authorized users can answer the question. Please sign in first, or register a free account.

kerryoliviaa

Add To Favorites

Follow

Total Points: 221

Total Questions: 102

Total Answers: 117

Location: Sint Maarten

Member since Tue, Mar 29, 2022

2 Years ago

answered 12 Years ago hasanjustusf · Accepted Answer

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.