(12C) Luhn algorithm
04-18-2018, 06:29 PM (This post was last modified: 04-18-2018 07:19 PM by pinkman.)
Post: #1
 pinkman Senior Member Posts: 387 Joined: Mar 2018
(12C) Luhn algorithm
Ho,
referring to the wikipedia page of the Luhn algorithm, I propose an implementation for the 12c.

How to use it ?

As the 12c has only 10 significant digits, we'll have to split the credit card number into 2 parts.
(Ex: 1234 5678 9012 3456 will be split in 12345678 and 90123456)
After having entered the code, clear the registries 0 and 1 and then enter the right part of the number.
(Ex: 90123456)
Then hit R/S until it displays 0 (don't forget to hit R/S if there were leading zeros).
You can then enter the left part of the number.
(Ex: 12345678)
Then hit R/S until it displays 0 (don't forget to hit R/S if there were leading zeros).

The Luhn key is in REG 0 => RCL 0

If it is a multiple of 10, your Luhn key is OK.
The number of processed digits is in REG 1.

To test :
543210 => 15 in REG 0 (Luhn KO)
543215 => 20 in REG 0 (Luhn OK)

Thibault

Code:
 001- 1 002- 0 003- ÷ 004- ENTER 005- INTG 006- X<>Y 007- FRAC 008- 1 009- 0 010- × 011- RCL 1 012- 2 013- ÷ 014- FRAC 015- x=0 (x=0?) 016- GTO 33 ; GTO odd 017- R↓ 018- 2 019- × 020- 1 021- 0 022- ÷ 023- ENTER 024- INTG 025- X<>Y 026- FRAC 027- 1 028- 0 029- × 030- + 031- STO + 0 032- GTO 35 ; GTO end 033- R↓ ; LBL odd 034- STO + 0 035- 1 ; LBL end 036- STO + 1 037- R↓ 038- R↓ 039- GTO 00
04-23-2018, 08:19 AM (This post was last modified: 04-23-2018 08:56 AM by Dieter.)
Post: #2
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Luhn algorithm
(04-18-2018 06:29 PM)pinkman Wrote:  referring to the wikipedia page of the Luhn algorithm, I propose an implementation for the 12c.
...

Another example of putting the 12C's limited programming capabilites to good use. ;-)

Here is a significantly shorter version that takes advantage of two simple tricks that can also be useful for other applications:

1. In your program the change between odd and even digit positions is done by checking if the index is divisible by 2. Afterwards the digit is doubled or not. My program toggles R1 between 0 and 2 (via R1 := 2 – R1). If it's zero the doubling is skipped, otherwise the factor 2 is already in X.

2. The original program calculates the digit sum of a two-digit result in a very straightforward way: divide x by 10, take the integer part, calculate the remainder, and add both. But since x does not exceed 18 the digit sum can also be calculated by subtracting 9 if x exceeds 9. This was implemented in the HP41 program in the General Forum's Luhn thread. Here the code sequence was

Code:
... 2 x 9 X>Y? CLX - ...

This means: if after doubling x is less than 9 (i.e. 0, 2, 4, 6 or 8) don't subtract anything (CLX –), and if it is ≥ 9 (i.e. 10, 12, 14, 16 or 18) subtract 9 to get 1, 3, 5, 7 or 9 as the digit sum.

Now HP's lower end programmables do not feature an X>Y? test. X≤Y? and X=0? is all they have. But there is a way. If one test is followed by another one which always tests false (!), the first test command is inverted! So an X≤Y? followed by an X=0? in effect is an X>Y? as long as X is not zero. Here X always is 9, so X=0? always tests false and we get an X>Y? test as desired.

Here is the complete program:

Code:
01 1 02 0 03 ÷ 04 INT 05 LSTX 06 FRAC 07 1 08 0 09 x 10 2 11 RCL 1 12 - 13 STO 1 14 X=0? 15 GTO 23 16 x 17 9 18 X≤Y? 19 X=0? 20 CLX 21 - 22 ENTER 23 R↓ 24 STO+0 25 R↓ 26 GTO 00

Initialize with
0  STO 0
2  STO 1

With two additional steps the program can be modified so that the initialization can be done with
0  ST0 0  STO 1
or even a simple CLEAR REG.

If you like this better here is an alternate version:

Code:
01 1 02 0 03 ÷ 04 INT 05 LSTX 06 FRAC 07 1 08 0 09 x 10 RCL 1 11 X=0? 12 GTO 20 13 x 14 9 15 X≤Y? 16 X=0? 17 CLX 18 - 19 ENTER 20 R↓ 21 STO+0 22 2 23 RCL 1 24 - 25 STO 1 26 R↓ 27 R↓ 28 GTO 00

In either case then proceed as with the original program.
Note: the number of processed digits here is not stored in R1.

Hint: INT LSTX FRAC is one step shorter than ENTER INT X<>Y FRAC. ;-)
Also note the dummy ENTER in line 22 or 20 that neutralizes the following R↓.
Yes, a GTO would have done it just as well.

Dieter
04-24-2018, 08:00 AM (This post was last modified: 04-24-2018 01:13 PM by pinkman.)
Post: #3
 pinkman Senior Member Posts: 387 Joined: Mar 2018
RE: (12C) Luhn algorithm
Thanks Dieter!!
I'm ashamed I forgot to use LastX, and I'm really impressed with your optimizations.

The 9 comparison with a combination of both x<=y and x=0 is a good sample of knowledge sharing.

I did not want to use a toggle to identify the odd/even case, because of the advantage of having a counter of digits processed. I found a new solution based on the deterministic result of dividing by 2 any integer: 0 or 0.5. Thus multiplying by 2 and adding 1 gives a factor suitable for any digit to process, without using a test. The code might be a bit slower, but shorter and easy to read and maintain (no gto).

Same usage: clear R0 and R1, enter the first (max 10) lower digits, then r/s for each digit including leading zeros, then enter the next digits, r/s again...
Result in R0, number of processed digits in R1.
If R0 is 10*N then Luhn is OK.

Code:
 01 1 02 0 03 / 04 Intg 05 LastX 06 Frac 07 1 08 0 09 * 10 Rcl 1 11 2 12 / 13 Frac 14 2 15 * 16 1 17 + 18 * 19 9 20 x<=y? 21 x=0? 22 CLX 23 - 24 Sto+ 0 25 Rv 26 1 27 Sto+ 1 28 Rv 29 Rtn
04-24-2018, 06:35 PM (This post was last modified: 04-24-2018 08:12 PM by Dieter.)
Post: #4
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Luhn algorithm
(04-24-2018 08:00 AM)pinkman Wrote:  I did not want to use a toggle to identify the odd/even case, because of the advantage of having a counter of digits processed. I found a new solution based on the deterministic result of dividing by 2 any integer: 0 or 0.5. Thus multiplying by 2 and adding 1 gives a factor suitable for any digit to process, without using a test.

First of all: you can save two steps if you have the "1" in line 16 followed by a STO+1. This way the counter is incremented en passant and you can delete the three steps near the end that do it now.

Regarding the method of calculating a factor (1 or 2) from the R1 counter: I had a similar idea, and avoiding tests and GTOs is something I really like. In this case it could even be done with two steps less:

Code:
... RCL 1 2 / FRAC X=0? e^x /

The e^x turns a 0 into 1, so the digit is divided by either 0,5 (=doubled) or 1 (unchanged).

But... sometimes even good ideas don't work. All this would be fine, even with four steps saved, IF the 12C had an X<Y? test as originally shown in your listing (I now see you corrected this). But in fact the 12C features an X≤Y? test. This way the digit 9 will not get processed correctly. Since 9 ≤ 9 the test is true, so X=0? is also tested, which is false, so the CLX is not executed and the result is zero (9 – 9). So this method is not an option here.

HP25 users: this is your moment! You can implement the idea above with the following code sequence, since your calculator sports an X≥Y? test:

Code:
RCL 1 2 /         // divide digit position in R1 by 2 FRC       // fractional part is 0 for even or 0,5 for odd digit position X=0?      // if even... e^x       // ...turn zero into 1, else keep the 0,5 /         // divide digit by 0,5 or 1, i.e. multiply by 2 or 1 9 X≥Y?      // if result ≤ 9 CLX       // leave it as it is (subtract 0) -         // else subtract 9 to get the digit sum

Note: be sure to add an ENTER as the first line, or even better something useful like FIX 0. If you don't the following 10 may be appended to your input. This is one of the HP25's ..."special features".

Owners of HP calculators with the common eight test commands may replace the X≥Y? with an X≠Y? X>Y? sequence. Yes, that's another trick from the olden days... ;-)

Dieter
04-24-2018, 07:40 PM (This post was last modified: 04-24-2018 08:20 PM by Dieter.)
Post: #5
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Luhn algorithm
(04-18-2018 06:29 PM)pinkman Wrote:  referring to the wikipedia page of the Luhn algorithm, I propose an implementation for the 12c.

Here is a version for a special application of the Luhn algorithm. The latter is often used to add a check digit to a locomotive's class/serial number. The German Federal Railways have been using this method since 50 years now, which maybe is a good reason to introduce this special program version. ;-)

Code:
01  STO 0 02  0 03  STO 1 04  STO 2 05  R↓ 06  X=0? 07  GTO 33 08  1 09  0 10  ÷ 11  INT 12  LSTX 13  FRAC 14  1 15  0 16  x 17  2 18  RCL 1 19  - 20  STO 1 21  X=0? 22  GTO 30 23  x 24  9 25  X≤Y? 26  X=0? 27  CLX 28  - 29  ENTER 30  R↓ 31  STO+2 32  GTO 05 33  RCL 2 34  , 35  9 36  x 37  FRAC 38  STO+0 39  RCL 0 40  FIX 1 41  GTO 00

Usage:
Enter the six-digit vehicle number (class and serial number) and the program adds the check digit (right of the decimal point).

Example:
103 118 => 103.118,6
111 111 => 111.111,1

You can also use this program to calculate the check digit for other numbers with up to nine digits:
123456789 => 123.456.789,7

If you replace line 38...40 with "10 x" only the check digit is returned and up to 10 digits can be processed.
In this case you may also replace the initial STO 0 with FIX 0. ;-)

