checkdigit calculation for HP-17b

[Don Shepherd]

The Luhn algorithm for calculating a standard mod-10 checkdigit for an account or ID number lends itself very well to a simple program, or in this case a 17b solver equation.

Checkdigits are typically used during data entry to prevent the transposition of digits, so that ID 12345, if keyed in as 13245, can be corrected before the erroneous data becomes part of a file. Each digit in the account number, starting at the right-hand side, is multiplied by the pattern 212121..., the digits of the products are summed and the total is subtracted from the next higher multiple of 10. The result is the checkdigit associated with the ID number, the rightmost digit.

An example:

ID: 4 5 6 7 8 9
multiply: 1 2 1 2 1 2
product: 4 10 6 14 8 18
digits sum: 33
subtract from next higher multiple of 10: 40-33=7
checkdigit is 7, so the final ID is 4567897

In 2007, when I became aware of the 17b/17bii, I wrote a solver equation to calculate the checkdigit of an ID number, up to 12 digits in length. Here is that equation:

CD = 0\(\times\)L(M:2)\(\times\)L(C:-1)
+MOD(10-
MOD(\(\Sigma\)(I:0:LOG(N):1:
0\(\times\)L(A:MOD(IP(N):10)\(\times\)G(M))
+IF(G(A)<10:G(A):G(A)-9)
+0\(\times\)L(M:G(M)+G(C))
\(\times\)L(C:-G(C))
\(\times\)L(N:N\(\div\)10)):10):10)

That equation works, but it is rather long, and smaller solver equations run faster than longer ones, so recently I took another look at this equation, with the following goals:

1. Make equation as small as possible
2. Avoid IF functions
3. Avoid 0 times
4. Handle getting each digit of the input number
5. Handle the 2121 multiplier
6. Handle 2X7 =14, you really want 5 not 14
7. Handle checkdigit 0, because 10-0=10, not 0
   

With those goals in mind, here is what I came up with:

CD = MOD(10-
MOD(\(\Sigma\)(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)\(\times\)(2-MOD(I:2)))
-9\(\times\)IDIV(G(A):10)
):10):10)

This reduced the size of the equation from 164 characters to 92 characters, a 44% reduction in size, and I achieved all of my goals. And, more importantly, it forced me to think through exactly what was needed, and use the available 17b solver functions to achieve this.

The 17b is a great little machine and can exercise your mind in 2015 as well as it could in 1988.

[Thomas Klemm]

(07-26-2015 12:08 AM)Don Shepherd Wrote:  This reduced the size of the equation from 164 characters to 92 characters, a 44% reduction in size, and I achieved all of my goals.

We can go a little further:

CD = MOD(\(\Sigma\)(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)\(\times\)(MOD(I:2)-2))
+IDIV(G(A):10)
):10)

I moved the final negation into the expression so we have to calculate MOD 10 only once.
Instead of -9 we can use +1 when calculating MOD 10.
However I can't verify the formula at the moment.
Thus I could be completely wrong.

Quote:The 17b is a great little machine and can exercise your mind in 2015 as well as it could in 1988.

Completely agree with you: I'm always happy when you bring it up.
The Luhn-algorithm was new to me. Thanks for letting us know.

Kind regards
Thomas

[Don Shepherd]

(07-26-2015 07:47 AM)Thomas Klemm Wrote:  

(07-26-2015 12:08 AM)Don Shepherd Wrote:  This reduced the size of the equation from 164 characters to 92 characters, a 44% reduction in size, and I achieved all of my goals.

We can go a little further:

CD = MOD(\(\Sigma\)(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)\(\times\)(MOD(I:2)-2))
+IDIV(G(A):10)
):10)

I moved the final negation into the expression so we have to calculate MOD 10 only once.
Instead of -9 we can use +1 when calculating MOD 10.
However I can't verify the formula at the moment.
Thus I could be completely wrong.

Quote:The 17b is a great little machine and can exercise your mind in 2015 as well as it could in 1988.

Completely agree with you: I'm always happy when you bring it up.
The Luhn-algorithm was new to me. Thanks for letting us know.

Kind regards
Thomas

Thomas, thanks for this. I can't get it to compile, however. Can you check it?

Don

[Thomas Klemm]

(07-26-2015 12:56 PM)Don Shepherd Wrote:  I can't get it to compile, however. Can you check it?

Sure. You just have to be a little patient.

Cheers
Thomas

[Don Shepherd]

(07-26-2015 01:25 PM)Thomas Klemm Wrote:  

(07-26-2015 12:56 PM)Don Shepherd Wrote:  I can't get it to compile, however. Can you check it?

