HP-67 Base Conversion from HP Key Notes
10-19-2015, 11:31 AM
Post: #1
 Karl-Ludwig Butte Member Posts: 123 Joined: Dec 2013
HP-67 Base Conversion from HP Key Notes
Dear All,

in HP Key Notes Vol. 3 No. 2 p. 13 there was a base conversion routine for the HP-67/97 written by Cass R. Lewart (Holmdel, New Jersey). In the following issue (Vol. 3 No. 3 p. 11) Bob Edelen corrected a missing program step in this routine.

The program works perfectly and even can convert directly from one non-decimal base to another non-decimal base (e.g. from base 2 to base 8) just by entering:

number
ENTER
original base
ENTER
new base
Function key A

The program listing is as follows:

001 *LBL A
002 STO 0
003 Roll Down
004 Enter
005 GSB 3
006 GSB 0
007 RCL 0
008 GSB 3
009 RCL 0
010 *LBL 0
011 STO 1
012 Roll Down
013 STO 2
014 Roll Down
015 STO 3
016 0
017 STO 4
018 1
019 STO 5
020 *LBL 1
021 RCL 3
022 X=0?
023 GTO 2
024 RCL 1
025 /
026 ENTER
027 INT
028 STO 3
029 -
030 RCL 1
031 x
032 RCL 5
033 x
034 INT
035 ST+4
036 RCL 2
037 STx5
038 GTO 1
039 *LBL 2
040 RCL 4
041 RTN
042 *LBL 3
043 1
044 -
045 LOG
046 INT
047 1
048 +
049 10^x
050 RTN

Alas, the original Key Notes article has not a tiny clue of how this routine works. And although I can see all the program steps I cannot reverse engineer the program to find out the algorithm which is behind this clever routine. I already did a Google search for base conversion algorithms but I only found descriptions for converting base X to base 10 and base 10 to base X. Most of them use string operations to seperate single digits.

So my question is: Can anyone of you math gurus of this forum please explain the algorithm of this base conversion routine to me?

Any hint will be very much appreciated.

Thank you very much in advance.

Best regards

Karl
10-19-2015, 02:57 PM (This post was last modified: 10-19-2015 06:35 PM by Thomas Klemm.)
Post: #2
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
(10-19-2015 11:31 AM)Karl-Ludwig Butte Wrote:  So my question is: Can anyone of you math gurus of this forum please explain the algorithm of this base conversion routine to me?

Here are some comments to the code:
Code:
001 *LBL A 002 STO 0                       ; save new base for later 003 Roll Down                   ; number    original base 004 Enter                       ; number    original base   original base 005 GSB 3                       ; number    original base   10^m 006 GSB 0                       ; number (in base 10^m) 007 RCL 0                       ; number    new base 008 GSB 3                       ; number    10^k 009 RCL 0                       ; number    10^k    new base     010 *LBL 0                      ; convert number z from y-base to x-base 011 STO 1                       ; to-base 012 Roll Down 013 STO 2                       ; from-base 014 Roll Down 015 STO 3                       ; number 016 0 017 STO 4                       ; total = 0 018 1 019 STO 5                       ; power = 1 020 *LBL 1 021 RCL 3 022 X=0?                        ; while number != 0 023 GTO 2 024 RCL 1 025 /                           ; number / to-base 026 ENTER                       ; number / to-base     number / to-base 027 INT 028 STO 3                       ; number = number >> 1 029 -                           ; FRAC(number / to-base) 030 RCL 1 031 x                           ; number MOD to-base (the right-most digit in from-base) 032 RCL 5 033 x                           ; digit * power (of from-base) 034 INT                         ; make sure to be an integer (probably due to rounding) 035 ST+4                        ; add to total 036 RCL 2 037 STx5                        ; power = power * from-base 038 GTO 1 039 *LBL 2                      ; number = 0 040 RCL 4                       ; total 041 RTN 042 *LBL 3                      ; find smallest power of 10 bigger or equal the input 043 1  044 - 045 LOG 046 INT 047 1 048 + 049 10^x 050 RTN

