Date: Thu, 21 Nov 2019 09:20:18 +0000 (UTC) Message-ID: <14299428.33203.1574328018988@menji.openmrs.org> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_33202_1385437005.1574328018988" ------=_Part_33202_1385437005.1574328018988 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Check Digit Algorithm

# Check Digit Algorithm

## Why bother= with check digits?

The purpose of check digits is simple. Any time identifiers (typically n= umber +/- letters) are being manually entered via keyboard, there will be e= rrors. Inadvertent keystrokes or fatigue can cause digits to be rearranged,= dropped, or inserted. Have you ever mis-dialed a phone number? It happens.=

Check digits help to reduce the likelihood of errors by introducing a fi= nal digit that is calculated from the prior digits. Using the proper algori= thm, the final digit can always be calculated. Therefore, when a number is = entered into the system (manually or otherwise), the computer can instantly= verify that the final digit matches the digit predicted by the check digit= algorithm. If the two do not match, the number is refused. The end result = is fewer data entry errors.

=20

Calculate a check digit:

=20
=20 =20
=20 Valid MRN: =20  = =20
=20 =20
=20 show bulk check digit tool=20 =20
=20

## What is the Luhn alg= orithm?

We use a variation of the Luhn algorithm. This= algorithm, also known as the "modulus 10" or "mod 10" algorithm, is very c= ommon. For example, it's the algorithm used by credit card companies to gen= erate the final digit of a credit card.

Given an identifier, let's say "139", you travel right to left. Every ot= her digit is doubled and the other digits are taken unchanged. All resultin= g digits are summed and the check digit is the amount necessary to take thi= s sum up to a number divisible by ten.

Got it? All right, lets try the example.

=20

Work right-to-left, using "139" and doubling every other digit.

9 x 2 =3D 18

3 =3D 3

1 x 2 =3D 2

Now sum all of the digits (note '18' is two digits, '1'= and '8'). So the answer is '1 + 8 + 3 + 2 =3D 14' and the check digit is t= he amount needed to reach a number divisible by ten. For a sum of '14', the= check digit is '6' since '20' is the next number divisible by ten.

=20

## Our variation= on the Luhn algorithm

### Allowing for Letters

