...
Our variation on the Luhn algorithm
Allowing for Letters
We have borrowed the variation on the Luhn algorithm used by Regenstrief Institute, Inc. In this variation, we allow for letters as well as numbers in the identifier (i.e., alphanumeric identifiers). This allows for an identifier like "139MT" that the original Luhn algorithm cannot handle (it's limited to numeric digits only).
...
To handle alphanumeric digits (numbers and letters), we actually use the ASCII value (the computer's internal code) for each character and subtract 48 to derive the "digit" used in the Luhn algorithm. We subtract 48 because the characters "0" through "9" are assigned values 48 to 57 in the ASCII table. Subtracting 48 lets the characters "0" to "9" assume the values 0 to 9 we'd expect. The letters "A" through "Z" are values 65 to 90 in the ASCII table (and become values 17 to 42 in our algorithm after subtracting 48). To keep life simple, we convert identifiers to uppercase and remove any spaces before applying the algorithm.
Here's how we handle non-numeric characters
For the second-to-last (2nd from the right) character and every other (even-positioned) character moving to the left, we just add 'ASCII value - 48' to the running total. The Luhn CheckDigit Validator uses this variation to allow for letters, whereas the Luhn Mod-10 Check-Digit Validator uses the standard Luhn Algorithm using only numbers 0-9.
Mod 25 and Mod 30
The idgen module supports additional algorithms, including Mod25 and Mod30 algorithms. These algorithms not only allow letters and numbers to be used throughout the identifier, but also allow the check "digit" to be a letter. Typically, letters than can easily be confused with numbers (B, I, O, Q, S, and Z) are omitted. In fact, the Mod25 algorithm omits both numbers and letters that look similar and can be confused with each other (0, 1, 2, 5, 8, B, I, O, Q, S, and Z); the Mod30 algorithm omits only the potentially confusing letters. The LuhnModNIdentifierValidator.java class contains the code that computes a check digit using "baseCharacters" as the set of possible characters for the identifier or check digit.
Here's how we handle non-numeric characters
For the second-to-last (2nd from the right) character and every other (even-positioned) character moving to the left, we just add 'ASCII value - 48' to the running total. Non-numeric characters will contribute values >10, but these digits are not added together; rather, the value 'ASCII value - 48' (even if over 10) is added to the running total. For example, '"M"' is ASCII 77. Since '77 - 48 = 29', we add 29 to the running total, not '2 + 9 = 11'.
...
| Code Block | ||||||
|---|---|---|---|---|---|---|
| ||||||
def checkdigit(idWithoutCheckDigit) {
idWithoutCheckDigit = idWithoutCheckDigit.trim().toUpperCase()
sum = 0
(0..<idWithoutCheckDigit.length()).each { i ->
char ch = idWithoutCheckDigit[-(i+1)]
if (!'0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_'.contains(ch.toString()))
throw new Exception("$ch is an invalid character")
digit = (int)ch - 48;
sum += i % 2 == 0 ? 2*digit - (int)(digit/5)*9 : digit
}
(10 - ((Math.abs(sum)+10) % 10)) % 10
}
// Validate our algorithm
assert checkdigit('12') == 5
assert checkdigit('123') == 0
assert checkdigit('1245496594') == 3
assert checkdigit('TEST') == 4
assert checkdigit('Test123') == 7
assert checkdigit('00012') == 5
assert checkdigit('9') == 1
assert checkdigit('999') == 3
assert checkdigit('999999') == 6
assert checkdigit('CHECKDIGIT') == 7
assert checkdigit('EK8XO5V9T8') == 2
assert checkdigit('Y9IDV90NVK') == 1
assert checkdigit('RWRGBM8C5S') == 5
assert checkdigit('OBYY3LXR79') == 5
assert checkdigit('Z2N9Z3F0K3') == 2
assert checkdigit('ROBL3MPLSE') == 9
assert checkdigit('VQWEWFNY8U') == 9
assert checkdigit('45TPECUWKJ') == 1
assert checkdigit('6KWKDFD79A') == 8
assert checkdigit('HXNPKGY4EX') == 3
assert checkdigit('91BT') == 2
try {
checkdigit ("12/3")
assert false
} catch(e) { }
|
Python
| Code Block | |||||
|---|---|---|---|---|---|
| |||||
import math# Works for Python 3 from here: https://gist.github.com/alastairmccormack/e115140ddb1b522059d677f6dbf38f34 def returnget_checkdigit(self, id_without_check): # allowable characters within identifier valid_chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_" # remove leading or trailing whitespace, convert to uppercase id_without_checkdigit = id_without_check.strip().upper() # this will be a running total sum = 0; # loop through digits from right to left for n, char in enumerate(reversed(id_without_checkdigit)): char in enumerate(reversed(id_without_checkdigit)): if not valid_chars.count(char): raise Exception('InvalidIDException') # our "digit" is calculated using ASCII value - 48 digit = ord(char) - 48 # weight will be the current digit's contribution to # the running total weight will= beNone the current digit's contribution to if (n % 2 == 0): # the running total # for alternating digits starting weightwith =the Nonerightmost, we if (n# %use 2our == 0): formula this is the same as multiplying x 2 and # adding digits together for values 0 to 9. Using the # for alternating digits starting with the rightmost, we # following formula allows us to gracefully calculate a # use our formula this is the same as# multiplyingweight xfor 2 and non-numeric "digits" as well (from their # addingASCII digitsvalue together- for48). values 0 to 9. Using the ## Use_sparingly: In Python 3, '/' makes floats. '//' fixes it #for followingPython formula3. allows us to gracefully calculate a ## For cross compatibility, simply int() the result # weight for non-numeric "digits" as well (from their ## # ASCII value - 48). VVVVVVVVVVVVV weight = (2 * digit) - int(digit / 5) * 9 else: # even-positioned digits just contribute their ascii # value minus 48 contribute their ascii weight = digit # value minus 48 weight = digit # keep a running total of weights ## Use_sparingly: removed maths.fabs() sum += weight ## abs() is sufficient sum += weight # avoid sum less than 10 (if characters below "0" allowed, # this could happen) sum = math.fabsabs(sum) + 10 # check digit is amount needed to reach next number # divisible by ten. Return an integer return int((10 - (sum % 10)) % 10) |
...