+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (12C) Luhn algorithm (/thread-10535.html)
(12C) Luhn algorithm - pinkman - 04-18-2018 06:29 PM
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)
Looking forward to reading you.
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 00RE: (12C) Luhn algorithm - Dieter - 04-23-2018 08:19 AM
(04-18-2018 06:29 PM)pinkman Wrote: referring to the wikipedia page of the Luhn algorithm, I propose an implementation for the 12c.
...
Looking forward to reading you.
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 00Initialize 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 00In 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
RE: (12C) Luhn algorithm - pinkman - 04-24-2018 08:00 AM
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 RtnRE: (12C) Luhn algorithm - Dieter - 04-24-2018 06:35 PM
(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 sumNote: 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
RE: (12C) Luhn algorithm - Dieter - 04-24-2018 07:40 PM
(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 00Usage:
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
RE: (12C) Luhn algorithm - pinkman - 04-24-2018 08:27 PM
(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 00This time I think it has been tested!
Same usage, but now R2 is used.
Result in R0, counter in R1.
RE: (12C) Luhn algorithm - Dieter - 04-25-2018 07:22 AM
(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 00R1 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
RE: (12C) Luhn algorithm - pinkman - 04-25-2018 02:52 PM
Great!