+- 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 RTNThus 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 RTNExample: 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 INTAfter 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 RTNAnd 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.
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: 10111convert(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: 213convert(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: 21220You 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 /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