HP Forums
HP-67 Base Conversion from HP Key Notes - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: HP-67 Base Conversion from HP Key Notes (/thread-4970.html)



HP-67 Base Conversion from HP Key Notes - Karl-Ludwig Butte - 10-19-2015 11:31 AM

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


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-19-2015 02:57 PM

(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


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-19-2015 04:08 PM

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


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-19-2015 06:32 PM

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.


RE: HP-67 Base Conversion from HP Key Notes - Karl-Ludwig Butte - 10-19-2015 07:35 PM

Hi Thomas,

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

Best regards

Karl


RE: HP-67 Base Conversion from HP Key Notes - TASP - 10-19-2015 09:06 PM

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.


Smile


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-19-2015 09:34 PM

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


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-19-2015 10:34 PM

(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/.


RE: HP-67 Base Conversion from HP Key Notes - Karl-Ludwig Butte - 10-20-2015 07:48 PM

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.

Thanks again for your superb answers.

Best regards

Karl


RE: HP-67 Base Conversion from HP Key Notes - Thomas Klemm - 10-21-2015 09:10 PM

(10-20-2015 07:48 PM)Karl-Ludwig Butte Wrote:  That's an excellent idea.

(HP-67) Base Conversion