Sure. You just have to be a little patient.

Cheers
Thomas

My mistake, I forgot one paren. It works. Great work, I like it! Down to 79 characters!

Don

[Thomas Klemm]

(07-26-2015 02:04 PM)Don Shepherd Wrote:  It works.

Good to hear. And I was going to blame my sausage fingers fumbling on a smart-phone.

Have these mechanical computers for verifying numbers in Luhn's patent ever been produced?


Cheers
Thomas

[Don Shepherd]

(07-26-2015 04:45 PM)Thomas Klemm Wrote:  Have these mechanical computers for verifying numbers in Luhn's patent ever been produced?

Cheers
Thomas

I've certainly never seen one. It does look very interesting, however.

[Gerson W. Barbosa]

Hello Don,

Interesting algorithm and HP-17B equation!

Here we happy taxpayers have a personal 11-digit number known as CPF, the last two of which being the checking digits. Starting with your SOD (sum of digits) equation, it wasn't difficult to obtain a 17Bii equation to compute them:

C=10*MOD(MOD(0*L(T:0)+Σ(I:1:9:1:0*L(T:G(T)+I*MOD(N:10))+(10-I)
*MOD(N:10)+0*L(N:IDIV(N:10))):11):10)+MOD(MOD(G(T):11):10)

No attempt have been made to optimize it, though.

123 456 789 --> 0 (they should be 00, actually)
976 431 258 --> 64
777 777 777 --> 77

The interesting part is that I didn't need to look at the linked Wikipedia article before writing the equation, as I knew the algorithm since I was 14 or 15, when I didn't have access to computers or even calculators, programmable or not. My father taught that to me. He was a policeman and once had a report returned because of missing or wrong checking digits. Since the number holder was not readily available, he tried and figured out the algorithm by himself, using pencil and paper. He was no computer or math expert!

Gerson.

[Don Shepherd]

(07-26-2015 07:29 PM)Gerson W. Barbosa Wrote:  The interesting part is that I didn't need to look at the linked Wikipedia article before writing the equation, as I knew the algorithm since I was 14 or 15

Thanks Gerson.

I first learned about this algorithm when I started my job as a programmer in 1974 at the US Census Bureau (ah, those big Univac mainframes, I loved them).

I worked in the Economic Surveys division of the Bureau, and our main file had a record for each business establishment in the US. Every business had an Employer Identification number (EIN) assigned by either Social Security or IRS, probably IRS. In our programs, whenever we processed these files we had to verify the correct EIN, and part of that was to verify the checkdigit. I had never heard of the Luhn algorithm; my boss had probably never heard of it either, but he sure knew how it worked, and he explained it to me so I could implement it in every FORTRAN program I wrote.

I discovered it is also used on all credit cards in the US.

Don

[Gerson W. Barbosa]

Don, here is a Free Pascal version:

Code:


Program CPF;
Uses Crt;
var c, i: Byte;
    s, t: Integer;
       n: Longint;
begin
  ClrScr;
  Read(n);
  s:=0;
  t:=0;
  for i:=1 to 9 do
    begin
      s:=s+(10-i)*(n Mod 10);
      t:=t+i*(n Mod 10);
      n:=n div 10
    end;
    c:=10*((s Mod 11) Mod 10) + ((t Mod 11) Mod 10);
    WriteLn(c:2)
end.

Run:

999999999
99
Type EXIT to return...

Again, no attempt has been made to optimize the program, but it's interesting to compare the number of characters in both the Pascal and 17Bii codes.

Notice the algorithm I've used is somewhat different (and easier to implement on the 17Bii) than the one in the Wikipedia article. Nonetheless, I get exactly the same results.

Gerson.

Edited to fix program line #17

Edited again to fix algorithm (inclusion of an IF-clause)

Code:


Program CPF;
Uses Crt;
var d1,d2, i: Byte;
    s, t: Integer;
       n: Longint;
begin
  ClrScr;
  Read(n);
  s:=0;
  t:=0;
  for i:=1 to 9 do
    begin
      s:=s+(10-i)*(n Mod 10);
      t:=t+i*(n Mod 10);
      n:=n div 10
    end;
  if (s Mod 11)=10 then
    t:=t+9;
  d1:=(s Mod 11) Mod 10;
  d2:=(t Mod 11) Mod 10;
  GotoXY(10,1);
  WriteLn('-',d1:1,d2:1)
end.

-------------------------

Run

123456789 

123456789-09
Type EXIT to return...

