HP-67 Base Conversion from HP Key Notes

[Thomas Klemm]

(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