Thus the number is first translated from the original base to a base of $$10^m$$ and then from this to the new base.

These programs for the Base Conversion do a similar thing but only halfway. It's mostly only what is done in the sub-routine 0.

However the algorithm used in this program could be improved a little with the following trick.
Say you want to translate 23 to binary:
\begin{align} 23 \div 2 &= 11 & \, (1) \\ 11 \div 2 &= 5 & \, (1) \\ 5 \div 2 &= 2 & \, (1) \\ 2 \div 2 &= 1 & \, (0) \\ 1 \div 2 &= 0 & \, (1) \\ \end{align}

The remainders are then multiplied by powers of 10 and added:

\begin{align} 1 \times 10^0 &= 1 \\ 1 \times 10^1 &= 10 \\ 1 \times 10^2 &= 100 \\ 0 \times 10^3 &= 0\\ 1 \times 10^4 &= 10000 \\ &= 10111 \end{align}

We can write the remainders using the first equations:
\begin{align} 1 &= 23 - 2 \times 11 \\ 1 &= 11 - 2 \times 5 \\ 1 &= 5 - 2 \times 2 \\ 0 &= 2 - 2 \times 1 \\ 1 &= 1 - 2 \times 0 \\ \end{align}

We do the same multiplication by powers of 10:

\begin{align} 1 \times 10^0 &= 23 \times 10^0 - 2 \times 11 \times 10^0 \\ 1 \times 10^1 &= 11 \times 10^1 - 2 \times 5 \times 10^1 \\ 1 \times 10^2 &= 5 \times 10^2 - 2 \times 2 \times 10^2 \\ 0 \times 10^3 &= 2 \times 10^3 - 2 \times 1 \times 10^3 \\ 1 \times 10^4 &= 1 \times 10^4 - 2 \times 0 \times 10^4 \\ \end{align}

Now we can see that the same numbers appear on different lines. Thus we can re-group the sum:

\begin{align} & 23 \times 10^0 \\ + & 11 \times (10^1 - 2 \times 10^0) \\ + & 5 \times (10^2 - 2 \times 10^1) \\ + & 2 \times 10^3 - 2 \times 10^2) \\ + & 1 \times 10^4 - 2 \times 10^3) \\ \end{align}

We end up with:

\begin{align} & 23 \\ + & 11 \times 8 \\ + & 5 \times 80 \\ + & 2 \times 800 \\ + & 1 \times 8000 \\ \end{align}

Thus we can avoid calculating the remainders. We just need to calculate the sequence 23, 11, 5, 2, 1 and multiply by the correct factors.

Kind regards
Thomas
10-19-2015, 04:08 PM
Post: #3
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
Here's the version of the program that implements the trick mentioned in my previous post:

Code:
001 *LBL A 002  STO 0 003  RDN 004  ENTER 005  GSB 3 006  GSB 0 007  RCL 0 008  GSB 3 009  RCL 0 010 *LBL 0 011  STO 1 012  STO 5 013  RDN 014  STO 2 015  STO- 5 016  RDN 017  STO 3 018  STO 4 019 *LBL 1 020  RCL 3 021  X=0? 022  GTO 2 023  RCL 1 024  / 025  INT 026  STO 3 027  RCL 5 028  * 029  STO- 4 030  RCL 2 031  STO* 5 032  GTO 1 033 *LBL 2 034  RCL 4 035  RTN 036 *LBL 3 037  1 038  - 039  LOG 040  INT 041  1 042  + 043  10^x 044  RTN

Example: 3258 to base 3

325 ENTER
8 ENTER
3 A

21220

I tested the original program using an HP-11C and got 20219. This is probably due to this line:
Code:
034 INT

After changing it to RND (rounding) I got the correct result.
The program above isn't affected by this rounding problem.

Cheers
Thomas
10-19-2015, 06:32 PM
Post: #4
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
This variant uses some stackrobatic so we need only 4 registers instead of 6:

Code:
001 *LBL A 002  STO 3   ; new base 003  RDN     ; old base 004  STO 1   ; from 005  ENTER 006  GSB 3   ; 10^m base 007  GSB 0   ; convert n from old base to 10^m base 008  RCL 3   ; new base 009  GSB 3   ; 10^k base 010  STO 1   ; from 011  RCL 3   ; new base 012 *LBL 0   ; convert ( n_from from to -- n_to ) 013  STO 2   ; to 014  -       ; p = from - to 015  X<>Y    ; n_from 016  STO 0   ; n_to 017 *LBL 1   ; begin loop 018  RCL 1   ; from 019  x<>y 020  RCL 2   ; to 021  / 022  INT     ; n' = n >> 1 023  x=0 024  GTO 2   ; exit loop 025  RDN 026  *       ; p' = p * from 027  RDN 028  *       ; n' * p' 029  STO+ 0  ; n_to = n_to + n' * p' 030  RDN 031  GTO 1   ; end loop 032 *LBL 2   ; exit 033  RCL 0   ; n_to 034  RTN 035 *LBL 3   ; find power of 10 base 036  1 037  - 038  LOG 039  INT 040  1 041  + 042  10^x 043  RTN

And it's even a little shorter.
10-19-2015, 07:35 PM
Post: #5
 Karl-Ludwig Butte Member Posts: 123 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
Hi Thomas,

thanks a lot for your three posts, explaining the algorithm and optimizing the code - great work :-)

Best regards

Karl
10-19-2015, 09:06 PM
Post: #6
 TASP Senior Member Posts: 401 Joined: Mar 2015
RE: HP-67 Base Conversion from HP Key Notes
While I was running errands it occurred to me that perhaps someone could enter the program on an HP97 and run it with a few examples using 'TRACE' mode.

I've returned and see the problem is already taken care of.

You've all done very well.

2speed HP41CX,int2XMEM+ZEN, HPIL+DEVEL, HPIL+X/IO, I/R, 82143, 82163, 82162 -25,35,45,55,65,67,70,80
10-19-2015, 09:34 PM
Post: #7
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
There's another program Base Conversions for the HP-67 in the Old Software Library which was originally published in the HP-67 Math Pac 1.
It can even find the binary representation of $$\pi$$!

Should we still add the optimized program to the new HP-65/67/97 Software Library so it may be found easier?

Cheers
Thomas
10-19-2015, 10:34 PM (This post was last modified: 10-19-2015 10:36 PM by Thomas Klemm.)
Post: #8
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
(10-19-2015 09:06 PM)TASP Wrote:  (...) perhaps someone could enter the program on an HP97 and run it with a few examples using 'TRACE' mode.

Not exactly what you want but I quickly wrote a convert(n_from, from_base, to_base) function that let's you run the innermost loop. Thus either from_base or to_base must be a power of 10.

Here are the examples I used:

convert(23, 10, 2)
Code:
Code       |          X |          Y |          Z |          T | Register  LBL 1      |         23 |          8 |          0 |          0 | R0:         23  RCL 1      |         10 |         23 |          8 |          0 | R0:         23  X<>Y       |         23 |         10 |          8 |          0 | R0:         23  RCL 2      |          2 |         23 |         10 |          8 | R0:         23  /          |         11 |         10 |          8 |          8 | R0:         23  INT        |         11 |         10 |          8 |          8 | R0:         23  X=0        |         11 |         10 |          8 |          8 | R0:         23  RDN        |         10 |          8 |          8 |         11 | R0:         23  *          |         80 |          8 |         11 |         11 | R0:         23  RDN        |          8 |         11 |         11 |         80 | R0:         23  *          |         88 |         11 |         80 |         80 | R0:         23  STO+ 0     |         88 |         11 |         80 |         80 | R0:        111  RDN        |         11 |         80 |         80 |         88 | R0:        111  GTO 1      |         11 |         80 |         80 |         88 | R0:        111  LBL 1      |         11 |         80 |          0 |          0 | R0:        111  RCL 1      |         10 |         11 |         80 |          0 | R0:        111  X<>Y       |         11 |         10 |         80 |          0 | R0:        111  RCL 2      |          2 |         11 |         10 |         80 | R0:        111  /          |          5 |         10 |         80 |         80 | R0:        111  INT        |          5 |         10 |         80 |         80 | R0:        111  X=0        |          5 |         10 |         80 |         80 | R0:        111  RDN        |         10 |         80 |         80 |          5 | R0:        111  *          |        800 |         80 |          5 |          5 | R0:        111  RDN        |         80 |          5 |          5 |        800 | R0:        111  *          |        400 |          5 |        800 |        800 | R0:        111  STO+ 0     |        400 |          5 |        800 |        800 | R0:        511  RDN        |          5 |        800 |        800 |        400 | R0:        511  GTO 1      |          5 |        800 |        800 |        400 | R0:        511  LBL 1      |          5 |        800 |          0 |          0 | R0:        511  RCL 1      |         10 |          5 |        800 |          0 | R0:        511  X<>Y       |          5 |         10 |        800 |          0 | R0:        511  RCL 2      |          2 |          5 |         10 |        800 | R0:        511  /          |          2 |         10 |        800 |        800 | R0:        511  INT        |          2 |         10 |        800 |        800 | R0:        511  X=0        |          2 |         10 |        800 |        800 | R0:        511  RDN        |         10 |        800 |        800 |          2 | R0:        511  *          |       8000 |        800 |          2 |          2 | R0:        511  RDN        |        800 |          2 |          2 |       8000 | R0:        511  *          |       1600 |          2 |       8000 |       8000 | R0:        511  STO+ 0     |       1600 |          2 |       8000 |       8000 | R0:       2111  RDN        |          2 |       8000 |       8000 |       1600 | R0:       2111  GTO 1      |          2 |       8000 |       8000 |       1600 | R0:       2111  LBL 1      |          2 |       8000 |          0 |          0 | R0:       2111  RCL 1      |         10 |          2 |       8000 |          0 | R0:       2111  X<>Y       |          2 |         10 |       8000 |          0 | R0:       2111  RCL 2      |          2 |          2 |         10 |       8000 | R0:       2111  /          |          1 |         10 |       8000 |       8000 | R0:       2111  INT        |          1 |         10 |       8000 |       8000 | R0:       2111  X=0        |          1 |         10 |       8000 |       8000 | R0:       2111  RDN        |         10 |       8000 |       8000 |          1 | R0:       2111  *          |      80000 |       8000 |          1 |          1 | R0:       2111  RDN        |       8000 |          1 |          1 |      80000 | R0:       2111  *          |       8000 |          1 |      80000 |      80000 | R0:       2111  STO+ 0     |       8000 |          1 |      80000 |      80000 | R0:      10111  RDN        |          1 |      80000 |      80000 |       8000 | R0:      10111  GTO 1      |          1 |      80000 |      80000 |       8000 | R0:      10111  LBL 1      |          1 |      80000 |          0 |          0 | R0:      10111  RCL 1      |         10 |          1 |      80000 |          0 | R0:      10111  X<>Y       |          1 |         10 |      80000 |          0 | R0:      10111  RCL 2      |          2 |          1 |         10 |      80000 | R0:      10111  /          |          0 |         10 |      80000 |      80000 | R0:      10111  INT        |          0 |         10 |      80000 |      80000 | R0:      10111  X=0        |          0 |         10 |      80000 |      80000 | R0:      10111  GTO 2      |          0 |         10 |      80000 |      80000 | R0:      10111  LBL 2      |          0 |         10 |      80000 |      80000 | R0:      10111  RCL 0      |      10111 |          0 |         10 |      80000 | R0:      10111