As I said, this algorithm is more simple than the official one [ function TestaCPF(strCPF) ]. I have yet to discover why this works.

[Don Shepherd]

Thanks Gerson.

So everybody who pays taxes in Brazil has a number. Same here in the US, ours is just called our Social Security number, and we all must go to great lengths to make sure nobody knows our SS number except people who need to know it (like banks and employers). If the bad guys know your number, I'm told your life will become miserable. I have to shred some personal financial documents occasionally so my number doesn't become known by the bad guys.

I got my SS number when I was 14 and got a part-time job delivering newspapers. Now, however, newborn babies get their number at birth. Some employers used to use an employees SS number as their personnel number, but I think that pretty much stopped when the bad guys got active. When I worked for a grocery store back in the 1960's they used my SS number as my employee number, and it always had the number 5 added to the end, and I wondered about that until years later I realized it was the checkdigit!

I once programmed a dedicated data entry system (Entrex), and its programming language had built-in routines for checkdigit verification.

Now, the challenge: try to derive my 9-digit SS number from the fact that its checkdigit is 5. If you could do that, the bad boys will pay you millions I'm sure.

Here is a link to a site with some interesting trivia information about the first SS card, back in 1936.

Don

[Bill (Smithville NJ)]

(07-26-2015 11:42 PM)Don Shepherd Wrote:  Now, the challenge: try to derive my 9-digit SS number from the fact that its checkdigit is 5. If you could do that, the bad boys will pay you millions I'm sure.

Hi Don,

Researchers have long figured out how to "guess" your SS number by using public data. SS numbers are not really random - or at least parts of it aren't.

Do a search for plenty of articles on predicting SS numbers. There's been plenty of news stories about this.

When I lived in Indiana, they used to use your SS number for the drivers license number. To get around the law that says you can't use SS numbers for other purposes, they just appended the Letter 'S' to it - that would magically make it NOT a SS number. I don't think they do that anymore.

A couple of years ago, I went to my local college to use their library. They said I could get a courtesy library card (even though I wasn't a student) since I lived in their county. But to get the card, I would have to give them my SS number - and you would never believe the reason given. The SS number was being required by the Department of Homeland Security. I passed on getting a library card there.

Bill
Smithville, NJ

[wynen]

(07-26-2015 04:45 PM)Thomas Klemm Wrote:  Have these mechanical computers for verifying numbers in Luhn's patent ever been produced?

I'm quite sure, you can find these little "computers" in the collection of the "Arithmeum",
a Museum for "Calculating in olden and modern times" in Bonn, Germany.

I've been there last Friday and it was amazing.

Hartmut (from Monheim am Rhein, Germany, near Bonn)

[Don Shepherd]

(07-26-2015 07:47 AM)Thomas Klemm Wrote:  

(07-26-2015 12:08 AM)Don Shepherd Wrote:  This reduced the size of the equation from 164 characters to 92 characters, a 44% reduction in size, and I achieved all of my goals.

We can go a little further:

CD = MOD(\(\Sigma\)(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)\(\times\)(MOD(I:2)-2))
+IDIV(G(A):10)
):10)

I moved the final negation into the expression so we have to calculate MOD 10 only once.
Instead of -9 we can use +1 when calculating MOD 10.
However I can't verify the formula at the moment.
Thus I could be completely wrong.

Quote:The 17b is a great little machine and can exercise your mind in 2015 as well as it could in 1988.

Completely agree with you: I'm always happy when you bring it up.
The Luhn-algorithm was new to me. Thanks for letting us know.

Kind regards
Thomas

Thomas, it has taken me a couple of days but I finally figured out exactly how your method works. I had to draw a table taking things one step at a time, for each digit of the input number. What I couldn't figure out was the behavior of the MOD function with negative numbers; I've always stayed away from negative numbers before, but I now understand how MOD and INT work differently with negative numbers as opposed to positive numbers. I didn't realize that before, and I thank you for giving me this opportunity to understand that behavior.

Your method is a work of art. You are a "steely-eyed missleman", as NASA would say.

Don

[Thomas Klemm]

(07-27-2015 04:11 PM)wynen Wrote:  I'm quite sure, you can find these little "computers" in the collection of the "Arithmeum",
a Museum for "Calculating in olden and modern times" in Bonn, Germany.

I've been there last Friday and it was amazing.

That looks very promising: Arithmeum.
Thanks for sharing. This might be a reason to travel to Bonn.

Cheers
Thomas

[Thomas Klemm]

(07-28-2015 02:54 PM)Don Shepherd Wrote:  I finally figured out exactly how your method works.

This is a step-by-step transformation of your formula to my solution.

