Damm’s Algorithm

November 18, 2014

This is simple; here are the table and two functions:

(define 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)))

(define (check num)
  (let loop ((d 0) (ds (digits num)))
    (if (null? ds) (+ (* num 10) d)
      (loop (vector-ref (vector-ref damm d) (car ds)) (cdr ds)))))

(define (valid? num)
  (let loop ((d 0) (ds (digits num)))
    (if (null? ds) (zero? d)
      (loop (vector-ref (vector-ref damm d) (car ds)) (cdr ds)))))

And here are some examples:

> (check 572)
5724
> (valid? 5724)
#t

We used digits from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/mIPEQIZX.

It is a mystery to my why the Luhn algorithm is so often used, whereas the Damm algorithm is so seldom used. The Damm algorithm finds all single-digit errors and all adjacent-digit transpositions; Luhn’s algorithm finds most, but not all. And Damm’s algorithm is arguably simpler, using table lookup instead of arithmetic. Perhaps Luhn is preferred because it was available first, and because it doesn’t require space to store the lookup table (though at only 100 half-bytes, the table size is probably about the same memory size as the program code).

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
7 Comments »

7 Responses to “Damm’s Algorithm”

  1. James Curtis-Smith said
    November 18, 2014 at 9:30 AM 
    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];
}
  3. Graham said
    November 18, 2014 at 10:18 PM

    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.")
  4. Graham said
    November 18, 2014 at 10:20 PM

    Didn’t read the directions carefully. check should return 10 * n + i, and the test at the end can be simplified to verify(check(n)). Sorry!

  5. Mike said
    November 19, 2014 at 12:39 AM

    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)
  6. matthew said
    November 20, 2014 at 12:23 PM

    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)
  7. Phil Martyn said
    December 9, 2015 at 11:41 AM

    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

Leave a comment