Talk:Verhoeff algorithm
![]() | Mathematics C‑class Low‑priority | |||||||||
|
![]() | Computing Unassessed | |||||||||
|
Is this algorithm correct?
According to [1], 3170092 is also a valid number.
Using the algorithm here, that becomes:
i | ni | p(i,ni) | previous c | new c = d(c,p(i,ni)) |
---|---|---|---|---|
0 | 2 | 2 | 0 | 2 |
1 | 9 | 4 | 2 | 1 |
2 | 0 | 5 | 1 | 6 |
3 | 0 | 8 | 6 | 3 |
4 | 7 | 8 | 3 | 6 |
5 | 1 | 2 | 6 | 9 |
6 | 3 | 3 | 9 | 6 |
Which one is incorrect? The wikiarticle? The other article? The fact that 3170092 is a valid number? Or have I made a mistake?
- As best I can tell, the Marist College article you cited is wrong. The position-based permutation which Verhoeff settled on (the p table) is not a simple exponential of the group multiplication (the d table), as the article you found claims.
- My understanding (from the first reference in the Wikipedia article) is that Verhoeff experimented with many different permutations before coming up with one that worked particularly well. A simple exponential permutation would actually be atrociously bad, since multiplication in the dihedral group contains two cycles of period 2 — namely, (14) and (23) — and one cycle of period 1 — namely, (0).
195.224.169.69 19:29, 26 September 2006 (UTC) Thanks for the information.
- (A few years later...)
- 3170092 is given as an example of valid number in Kirtland, Joseph (2001): Identification Numbers and Check Digit Schemes (see the exact reference in the article).
- From superficial reading, it looks like Kirtland and the Wikipedia article actually use 2 different variants of the Verhoeff algorithm, so no wonder a number accepted by Kirtland is refused by Wikipedia. The difference lies in table p: while the Wikipedia article uses powers of permutation (1 5 8 9 4 2 7 0)(3 6), Kirtland uses powers of (0) (1 4) (2 3) (5 6 7 8 9). (Also, they might apply the powers in a different direction to the digits: right-to-left for Kirtland, left-to-right for Wikipedia, I haven't checked yet.) The algorithm in the Wikipedia article is probably the one used by the German Bundesbank from 1990 to (2002?) for banknote serial numbers. (Actually, Kirtland also does mention the German Bundesbank and its permutation, in a final short note.) --FvdP (talk) 20:50, 20 August 2012 (UTC)
I don't understand the following description:
"The involved nature of the Verhoeff check might especially be seen as a drawback if the client applications within a system need to explicitly identify ID's that fail the check digit test. If it is sufficient for a client to look up each ID in a master database and report malformed values as "not found," then only the piece of the system that issues new ID's needs to know how to do the Verhoeff calculations, and the complexity issue is mitigated."
Can someone more knowledgable try to explain it better? The first sentence sounds like the reason why to use a check digit in the first place. 193.12.151.160 (talk) —Preceding comment was added at 16:27, 7 March 2008 (UTC)
- I added some explanation which I hope will take care of this issue. The point is that if all a client application needs to be told is that a given ID is not found in the system, there is no need for the client app to do the check-digit calculations itself; it will simply do a lookup using the malformed ID, and it won't match anything. However, if it is decided that a client application needs to be able to explicitly say that a given ID has failed the check-digit test and must have been garbled somehow, then the client would naturally need to have the necessary smarts to do the check-digit calculations on the ID before trying to do a lookup. Richwales (talk) 19:55, 7 March 2008 (UTC)