Dieter
04-24-2018, 08:27 PM
Post: #6
 pinkman Senior Member Posts: 387 Joined: Mar 2018
RE: (12C) Luhn algorithm
(04-24-2018 06:35 PM)Dieter Wrote:  First of all: you can save two steps if you have the "1" in line 16 followed by a STO+1. This way the counter is incremented en passant and you can delete the three steps near the end that do it now.
Yes!!

(04-24-2018 06:35 PM)Dieter Wrote:  But... sometimes even good ideas don't work. All this would be fine, even with four steps saved, IF the 12C had an X<Y? test as originally shown in your listing (I now see you corrected this). But in fact the 12C features an X≤Y? test. This way the digit 9 will not get processed correctly. Since 9 ≤ 9 the test is true, so X=0? is also tested, which is false, so the CLX is not executed and the result is zero (9 – 9). So this method is not an option here.
Whoo, lack of test on my side!
There is another way to avoid the >9 test: add the 2 numbers, even if there is a leading zero.
This can be done with:

Code:
 10 / Intg LastX Frac 10 * +

So I decided to store 10 in R2, to spare 2 lines.

New code is:

Code:
 01 1 02 0 03 Sto 2 04 / 05 Intg 06 LastX 07 Frac 08 Rcl 2 09 * 10 Rcl 1 11 2 12 / 13 Frac 14 2 15 * 16 1 17 Sto+ 1 18 + 19 * 20 Rcl 2 21 / 22 Intg 23 LastX 24 Frac 25 Rcl 2 26 * 27 + 28 Sto+ 0 29 Rv 30 Gto 00