convert(325, 8, 10)
Code:
Code       |          X |          Y |          Z |          T | Register  LBL 1      |        325 |         -2 |          0 |          0 | R0:        325  RCL 1      |          8 |        325 |         -2 |          0 | R0:        325  X<>Y       |        325 |          8 |         -2 |          0 | R0:        325  RCL 2      |         10 |        325 |          8 |         -2 | R0:        325  /          |         32 |          8 |         -2 |         -2 | R0:        325  INT        |         32 |          8 |         -2 |         -2 | R0:        325  X=0        |         32 |          8 |         -2 |         -2 | R0:        325  RDN        |          8 |         -2 |         -2 |         32 | R0:        325  *          |        -16 |         -2 |         32 |         32 | R0:        325  RDN        |         -2 |         32 |         32 |        -16 | R0:        325  *          |        -64 |         32 |        -16 |        -16 | R0:        325  STO+ 0     |        -64 |         32 |        -16 |        -16 | R0:        261  RDN        |         32 |        -16 |        -16 |        -64 | R0:        261  GTO 1      |         32 |        -16 |        -16 |        -64 | R0:        261  LBL 1      |         32 |        -16 |          0 |          0 | R0:        261  RCL 1      |          8 |         32 |        -16 |          0 | R0:        261  X<>Y       |         32 |          8 |        -16 |          0 | R0:        261  RCL 2      |         10 |         32 |          8 |        -16 | R0:        261  /          |          3 |          8 |        -16 |        -16 | R0:        261  INT        |          3 |          8 |        -16 |        -16 | R0:        261  X=0        |          3 |          8 |        -16 |        -16 | R0:        261  RDN        |          8 |        -16 |        -16 |          3 | R0:        261  *          |       -128 |        -16 |          3 |          3 | R0:        261  RDN        |        -16 |          3 |          3 |       -128 | R0:        261  *          |        -48 |          3 |       -128 |       -128 | R0:        261  STO+ 0     |        -48 |          3 |       -128 |       -128 | R0:        213  RDN        |          3 |       -128 |       -128 |        -48 | R0:        213  GTO 1      |          3 |       -128 |       -128 |        -48 | R0:        213  LBL 1      |          3 |       -128 |          0 |          0 | R0:        213  RCL 1      |          8 |          3 |       -128 |          0 | R0:        213  X<>Y       |          3 |          8 |       -128 |          0 | R0:        213 RCL 2      |         10 |          3 |          8 |       -128 | R0:        213 /          |          0 |          8 |       -128 |       -128 | R0:        213 INT        |          0 |          8 |       -128 |       -128 | R0:        213 X=0        |          0 |          8 |       -128 |       -128 | R0:        213 GTO 2      |          0 |          8 |       -128 |       -128 | R0:        213 LBL 2      |          0 |          8 |       -128 |       -128 | R0:        213 RCL 0      |        213 |          0 |          8 |       -128 | R0:        213

