Damm’s Algorithm
November 18, 2014
We studied Hans Peter Luhn’s algorithm for generating check digits in a previous exercise. Today, we look at an alternate check digit algorithm developed by H. Michael Damm. Both algorithms are useful for creating checked identification numbers, suitable for credit cards or other identity numbers.
Damm’s algorithm is based on table lookup. It is initialized with a current check digit of 0. Then, each digit of the number, from left to right (most-significant to least-significant) is looked up in a two-dimensional table with the current check digit pointing to the row and the digit of the number pointing to the column, using this table:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
| 1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
| 2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
| 3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
| 4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
| 5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
| 6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
| 7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
| 8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 9 |
| 9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
For instance, given the input 572, the check digit is 4 and the output is 5724. The check digit is computed starting with 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, and row 7 and column 2 gives a final check digit of 4. Notice that leading zeroes do not affect the check digit.
Checking goes the same way, and is successful if the final check digit is 0. Given the input 5724, the initial check digit is 0, then row 0 and column 5 gives a new check digit of 9, row 9 and column 7 gives a new check digit of 7, row 7 and column 2 gives a new check digit of 4, and row 4 and column 4 gives a final check digit of 0.
Your task is to write functions that add a check digit to a number and validate a number to which a check digit has been added. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
my @map = qw( 0317598642 7092154863 4206871359 1750983426 6123045978 3674209581 5869720134 8945362017 9438617209 2581436790 ); sub cs { my $cs=0; $cs = substr $map[$cs],$_,1 foreach split m{}, $_[0]; return "$_[0]$cs"; } sub valid { return cs(substr $_[0],0,-1) eq $_[0]; }Haskell: http://codepad.org/plvEcNXF
Having leading zeroes not affect the check digit makes things a bit simpler.
#!/usr/bin/env python3 TABLE = [[0, 3, 1, 7, 5, 9, 8, 6, 4, 2], [7, 0, 9, 2, 1, 5, 4, 8, 6, 3], [4, 2, 0, 6, 8, 7, 1, 3, 5, 9], [1, 7, 5, 0, 9, 8, 3, 4, 2, 6], [6, 1, 2, 3, 0, 4, 5, 9, 7, 8], [3, 6, 7, 4, 2, 0, 9, 5, 8, 1], [5, 8, 6, 9, 7, 2, 0, 1, 3, 4], [8, 9, 4, 5, 3, 6, 2, 0, 1, 7], [9, 4, 3, 8, 6, 1, 7, 2, 0, 9], [2, 5, 8, 1, 4, 3, 6, 7, 9, 0]] def digits(n): if n <= 0: return [0] else: q, r= divmod(n, 10) ds = [r] ds.extend(digits(q)) return ds def check(n): i = 0 for j in reversed(digits(n)): i = TABLE[i][j] return i def verify(c): 0 == check(c) if __name__ == "__main__": from random import randrange from sys import exit for _ in xrange(10000): n = randrange(int(1e42)) if not verify(10 * n + check(n)): exit("Failure! {0}".format(n)) print("All tests passed.")Didn’t read the directions carefully.
checkshould return10 * n + i, and the test at the end can be simplified toverify(check(n)). Sorry!On my laptop, using a dict of dicts for the table and processing the number as a string, is about twice as fast as using a list of lists and processing the number as digits (i.e., ints).
data = """0 3 1 7 5 9 8 6 4 2 7 0 9 2 1 5 4 8 6 3 4 2 0 6 8 7 1 3 5 9 1 7 5 0 9 8 3 4 2 6 6 1 2 3 0 4 5 9 7 8 3 6 7 4 2 0 9 5 8 1 5 8 6 9 7 2 0 1 3 4 8 9 4 5 3 6 2 0 1 7 9 4 3 8 6 1 7 2 0 9 2 5 8 1 4 3 6 7 9 0 """.splitlines() digits = '0123456789' table = dict(zip(digits, (dict(zip(digits, row.split())) for row in data))) def damm(n): check = '0' for d in str(n): check = table[check][d] return int(check) def add_check(n): return 10*n + damm(n) def validate(n): return not damm(n)I’ve been getting into Clojure lately:
(def damm [[0 3 1 7 5 9 8 6 4 2] [7 0 9 2 1 5 4 8 6 3] [4 2 0 6 8 7 1 3 5 9] [1 7 5 0 9 8 3 4 2 6] [6 1 2 3 0 4 5 9 7 8] [3 6 7 4 2 0 9 5 8 1] [5 8 6 9 7 2 0 1 3 4] [8 9 4 5 3 6 2 0 1 7] [9 4 3 8 6 1 7 2 0 9] [2 5 8 1 4 3 6 7 9 0]]) (defn digits [n] (map #(- (int %) (int \0)) (str n))) (defn checkdigit[n] (reduce #((damm %1) %2) 0 (digits n))) (defn check[n] (+ (* n 10) (checkdigit n))) (defn valid?[n] (= (checkdigit n) 0)) (check 572) (valid? 5724)Just to let you guys know, the lookup table you’re using is incorrect. The 8th row, 9th column should be a 5. https://en.wikipedia.org/wiki/Damm_algorithm