This time I think it has been tested!
Same usage, but now R2 is used.
Result in R0, counter in R1.
04-25-2018, 07:22 AM (This post was last modified: 04-25-2018 07:23 AM by Dieter.)
Post: #7
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Luhn algorithm
(04-24-2018 08:27 PM)pinkman Wrote:  There is another way to avoid the >9 test: add the 2 numbers, even if there is a leading zero.

It can also be done with the >9 test.
Here is a version that processes the complete number, so you don't have to press R/S several times:

Code:
01  1 02  0 03  ÷ 04  INTG 05  LSTX 06  FRAC 07  1 08  0 09  x 10  RCL 1 11  2 12  ÷ 13  FRAC 14  2 15  x 16  1 17  STO+1 18  + 19  x 20  9 21  X<>Y 22  X≤Y? 23  GTO 26 24  X<>Y 25  - 26  STO+0 27  R↓ 28  R↓ 29  X=0? 30  GTO  32 31  GTO 01 32  RCL 1 33  RCL 0 34  GTO 00

R1 is returned in Y and R0 in X. Simply check if the last digit is zero. Yes, with a few more steps the program could also do this.

The code up to line 28 works like the previous versions, so it's even one step shorter. And R2 is not required. ;-)

Dieter
04-25-2018, 02:52 PM
Post: #8
 pinkman Senior Member Posts: 387 Joined: Mar 2018
RE: (12C) Luhn algorithm
Great!
 « Next Oldest | Next Newest »

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