What algorithm to use to calculate a check digit?
Solution 1
The Luhn algorithm is good enough for the credit card industry...
Solution 2
As RichieHindle points out, the Luhn algorithm is pretty good. It will detect (but not correct) any one error or transposition (except a transposition of 0 and 9).
You could also consider the algorithm for ISBN check digits, although for old-style ISBN, the check digit is sometimes "X", which may be a problem for you if you're using integer fields. New-style ISBN doesn't seem to have that problem. Wikipedia doesn't go in to the theoretical properties of the system, but I remember studying ISBN numbers in my coding theory course long ago, so I think they are pretty good :-)
Solution 3
I know it is a bit late (according to post dates), but first time I needed a check number algorithm was last week.
So I checked more algorithms and IMHO the best solution seems to be the Damm algorithm. It is simple to implementation and detect most of tested errors. With default digit check table all single digit errors, all English language mishearing errors, all adjacent transposition errors, and almost all jump transpositions errors are detectable.
For me there was only a single problem, since I need to calculate check digit not only from numbers but also from characters. Unfortunately for me, there was a given rule, that the last character must be a digit; or better to say, the characters were assigned by third party authority and only fixed amount of numbers were used as manufacturer number.
There are many ways how to transcribe characters to number, but the error detection will always be lower, comparing to when only numbers are used.
For these cases you can use the ISO_6346 specification.
When there is no such limitation, use the tables for different size and assign characters and number to table values.
EDIT: updated/fixed description, added reason for digit check number for characters, and added tables for different base sizes.
Comments
-
Piotr Dobrogost almost 2 years
What algorithm to use to calculate a check digit for a list of digits?
The length of the list is between 8 and 12 digits. -
Alix Axel over 14 yearsLuhn algorithm is way to weak, try swapping the first digit with the last digit - ooops, valid!
-
Jaymelson Galang over 8 years@AlixAxel It may be true that swapping of first and last will result to valid but the whole idea of Luhn Algorithm is just to prevent/to lessen user input error. Meaning, if the end-user inputs a wrong 16 digit number of the customer account number it has 10% (more or less) chance to be valid. But still its more accurate to validate the other detail like Account Name along with the account number if it much the data in the database. -
Jaymelson Galang over 8 years@AlixAxel Wiki meaning of Luhn Algo or check digit - designed to protect against accidental errors, not malicious attacks.
-
MsBao over 7 yearsWhy is there nothing better? What properties does this algorithm have that others do not?
-
jswolf19 about 4 yearsI don't believe th Damm algorithm is limited to only digits. A larger table should be able to be generated with the required properties. You can then convert non-numeric values to a numeric equivalent (A = 10, B = 11, ...) and perform the algorithm with the caveat that any valid character in the input string is a valid value for the check digit.
-
jswolf19 about 4 yearsTables handling up to 64 values are linked from Wikipedia (md-software.de/math/DAMM_Quasigruppen.txt)
-
Julo about 4 years@jswolf19: You are right. I already found the tables long ago, but I did forget that this answer stated 'only digits' and therefore forgot to update the answer. But in my case (the need to implement check digit) was limited to digit, so I did not search it at that time. The answer is already updated. And the transcription (A=10, B=11...) is part of ISO_6346, but the results were not good. I tested it and at least one tested misspelling (different character), or transposition error was not detected.