We have borrowed the variation on the Luhn algorithm used by Regens= trief Institute, Inc. In this variation, we allow for letters as well a= s numbers in the identifier (i.e., alphanumeric identifiers). This allows f= or an identifier like "139MT" that the original Luhn algorithm cannot handl= e (it's limited to numeric digits only).

Allowing letters-even lim= ited to capital letters-does not increase the accuracy of data entry= . In fact, the potential for mistaking numbers and letters likely increases= the chance for errors. In our case (Regenstrief with the AMPATH Medical Re= cord System), we were forced to come up with a simple method for generating= identifiers in disparate, disconnected location without collision (giving = out the same number twice). Adding a 2-3 letter suffix to the identifer was= our solution.

To handle alphanumeric digits (numbers and letters), we= actually use the ASCII value (the computer's internal code) for each chara= cter and subtract 48 to derive the "digit" used in the Luhn algorithm. We s= ubtract 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" assum= e 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.

The Luhn CheckDigit Validator uses this variation to allow for letters, = whereas the Luhn Mod-10 Check-Digit Validator uses the standard Luhn Algori= thm using only numbers 0-9.

### Mod 25 and Mod 30

The idgen module supports additional algorithms, including Mod25 and Mod30 algorithms. These algorithms not onl= y 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 M= od25 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 a= lgorithm omits only the potentially confusing letters. The LuhnModNIdentifierValidator.= java class contains the code that computes a check digit using "baseCha= racters" as the set of possible characters for the identifier or check digi= t.

## Here'= s how we handle non-numeric characters

For the second-to-last (2nd from the right) character and every other (e= ven-positioned) character moving to the left, we just add 'ASCII value - 48= ' to the running total. Non-numeric characters will contribute values >1= 0, but these digits are not added together; rather, the va= lue 'ASCII value - 48' (even if over 10) is added to the running total. For= example, '"M"' is ASCII 77. Since '77 - 48 =3D 29', we add 29 to the runni= ng total, not '2 + 9 =3D 11'.

For the rightmost character and every other (odd-positioned) character m= oving to the left, we use the formula '2 * n - 9 x INT(n/5)' (where INT() r= ounds off to the next lowest whole number) to calculate the contribution of= every other character. If you use this formula on the numbers 0 to 9, you = will see that it's the same as doubling the value and then adding the resul= ting digits together (e.g., using 8: '2 x 8 =3D 16' and '1 + 6 =3D 7'. Usin= g the formula: '2 x 8 - 9 x INT(8/5) =3D 16 - 9 x 1 =3D 16 - 9 =3D 7') =E2= =80=93 identical to the Luhn algorithm. But using this formula allows us to= handle non-numeric characters as well by simply plugging 'ASCII value - 48= ' into the formula. For example, '"Z"' is ASCII 90. '90 - 48 =3D 42' and '2= x 42 - 9 x INT(42/5) =3D 84 - 9 x 8 =3D 84 - 72 =3D 12'. So we add 12 (not '1 + 2 =3D 3') to the running total.

So, here's how we would use the Luhn algorithm for the identifier "139MT= ":

=20

T (ASCII 84) -> 84 - 48 =3D 36 -> 2 x 36 - 9 x INT(36/5) =3D 72 - = 9 x 7 =3D 72 - 63 =3D 9

M (ASCII 77) -> 77 - 48 =3D 29

9 x 2 =3D 18 -> 1 + 8 =3D 9 or 9 =3D> 2 x 9 - 9 x INT(9/5) =3D 18 = - 9 x 1 =3D 18 - 9 =3D 9

3 =3D 3

1 x 2 =3D 2 or 1 =3D> 2 x 1 - 9 x INT(1/5) =3D 2 - 9 x 0 =3D 2

Summing the results we get '9 + 29 + 9 + 3 + 2 =3D 52'. The next number = divisible by ten is 60. So, our check digit (the difference) is 8.

=20

## Java

The modified mod10 algorithm implemented in Java
=20
```public i=
nt checkdigit(String idWithoutCheckdigit) {

// allowable characters within identifier
String validChars =3D "0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_";

// remove leading or trailing whitespace, convert to uppercase
idWithoutCheckdigit =3D idWithoutCheckdigit.trim().toUppercase();

// this will be a running total
int sum =3D 0;

// loop through digits from right to left
for (int i =3D 0; i < idWithoutCheckdigit.length(); i++) {

//set ch to "current" character to be processed
char ch =3D idWithoutCheckdigit
.charAt(idWithoutCheckdigit.length() - i - 1);

// throw exception for invalid characters
if (validChars.indexOf(ch) =3D=3D \-1)
throw new InvalidIdentifierException(
"\"" + ch + "\" is an invalid character");

// our "digit" is calculated using ASCII value - 48
int digit =3D (int)ch - 48;

// weight will be the current digit's contribution to
// the running total
int weight;
if (i % 2 =3D=3D 0) {

// for alternating digits starting with the rightmost, we
// use our formula this is the same as multiplying x 2 and
// adding digits together for values 0 to 9.  Using the
// following formula allows us to gracefully calculate a
// weight for non-numeric "digits" as well (from their
// ASCII value - 48).
weight =3D (2 * digit) - (int) (digit / 5) * 9;

} else {

// even-positioned digits just contribute their ascii
// value minus 48
weight =3D digit;

}

// keep a running total of weights
sum \+=3D weight;

}

// avoid sum less than 10 (if characters below "0" allowed,
// this could happen)
sum =3D Math.abs(sum) + 10;

// check digit is amount needed to reach next number
// divisible by ten
return (10 - (sum % 10)) % 10;

}
```
=20

## VBA

The modified mod10 algorithm implemented in VBA
=20
```Function c=
heckdigit(idWithoutCheckDigit)

ucIdWithoutCheckdigit =3D UCase(idWithoutCheckDigit)
total =3D 0
For i =3D Len(ucIdWithoutCheckdigit) To 1 Step \-2
digit =3D Asc(Mid(ucIdWithoutCheckdigit, i, 1)) - 48
total =3D total + (2 * digit) - Int(digit / 5) * 9
If (i > 1) Then
digit =3D Asc(Mid(ucIdWithoutCheckdigit, i - 1, 1)) - 48
total =3D total + digit
End If
Next i
total =3D Abs(total) + 10
checkdigit =3D (10 - (total Mod 10)) Mod 10

End Function
```
=20

Note:

This VBA algorithm should probably check each character and return an er= ror if any invalid characters are found (as the Java example above does by = throwing an exception).

## Groovy

The modified mod10 algorithm implemented in Groovy
=20
```def ch=
eckdigit(idWithoutCheckDigit) {
=09idWithoutCheckDigit =3D idWithoutCheckDigit.trim().toUpperCase()
=09sum =3D 0
=09(0..<idWithoutCheckDigit.length()).each { i ->
=09char ch =3D idWithoutCheckDigit[-(i+1)]
=09if (!'0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_'.contains(ch.toString())=
)
=09throw new Exception("\$ch is an invalid character")
=09digit =3D (int)ch - 48;
=09sum +=3D i % 2 =3D=3D 0 ? 2*digit - (int)(digit/5)*9 : digit
=09}
=09(10 - ((Math.abs(sum)+10) % 10)) % 10
}

// Validate our algorithm
assert checkdigit('12') =3D=3D 5
assert checkdigit('123') =3D=3D 0
assert checkdigit('1245496594') =3D=3D 3
assert checkdigit('TEST') =3D=3D 4
assert checkdigit('Test123') =3D=3D 7
assert checkdigit('00012') =3D=3D 5
assert checkdigit('9') =3D=3D 1
assert checkdigit('999') =3D=3D 3
assert checkdigit('999999') =3D=3D 6
assert checkdigit('CHECKDIGIT') =3D=3D 7
assert checkdigit('EK8XO5V9T8') =3D=3D 2
assert checkdigit('Y9IDV90NVK') =3D=3D 1
assert checkdigit('RWRGBM8C5S') =3D=3D 5
assert checkdigit('OBYY3LXR79') =3D=3D 5
assert checkdigit('Z2N9Z3F0K3') =3D=3D 2
assert checkdigit('ROBL3MPLSE') =3D=3D 9
assert checkdigit('VQWEWFNY8U') =3D=3D 9
assert checkdigit('45TPECUWKJ') =3D=3D 1
assert checkdigit('6KWKDFD79A') =3D=3D 8
assert checkdigit('HXNPKGY4EX') =3D=3D 3
assert checkdigit('91BT') =3D=3D 2
try {
checkdigit ("12/3")
assert false
} catch(e) { }
```
=20

## Python

Implemented in Python, by Daniel Watson
=20
```import=
math
def return_checkdigit(self, id_without_check):

# allowable characters within identifier
valid_chars =3D "0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_"
=20
# remove leading or trailing whitespace, convert to uppercase
id_without_checkdigit =3D id_without_check.strip().upper()
=20
# this will be a running total
sum =3D 0;
=20
# loop through digits from right to left
for n, char in enumerate(reversed(id_without_checkdigit)):
=20
if not valid_chars.count(char):
raise Exception('InvalidIDException')
=20
# our "digit" is calculated using ASCII value - 48
digit =3D ord(char) - 48
=20
# weight will be the current digit's contribution to
# the running total
weight =3D None
if (n % 2 =3D=3D 0):
=20
# for alternating digits starting with the rightmost, we
# use our formula this is the same as multiplying x 2 and
# adding digits together for values 0 to 9.  Using the
# following formula allows us to gracefully calculate a
# weight for non-numeric "digits" as well (from their
# ASCII value - 48).
weight =3D (2 * digit) - (digit / 5) * 9
else:
# even-positioned digits just contribute their ascii
# value minus 48
weight =3D digit
=20
# keep a running total of weights
sum +=3D weight
=20
# avoid sum less than 10 (if characters below "0" allowed,
# this could happen)
sum =3D math.fabs(sum) + 10
=20
# check digit is amount needed to reach next number
# divisible by ten. Return an integer=20
return int((10 - (sum % 10)) % 10)
```
=20

## Perl

Implemented in Perl, by Steve Cayford
=20
``` sub che=
ckdigit {
my ( \$tocheck ) =3D @_;

\$tocheck =3D uc \$tocheck;
die 'Invalid characters' if \$tocheck =3D~ m/ [^0-9A-Z_]=
/xms;

my \$sum  =3D 0;
my \$even =3D 0;

for my \$char ( reverse split( qr//, \$tocheck ) ) {
my \$n =3D ord( \$char ) - 48;
\$sum +=3D
&n=
bsp; \$even
? \$n
: 2 * \$=
n - 9 * int( \$n / 5 );
\$even =3D ( \$even + 1 ) % 2;
}

\$sum =3D abs \$sum + 10;
return ( 10 - \$sum % 10 ) % 10;
}
```
=20

## C#

C# direct translation, by Yves Rochon
=20
```      =
private static int D3CustomerCheckDigit(string idWithoutCheckdigit) {

// allowable characters within identifier
const string validChars =3D "0123456789ABCDEFGHIJKLMNOPQRSTUVYW=
XZ_";

// remove leading or trailing whitespace, convert to uppercase
idWithoutCheckdigit =3D idWithoutCheckdigit.Trim().ToUpper();

// this will be a running total
int sum =3D 0;

// loop through digits from right to left
for (int i =3D 0; i < idWithoutCheckdigit.Length; i++) {

//set ch to "current" character to be processed
char ch =3D idWithoutCheckdigit[idWithoutCheckdigit.Length =
- i - 1];

// throw exception for invalid characters
if (validChars.IndexOf(ch) =3D=3D -1)
throw new Exception(ch + " is an invalid character");

// our "digit" is calculated using ASCII value - 48
int digit =3D (int)ch - 48;

// weight will be the current digit's contribution to
// the running total
int weight;
if (i % 2 =3D=3D 0)
{

// for alternating digits starting with the rightmost, we
// use our formula this is the same as multiplying x 2 an=
d
// adding digits together for values 0 to 9.  Using the
// following formula allows us to gracefully calculate a
// weight for non-numeric "digits" as well (from their
// ASCII value - 48).
weight =3D (2 * digit) - (int) (digit / 5) * 9;
}
else
{
// even-positioned digits just contribute their ascii
// value minus 48
weight =3D digit;
}

// keep a running total of weights
sum +=3D weight;

}

// avoid sum less than 10 (if characters below "0" allowed,
// this could happen)
sum =3D Math.Abs(sum) + 10;

// check digit is amount needed to reach next number
// divisible by ten
return (10 - (sum % 10)) % 10;

}```
=20

## JavaScript

Implemented in JavaScript, by Owais Hussain
=20
``` f=
unction luhnCheckDigit(number) {
var validChars =3D "0123456789ABCDEFGHIJKLMNOPQRSTUVYWXZ_";
number =3D number.toUpperCase().trim();
var sum =3D 0;
for (var i =3D 0; i < number.length; i++) {
var ch =3D number.charAt(number.length - i - 1);
if (validChars.indexOf(ch) < 0) {
return false;
}
var digit =3D ch.charCodeAt(0) - 48;
var weight;
if (i % 2 =3D=3D 0) {
weight =3D (2 * digit) - parseInt(digit / 5) * 9;
}
else {
weight =3D digit;
}
sum +=3D weight;
}
sum =3D Math.abs(sum) + 10;
var digit =3D (10 - (sum % 10)) % 10;
return digit;
}```
=20

## Excel Formula

```Input the number in cell "A1" and assign the formula below to cell "A2=
", which will give you the check digit.```
Implemented in MS Excel, by Owais Hussain
=20
```A2=3DMO=
D(SUMPRODUCT(-MID(TEXT(MID(A1,ROW(INDIRECT("1:"&LEN(A1))),1)*(MOD(ROW(I=
NDIRECT("1:"&LEN(A1)))+1,2)+1),"00"),{1,2},1)),10)```
=20
------=_Part_33202_1385437005.1574328018988--