convert(213, 10, 3)
Code:
Code       |          X |          Y |          Z |          T | Register  LBL 1      |        213 |          7 |          0 |          0 | R0:        213 RCL 1      |         10 |        213 |          7 |          0 | R0:        213 X<>Y       |        213 |         10 |          7 |          0 | R0:        213 RCL 2      |          3 |        213 |         10 |          7 | R0:        213 /          |         71 |         10 |          7 |          7 | R0:        213 INT        |         71 |         10 |          7 |          7 | R0:        213 X=0        |         71 |         10 |          7 |          7 | R0:        213 RDN        |         10 |          7 |          7 |         71 | R0:        213 *          |         70 |          7 |         71 |         71 | R0:        213 RDN        |          7 |         71 |         71 |         70 | R0:        213 *          |        497 |         71 |         70 |         70 | R0:        213 STO+ 0     |        497 |         71 |         70 |         70 | R0:        710 RDN        |         71 |         70 |         70 |        497 | R0:        710 GTO 1      |         71 |         70 |         70 |        497 | R0:        710 LBL 1      |         71 |         70 |          0 |          0 | R0:        710 RCL 1      |         10 |         71 |         70 |          0 | R0:        710 X<>Y       |         71 |         10 |         70 |          0 | R0:        710 RCL 2      |          3 |         71 |         10 |         70 | R0:        710 /          |         23 |         10 |         70 |         70 | R0:        710 INT        |         23 |         10 |         70 |         70 | R0:        710 X=0        |         23 |         10 |         70 |         70 | R0:        710 RDN        |         10 |         70 |         70 |         23 | R0:        710 *          |        700 |         70 |         23 |         23 | R0:        710 RDN        |         70 |         23 |         23 |        700 | R0:        710 *          |       1610 |         23 |        700 |        700 | R0:        710 STO+ 0     |       1610 |         23 |        700 |        700 | R0:       2320 RDN        |         23 |        700 |        700 |       1610 | R0:       2320 GTO 1      |         23 |        700 |        700 |       1610 | R0:       2320 LBL 1      |         23 |        700 |          0 |          0 | R0:       2320 RCL 1      |         10 |         23 |        700 |          0 | R0:       2320 X<>Y       |         23 |         10 |        700 |          0 | R0:       2320 RCL 2      |          3 |         23 |         10 |        700 | R0:       2320 /          |          7 |         10 |        700 |        700 | R0:       2320 INT        |          7 |         10 |        700 |        700 | R0:       2320 X=0        |          7 |         10 |        700 |        700 | R0:       2320 RDN        |         10 |        700 |        700 |          7 | R0:       2320 *          |       7000 |        700 |          7 |          7 | R0:       2320 RDN        |        700 |          7 |          7 |       7000 | R0:       2320 *          |       4900 |          7 |       7000 |       7000 | R0:       2320 STO+ 0     |       4900 |          7 |       7000 |       7000 | R0:       7220 RDN        |          7 |       7000 |       7000 |       4900 | R0:       7220 GTO 1      |          7 |       7000 |       7000 |       4900 | R0:       7220 LBL 1      |          7 |       7000 |          0 |          0 | R0:       7220 RCL 1      |         10 |          7 |       7000 |          0 | R0:       7220 X<>Y       |          7 |         10 |       7000 |          0 | R0:       7220 RCL 2      |          3 |          7 |         10 |       7000 | R0:       7220 /          |          2 |         10 |       7000 |       7000 | R0:       7220 INT        |          2 |         10 |       7000 |       7000 | R0:       7220 X=0        |          2 |         10 |       7000 |       7000 | R0:       7220 RDN        |         10 |       7000 |       7000 |          2 | R0:       7220 *          |      70000 |       7000 |          2 |          2 | R0:       7220 RDN        |       7000 |          2 |          2 |      70000 | R0:       7220 *          |      14000 |          2 |      70000 |      70000 | R0:       7220 STO+ 0     |      14000 |          2 |      70000 |      70000 | R0:      21220 RDN        |          2 |      70000 |      70000 |      14000 | R0:      21220 GTO 1      |          2 |      70000 |      70000 |      14000 | R0:      21220 LBL 1      |          2 |      70000 |          0 |          0 | R0:      21220 RCL 1      |         10 |          2 |      70000 |          0 | R0:      21220 X<>Y       |          2 |         10 |      70000 |          0 | R0:      21220 RCL 2      |          3 |          2 |         10 |      70000 | R0:      21220 /          |          0 |         10 |      70000 |      70000 | R0:      21220 INT        |          0 |         10 |      70000 |      70000 | R0:      21220 X=0        |          0 |         10 |      70000 |      70000 | R0:      21220 GTO 2      |          0 |         10 |      70000 |      70000 | R0:      21220 LBL 2      |          0 |         10 |      70000 |      70000 | R0:      21220 RCL 0      |      21220 |          0 |         10 |      70000 | R0:      21220

You can use it with your own examples if you want. Just follow the link above and click run.
Enter the convert function with the desired parameters into the black box and hit the Enter key.

Cheers
Thomas

PS: I cheated a little with this line:
Code:
021  /
As the next step is INT I didn't bother with floating point numbers and just used integer division. On a HP-42S both steps could be replaced by BASE/.
10-20-2015, 07:48 PM
Post: #9
 Karl-Ludwig Butte Member Posts: 123 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
Hi Thomas,

(10-19-2015 09:34 PM)Thomas Klemm Wrote:  Should we still add the optimized program to the new HP-65/67/97 Software Library so it may be found easier?

That's an excellent idea.

Best regards

Karl
10-21-2015, 09:10 PM
Post: #10
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: HP-67 Base Conversion from HP Key Notes
(10-20-2015 07:48 PM)Karl-Ludwig Butte Wrote:  That's an excellent idea.

(HP-67) Base Conversion
 « Next Oldest | Next Newest »

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