1. We can remove the inner calculation of MOD 10 as it's enough to do that once:

CD = MOD(10-
MOD(Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
-9×IDIV(G(A):10)
):10):10)


2. We can remove multiples of 10 as that doesn't change the result when calculating MOD 10:

CD = MOD(10-
Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
-9×IDIV(G(A):10)
):10)


3. We can replace -9 by +1 as they are the same MOD 10:

CD = MOD(-
Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
-9×IDIV(G(A):10)
):10)


4. We can move the - sign into sum.

CD = MOD(-
Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
+IDIV(G(A):10)
):10)

Here comes the tricky part. If we move that just to the summand we have to change the sign of both expressions:

CD = MOD(
Σ(I:0:LOG(N):1:
-L(A:MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
-IDIV(G(A):10)
):10)

But if we move it into the Let-A expression the sign of A will change and thus we don't have to change the sign of the Get-A expression as well:

CD = MOD(
Σ(I:0:LOG(N):1:
L(A:-MOD(IDIV(N:10^I):10)×(2-MOD(I:2)))
+IDIV(G(A):10)
):10)


5. Now we're nearly there. Just move the - sign to the 2nd factor:

CD = MOD(
Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(-2+MOD(I:2)))
+IDIV(G(A):10)
):10)


6. Change the order and we're finally done:

CD = MOD(
Σ(I:0:LOG(N):1:
L(A:MOD(IDIV(N:10^I):10)×(MOD(I:2)-2))
+IDIV(G(A):10)
):10)

For further information I recommend this article on modular arithmetic.
BTW: That's why casting out nines works.

Your table looks familiar: I often have to do these kind of calculations until I understand something.

Kind regards
Thomas

[Gerson W. Barbosa]

Quoting myself:

(07-26-2015 07:29 PM)Gerson W. Barbosa Wrote:  C=10*MOD(MOD(0*L(T:0)+Σ(I:1:9:1:0*L(T:G(T)+I*MOD(N:10))+(10-I)
*MOD(N:10)+0*L(N:IDIV(N:10))):11):10)+MOD(MOD(G(T):11):10)
...

123 456 789 --> 0 (they should be 00, actually)
976 431 258 --> 64
777 777 777 --> 77

I found out my first example was wrong, it should be 09, not 00. The algorithm I use is different from the official one [ function TestaCPF(strCPF) ], but I've managed to fix it so that it always gives the same results:

C=10*MOD(MOD(0*L(T:0)+L(S:Σ(I:1:9:1:0*L(T:G(T)+I*MOD(N:10))+(10-I)*MOD(N:10)
+0*L(N:IDIV(N:10)))):11):10)+MOD(MOD(G(T)+9*IDIV((MOD(G(S):11)):10):11):10)

123 456 789 --> 9 (09 actually, since we have two checking digits)
976 431 258 --> 64
777 777 777 --> 77

Here are the equivalent Free Pascal code and results:

Code:


-------------

Program CPF;
Uses Crt;
var d1,d2, i: Byte;
    s, t: Integer;
       n: Longint;
begin
  ClrScr;
  Read(n);
  s:=0;
  t:=0;
  for i:=1 to 9 do
    begin
      s:=s+(10-i)*(n Mod 10);
      t:=t+i*(n Mod 10);
      n:=n div 10
    end;
  t:=t+9*((s Mod 11) div 10);
  d1:=(s Mod 11) Mod 10;
  d2:=(t Mod 11) Mod 10;
  GotoXY(10,1);
  WriteLn('-',d1:1,d2:1)
end.

-------------

123456789-09
976431258-64
777777777-77

------------

It intrigues me a bit why this more simple algorithm works, but I am not nearly as diligent as Don to find the reason.

Code:


976 431 258 

Algorithm 1:

   9    7    6    4    3    1    2    5    8 

x  1    2    3    4    5    6    7    8    9

   9 + 14 + 18 + 16 + 15 +  6 + 14 + 40 + 72 = 204; 204 mod 11 = 6; 1st Chk Dgt


   9    7    6    4    3    1    2    5    8 

x  9    8    7    6    5    4    3    2    1

  81 + 56 + 42 + 24 + 15 +  4 +  6 + 10 +  8 = 246; 246 mod 11 = 4; 2nd Chk Dgt


Algorithm 2:
  
   9    7    6    4    3    1    2    5    8 

x 10    9    8    7    6    5    4    3    2 

  90 + 63 + 48 + 28 + 18 +  5 +  8 + 15 + 16 = 291; 291 x 10 = 2910; 2910 mod 11 = 6; 1st Chk Dgt

                                                                                   |
                                                +----------------------------------+
                                                |
                                                v

   9    7    6    4    3    1    2    5    8    6

