Talk:Luhn algorithm

From Wikipedia, the free encyclopedia

Contents 1 Patent 2950048 2 No longer valid? 3 Created/Adopted When? 4 Resolved Discussions 4.1 First Comment (Untitled) 4.2 Strengths/Weaknesses 4.3 The Pseudocode Is Wrong 4.4 Computing the check digit 4.5 Comments on Changes 5 Fixed Algorithm Section 6 Removal of VB and PHP Algorithms 7 Algorithms 8 Mathematica implementation

[edit] Patent 2950048

http://www.pat2pdf.org/patents/pat2950048.pdf [1]

Page 4, Point 20 ~ 25

With numbers that result in 10 or greater are added together, not subtract 9. However when you are write computer code minus 9 is normally used.

[edit] No longer valid?

Is this algorithm no longer valid? There are now VISA cards in circulation that fail this test but are legitimate cards.

[edit] Created/Adopted When?

The article states that the formula was adopted by credit card companies "late 1960s". But Luhn died in 1964, so wasn't creating much in the late 1960s. I suspect it's just a dangling modifier, and it should probably say that it was adopted in the late 1960s, shortly (or perhaps "not long", or "a few years") after its creation. However, without knowing the specifics of when it was created and when it was adopted, I'm not sure how to re-write. Darguz Parsilvan 6 July 2005 12:12 (UTC)

[edit] Resolved Discussions

[edit] First Comment (Untitled)

When converting every other digits (e.g. 8 -> 16 -> 7), the doubling step helps check for people who accidentally swapped adjacent digits (e.g. 1234->1243). But what's rationale behind converting 16 to 7?

My guess is that it keeps the overall numbers smaller, keeping things down to single check digits at each iteration.

[edit] Strengths/Weaknesses

The Luhn formula will catch any single-digit error. It will also catch almost any transposition of adjacent digits (e.g., 18 <-> 81). There is one adjacent-digit transposition that Luhn will not catch: 09 <-> 90. It would be a prudent step for applications using Luhn to refrain from issuing numbers with 09 and/or 90 in them, so that this particular transposition cannot result in another valid number. The Verhoeff check digit formula (not currently described in Wikipedia) might be a better choice, since it catches all adjacent-digit transposition errors. Richwales 21:17, 14 April 2006 (UTC)

The Verhoeff algorithm is described now. Richwales 00:06, 20 April 2006 (UTC)

[edit] The Pseudocode Is Wrong

The given pseudocode is incorrect. The for loop must iterate from 0 to (nDigits - 1), not to nDigits. Iterating to the length of a zero-based array will exceed the upper bound of the array. For example, an array Arr[] of only one element has a length of 1, but the only valid entry is Arr[0]. The loop presented would attempt to check both Arr[0] and Arr[1], exceeding the upper bound of the array. In memory-managed environments this will generate a runtime error; in C, it's interesting pointer arithmetic resulting in the inclusion of a more-or-less random memory location as an unintended digit of the number being checked. A good compiler may catch the error.

Also, the general purpose of pseudocode is to be illustrative. As such, it would be more informative to use modulus 2 in place of AND 1. AND 1 is a programming optimization which exploits a bitwise AND to perform the same logical operation as modulus 2. AND 1 is used in programming solely because it generally compiles to faster executable code than does modulus 2. However, speed optimization is rarely the point of pseudocode. The use of modulus 2 would relate the pseudocode more directly to the informal discussion in the article, and make the pseudocode easier to follow for a more general audience.

You are absolutely right, and indeed argue with too much force; both seem clearly good changes to me. I also changed XOR to ≠. The result seems a lot simpler. In the future I encourage you to be bold and make changes yourself, as well as leave a note on the talk page, if you wish. Deco 06:26, 7 Jan 2005 (UTC)

Woah now, isn't the pseudo code supposed to go from nDigits - 1 down to 0? This is the first I've read the algorithm, and the words don't match the code. If I was sure which was correct I'd fix it. --Nofxjunkee 17:21, 20 September 2006 (UTC)

You are correct. According to Vital (Now TSYS) the wording is correct and the pseudo-code is wrong. I have recommended that it be changed. Have to be careful though in how you word the for loop cause not all languages implement for the same. While loops may be safer and more language independant. --dmprantz 17 October 2006 (UTC)

[edit] Computing the check digit

The algorithm stated checks if a number is valid according to the Luhn algorithm, but does anyone have an algorithm that computes a Luhn check digit, i. e. modifies an existing number by appending a digit so that the result is Luhn valid? I mean, something smarter than trying the ten possible digits until the matching one is found. - wr 10-oct-2006

Agreed, but the code for this would be so similar to the CreateNumber example as to get repetitive (based on idea that this is not code repository). Would it be more relevant to replace CreateNumber with GetCheckDigit? Probably best to just go with one or the other. Would be happy to post calc function if deemed more relevant than existing CreatNumber. Skratowicz 03:31, 29 June 2007 (UTC)

[edit] Comments on Changes

