checkdigit calculation for HP17b

07262015, 12:08 AM
(This post was last modified: 07262015 02:52 PM by Don Shepherd.)
Post: #1




checkdigit calculation for HP17b
The Luhn algorithm for calculating a standard mod10 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 righthand 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: 4033=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:
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\)(2MOD(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. 

07262015, 07:47 AM
Post: #2




RE: checkdigit calculation for HP17b
(07262015 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 Luhnalgorithm was new to me. Thanks for letting us know. Kind regards Thomas 

07262015, 12:56 PM
Post: #3




RE: checkdigit calculation for HP17b
(07262015 07:47 AM)Thomas Klemm Wrote:(07262015 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. Thomas, thanks for this. I can't get it to compile, however. Can you check it? Don 

07262015, 01:25 PM
Post: #4




RE: checkdigit calculation for HP17b  
07262015, 02:04 PM
(This post was last modified: 07262015 02:11 PM by Don Shepherd.)
Post: #5




RE: checkdigit calculation for HP17b  
07262015, 04:45 PM
Post: #6




RE: checkdigit calculation for HP17b
(07262015 02:04 PM)Don Shepherd Wrote: It works. Good to hear. And I was going to blame my sausage fingers fumbling on a smartphone. Have these mechanical computers for verifying numbers in Luhn's patent ever been produced? Cheers Thomas 

07262015, 05:02 PM
Post: #7




RE: checkdigit calculation for HP17b
(07262015 04:45 PM)Thomas Klemm Wrote: Have these mechanical computers for verifying numbers in Luhn's patent ever been produced? I've certainly never seen one. It does look very interesting, however. 

07262015, 07:29 PM
Post: #8




RE: checkdigit calculation for HP17b
Hello Don,
Interesting algorithm and HP17B equation! Here we happy taxpayers have a personal 11digit 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))+(10I) *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. 

07262015, 08:34 PM
Post: #9




RE: checkdigit calculation for HP17b
(07262015 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 

07262015, 11:03 PM
(This post was last modified: 07282015 02:32 AM by Gerson W. Barbosa.)
Post: #10




RE: checkdigit calculation for HP17b
Don, here is a Free Pascal version:
Code:
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 IFclause) Code:
As I said, this algorithm is more simple than the official one [ function TestaCPF(strCPF) ]. I have yet to discover why this works. 

07262015, 11:42 PM
(This post was last modified: 07272015 12:00 AM by Don Shepherd.)
Post: #11




RE: checkdigit calculation for HP17b
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 parttime 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 builtin routines for checkdigit verification. Now, the challenge: try to derive my 9digit 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 

07272015, 01:03 AM
Post: #12




RE: checkdigit calculation for HP17b
(07262015 11:42 PM)Don Shepherd Wrote: Now, the challenge: try to derive my 9digit 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 

07272015, 04:11 PM
Post: #13




RE: checkdigit calculation for HP17b
(07262015 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) 

07282015, 02:54 PM
Post: #14




RE: checkdigit calculation for HP17b
(07262015 07:47 AM)Thomas Klemm Wrote:(07262015 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. 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 "steelyeyed missleman", as NASA would say. Don 

07282015, 06:16 PM
Post: #15




RE: checkdigit calculation for HP17b
(07272015 04:11 PM)wynen Wrote: I'm quite sure, you can find these little "computers" in the collection of the "Arithmeum", That looks very promising: Arithmeum. Thanks for sharing. This might be a reason to travel to Bonn. Cheers Thomas 

07282015, 06:22 PM
Post: #16




RE: checkdigit calculation for HP17b
(07282015 02:54 PM)Don Shepherd Wrote: I finally figured out exactly how your method works. This is a stepbystep 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)×(2MOD(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)×(2MOD(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)×(2MOD(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)×(2MOD(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)×(2MOD(I:2))) IDIV(G(A):10) ):10) But if we move it into the LetA expression the sign of A will change and thus we don't have to change the sign of the GetA expression as well: CD = MOD( Σ(I:0:LOG(N):1: L(A:MOD(IDIV(N:10^I):10)×(2MOD(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 

07282015, 06:48 PM
Post: #17




RE: checkdigit calculation for HP17b
Quoting myself:
(07262015 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))+(10I) 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))+(10I)*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:
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:
Gerson. 

07282015, 08:28 PM
Post: #18




RE: checkdigit calculation for HP17b
(07282015 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]) + 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] + 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 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 

07282015, 09:44 PM
Post: #19




RE: checkdigit calculation for HP17b
(07282015 06:48 PM)Gerson W. Barbosa Wrote: 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=ut=(u+t)\). This might be easier to implement. Just an idea \(\cdots\) Thomas 

07282015, 09:51 PM
Post: #20




RE: checkdigit calculation for HP17b
(07282015 08:28 PM)Thomas Klemm Wrote: This gives us: 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. (07282015 08:28 PM)Thomas Klemm Wrote: But then you will say that v[1] wasn't calculated correctly: 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 Regards, Gerson. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)