x 11   10    9    8    7    6    5    4    3    2

  99 + 70 + 54 + 32 + 21 +  6 + 10 + 20 + 24 + 12 = 348; 348 x 10 = 3480; 3480 mod 11 = 4; 2nd Chk Dgt

Gerson.

[Thomas Klemm]

(07-28-2015 06:48 PM)Gerson W. Barbosa Wrote:  It intrigues me a bit why this more simple algorithm works

From Cadastro de Pessoas Físicas

Code:

v[1] := (1×cpf[1] + 2×cpf[2] + 3×cpf[3] + 4×cpf[4] + 5×cpf[5] + 6×cpf[6] + 7×cpf[7] + 8×cpf[8] + 9×cpf[9]) mod 11

Code:

v[2] := (9×(1×cpf[1] + 2×cpf[2] + 3×cpf[3] + 4×cpf[4] + 5×cpf[5] + 6×cpf[6] + 7×cpf[7] + 8×cpf[8] + 9×cpf[9]) +
                       1×cpf[2] + 2×cpf[3] + 3×cpf[4] + 4×cpf[5] + 5×cpf[6] + 6×cpf[7] + 7×cpf[8] + 8×cpf[9]) mod 11

We can do the multiplication by 9 mod 11:

Code:

v[2] := (9×cpf[1] + 7×cpf[2] + 5×cpf[3] + 3×cpf[4] + 1×cpf[5] - 1×cpf[6] - 3×cpf[7] - 5×cpf[8] - 7×cpf[9] +
                    1×cpf[2] + 2×cpf[3] + 3×cpf[4] + 4×cpf[5] + 5×cpf[6] + 6×cpf[7] + 7×cpf[8] + 8×cpf[9]) mod 11

This gives us:

Code:

v[2] := (9×cpf[1] + 8×cpf[2] + 7×cpf[3] + 6×cpf[4] + 5×cpf[5] + 4×cpf[6] + 3×cpf[7] + 2×cpf[8] + 1×cpf[9]) mod 11

But then you will say that v[1] wasn't calculated correctly:

Code:

v[1] := v[1] mod 11
v[1] := v[1] mod 10

Thus in case that v[1] = 10 we will get 0 instead of 10.
This is corrected with this step in your program:

Code:

  t:=t+9*((s Mod 11) div 10);

Kind regards
Thomas

[Thomas Klemm]

(07-28-2015 06:48 PM)Gerson W. Barbosa Wrote:  
C=10*MOD(MOD(0*L(T:0)+L(S:Σ(I:1:9:1:0*L(T:G(T)+I*MOD(N:10))+(10-I)*MOD(N:10)
+0*L(N:IDIV(N:10)))):11):10)+MOD(MOD(G(T)+9*IDIV((MOD(G(S):11)):10):11):10)

If you add both s and t you will get \(10\times\sum\) of the digits which is just: \(-\sum\) of the digits mod 11. If you call that u then s can be calculated as \(s=u-t=-(-u+t)\).
This might be easier to implement.

Just an idea \(\cdots\)
Thomas

[Gerson W. Barbosa]

(07-28-2015 08:28 PM)Thomas Klemm Wrote:  This gives us:

Code:

v[2] := (9×cpf[1] + 8×cpf[2] + 7×cpf[3] + 6×cpf[4] + 5×cpf[5] + 4×cpf[6] + 3×cpf[7] + 2×cpf[8] + 1×cpf[9]) mod 11

Thanks, Thomas!

I wonder why they use a somewhat more complicate method here, that is, multiplications of the sums by 10 being required before the final mod 11 operation, not to mention the appending of the first checking digit to the number before computing the second checking digit. I haven't even tried to implement that method on the 17Bii, but it appears to me the resulting equation would be much longer.

(07-28-2015 08:28 PM)Thomas Klemm Wrote:  But then you will say that v[1] wasn't calculated correctly:

Code:

v[1] := v[1] mod 11
v[1] := v[1] mod 10

Thus in case that v[1] = 10 we will get 0 instead of 10.
This is corrected with this step in your program:

Code:

  t:=t+9*((s Mod 11) div 10);

Yes, I discovered that by examining a few wrong results (adding 9 to the first sum before mod 11 would always do in those cases). Another version uses the following instead, but that would make for a longer 17Bii equation, I think.

Code:

  if (s Mod 11)=10 then
    t:=t+9;

Regards,

Gerson.