This article was just plain wrong in the way it was worded. It talked about "calculating" a checksum digit, but explained how to VERIFY a checksum digit. Two slightly different tasks. I changed the text to match the algorithm since that is the most commonly used purpose. I tried to remove everything that didn't make sense. If some one really wants to add back in an area for calculating the checksum digit, by all means do so, but please be precise and clear.

Responses to various Talk Topics:

Computing the check digit is a simple excercise of mathematics, and a well written Luhn Algorithm will be able to do it with little stress. Implementation is left as an excersize.

The Mod 10 (Luhn) algorithm is very much valid. If you know of any Visa numbers that do not pass it, please elaborate, but my business depends on it, and there is no notice of which I am aware which depricates this algorithm.

The current state of the pseudocode is still wrong IMHO, and at least one other person agrees. The algorithm, as it is stated, goes from the end to the beginning, so make the pseudo-code loop go from the end to the beginning. Don't ever bother checking for this parity value that only stands to confuse the reader....if the pseudo-code goes from right to left with if statements, restate the algorithm to do the same. I have seen far too many implementations that take this crazy turn:( Also, ADD SOME CURLY BRACES!!!! Allow me to paraphrase Larry Wall: "Even if you aren't in doubt, consider the mental welfare of the person who has to read the code after you, and who will probably put braces in the wrong place."

Before any one tells me to be bold, please don't. Mod 10 is part of my business. As much as I would like to help the world understand the algorithm, I cannot share my knowledge without giving away my business' IP. I am glad to remove inaccuracies and to point others in the right direction, but creation of any specific code (pseudo or real) can get me into trouble. Sorry. :( --dmprantz 17 October 2006 (UTC)

[edit] Fixed Algorithm Section

I rewrote the algorithm and included a complementary one. I use a boolean flag instead of a mod 2 or and 1 to make the code simpler and more similar to the text. Feedback? ZX2C4 08:14, 6 January 2007 (UTC)

I'd like to make some changes. The PHP algorithm calls the digits to be double Luhn Digits. In the original patent, Luhn calls them substitution digits. Also in this algorithm, I think it is odd to convert the subsitution digit to a string just to find out that its ten's digit is one. We know that. The C# algorithm is more direct on this. Concerning the C# alternating flag thing, well, since taking a number mod 2 is (or should be) implemented as bit-wise AND with 1, I would stick w/ mod 2. It's clearer what's going on, the code is all in one place, and it might be even faster in use. But I will differ to the person who took the time to write this excellent code.

Finally, as for creating the check digit, I don't think that code is what we want. The question is: what digit should I add to a particular number? If we assume that we will get a k digit number, and will add the check-digit as the least-significant number and return a k+1 digit number. --Ozga 14:42, 14 December 2006 (UTC) --Ozga 14:36, 24 August 2007 (UTC)

I think if you factor your equation above and adjust for the modulo implementation I use, you'll come up the same thing, unless you are mistaken. I have double checked the last part of the algorithm. Essentially the algorithm figures out what the Luhn sum would be for the number sequence with out the check number. Then it determines what mod 10 of that number is. If mod 10 is 0, then the number already passes, so the check is 0. Otherwise, a value needs to be added so that the sum + check mod 10 will be zero. Therefore, we do 10 minus the sum mod 10 to determine the check digit. If you're unhappy with the logical defense of last step, you can observe it empirically by compiling the test program here: [2]. I have added a new section below regarding the improper addition of the php and vb algorithms. ZX2C4 08:14, 6 January 2007 (UTC)

I agree with the math, and apologize if it seemed like I didn't acknowledge the correctness of your algorithm. What I meant was, to present code that takes as argument a string of digits that lacks a checksum digit, and returns that string with the appropriate digit appended so the result passes the checksum, or some similar functionality. --Ozga 04:53, 26 May 2007 (UTC)

[edit] Removal of VB and PHP Algorithms

The VB/VB.net algorithm was not valid vb.net. Both algorithms introduced extraneous complexities that utilize more concepts than necessary to demonstrate the Luhn algorithm. Wikipedia is an encyclopedia, not a code repository, and for this reason, these two extra algorithms have been removed. The C# algorithm is the most straightforward and does not introduce unnecessary concepts. The C# algorithm is also consistent in its coding to the following algorithm that generates Luhn sequences. ZX2C4 08:05, 6 January 2007 (UTC)

[edit] Algorithms

Many people must be interested in links to the algorithms! As a compromise, let's just keep them on the discussion page, shall we? PLEASE don't delete these! Most of us don't care for C#! Paperweight 21:18, 28 February 2007 (UTC)

I've moved these links to a section on the main page, complying with the compromise. --ZX2C4

[edit] Mathematica implementation

Still missing this one :) LuhnCheck[n_] := Module[{digits = IntegerDigits[n]}, For[i = Length[digits] - 1, i >= 1, i -= 2, digits[[i]] = FixedPoint[Composition[Total, IntegerDigits], 2*digits[[i]]]]; Mod[Total[digits], 10] == 0 ] 11:42, 28 December 2007 (UTC)