(11C) (15C) Very fast binary converter + fast modulo

[Michael Zinn]

This program can convert numbers to binary quickly by using a lookup table to convert 4 bits at once. Internally, it also uses a fast modulo calculation.

How to use the three programs:

A: Create a lookup table in registers 1 to 15. This takes about 3 minutes.
B: Convert a number to binary. If you created the table this will be fast. Without the table it will be 3x slower.
D: y mod x

The B program reads flag 0: If it is clear it will use a slow algorithm, if it is set it will use the fast one instead. Program A clears flag 0, creates the lookup table and then sets flag 0.


In my custom notation the code looks like this:

Code:


; create lookup table
A:
  flag0 = false    ; slow algorithm
  15
  i=
  0:               ; for(i = 15, i > 0, i--)
    i
    int
    gosub B        ; to binary
    register[i]=
    decrementSkipEqual
      goto 0
  flag0 = true
  return


; toBinary with lookup table
B:
  0                ; the result
  register[0]=     ; exponent
  x >< y

  1:               ; begin loop
    if(x == 0)
      goto 4
    register[16]=  ; store input

    if(flag0)
      goto 2       ; fast algorithm
    ;else
      ; slow algorithm
      2
      gosub D      ; (`mod` 2)
      register[0]
      10^x
      *
      +
      1
      register[0] +=
      pop
      register[16]

      2
      /
      int
      goto 1

    ; fast (fetch 4 bits using the lookup table)
    2:

      ; fetch 4 bits from input
      16
      gosub D      ; (`mod` 16)

      if(x == 0)
        goto 3
      ;else
        ; lookup binary
        i=
        pop
        register[i]
      3:

      ; shift result bits to the left and add to result
      register[0]
      10^x
      *
      +

      ; increment left shift amount for next iteration
      4
      register[0] +=
      pop

      ; input `shr` 4
      register[16]
      16
      /
      int

    goto 1 ; end loop

  4:
  pop
  return


; fast modulo
D:
  register[17]=
  /
  fractional
  register[17]
  *
  return

However, for entering it into the calculator, the classical button notation might be easier:

Code:


LBL A
CF 0
1
5
STO I
LBL 0
RCL I
GSB B
STO (i)
DSE
GTO 0
SF 0
RTN

LBL B
0
STO 0
x><y
LBL 1
x=0
GTO 4
STO . 6
F? 0
GTO 2
2
GSB D
RCL 0
10^x
*
+
1
STO + 0
R\/
RCL . 6
2
/
int
GTO 1
LBL 2
1
6
GSB D
x=0
GTO 3
STO I
R\/
RCL (i)
LBL 3
RCL 0
10^x
*
+
4
STO + 0
R\/
RCL . 6
1
6
/
int
GTO 1
LBL 4
R\/
RTN

LBL D
STO . 7
/
FRAC
RCL 17
*
RTN

If you want to know how I wrote this you can read my blog post about it.

[Dieter]

(03-14-2018 10:07 PM)michaelzinn Wrote:  This program can convert numbers to binary quickly by using a lookup table to convert 4 bits at once.

That's a nice idea which results in a significantly faster program.

(03-14-2018 10:07 PM)michaelzinn Wrote:  Internally, it also uses a fast modulo calculation.

The program uses this routine at LBL D for calculating x mod 2. This works well with the implemented method, calculating 2 · frac(x/2), but it's not a good idea for a general modulo function: try 25 mod 7 to get 3,999999997 instead of 4.

A better method for a mod b is  a – b · int(a/b):

Code:

LBL D
X<>Y
STO .7
X<>Y
/
LastX
X<>Y
INT
x
RCL .7
X<>Y
–
RTN

Of course this is slower than the frac method, but it yields better results.

If you want to stay with the original method: this can be done without using a data register:

Code:

LBL D
/
LastX
X<>Y
FRAC
x
RTN

Oh, I just notice this is your first post here. So, welcome to the forum. :-)

Dieter

[Gene]

Yes, Michael... welcome to the forum. Please post more often.

Don't worry... Dieter can reprogram ANYONE's efforts and make them better. :-) He always does and I am very glad about it.

The key is to post ideas, thoughts, programs, and then we all can learn and sometimes help improve.

Welcome to the community here!

[Michael Zinn]

Hi!

>The program uses this routine at LBL D for calculating x mod 2. This works well with the implemented method, calculating 2 · frac(x/2), but it's not a good idea for a general modulo function: try 25 mod 7 to get 3,999999997 instead of 4.

I actually tested that and it gave me 4, but I don't have a real calculator so I'm doing all this in the i11 Android app. Can anyone recommend a more accurate emulator?

> If you want to stay with the original method: this can be done without using a data register:

Heh, I ignored LastX and how stack lifting works because I didn't understand it quickly. I guess I should go back to reading the manual.

Also, how exactly are numbers stored in registers? The app I'm using might be inaccurate here, do real HP calculators use decimals with a floating point? Or is it binary?

> welcome to the [...]
Thank you both

[Dieter]

(03-17-2018 06:06 PM)michaelzinn Wrote:  > try 25 mod 7 to get 3,999999997 instead of 4.
I actually tested that and it gave me 4, but I don't have a real calculator so I'm doing all this in the i11 Android app.

The basic problem is that it is impossible to exactly represent all fractions with a limited number of digits. 1/7 = 0,142857142857...., so multiplying this by 7 again with finite precision will never yield an integer result. Rounding helps here and there, but not in any case.

In the 25 mod 7 case this happens with 10-digit precision:

25/7 => 3,571428571
FRAC => 0,5714285710
x 7 => 3,9999999997

It gets even worse with 25000 mod 7:

25000/7 => 3571,428571
FRAC => 0,4285710000  // now only six decimals are left !
x 7 => 2,999997000

(03-17-2018 06:06 PM)michaelzinn Wrote:  Can anyone recommend a more accurate emulator?

Sorry, no idea. But you seem to use a simulator instead of an an emulator (which would reproduce the real thing exactly, running the original firmware). If, for instance, the calculations in your simulator are performend in standard 15-digit binary arithmetics, roundoff errors like the one above are covered since only 10 digits are visible in the display.

What do you get if you see the result "4" with the modulo routine and then subtract 4 from this? It is 0 or something different?
And what is the result if you calculate 10/3 (=3,333333333) and then double the result? Is it 6,666666666 or 6,666666667 ?

(03-17-2018 06:06 PM)michaelzinn Wrote:  Heh, I ignored LastX and how stack lifting works because I didn't understand it quickly. I guess I should go back to reading the manual.

From your blog post I understand that all this is new to you and something like ..."vintage computing", while most of the members here have grown up with all this, and RPN is nothing that one even has to think about – it feels natural and intuitive. ;-)

(03-17-2018 06:06 PM)michaelzinn Wrote:  Also, how exactly are numbers stored in registers? The app I'm using might be inaccurate here, do real HP calculators use decimals with a floating point? Or is it binary?

No, it's decimal arithmetics (BCD). The internal registers consist of 7 bytes = 56 bits with one nybble (4 bits) for each digit in mantissa (10) and exponent (2), and two more for their respective signs.

Since the mid-seventies most HPs use extended internal precision with 3 more guard digits for their calculations. This significantly improves the accuracy of the more complex functions since these are calculated with 13-digit internal precision before the result is rounded back to 10 digits and returned to the user.

Dieter

[Michael Zinn]

Thank you, that is very helpful. I guess this means that multiplication/division by 2/5/10 etc. is totally safe .

The simulator seems to use binary, but it uses so much bits that I get about 15 decimal digits of precision (e.g. if I do 1/3 it looks like 0.333333333333333 followed by a bunch of random looking digits).

25000 mod 7 results in 3.

Yes, I see this as a fun vintage computing experience. I wanted to try something that was new to me and solving problems by programming the calculator is an interesting puzzle (It's very far removed from high level languages like Haskell or even Java).

Thank you again for your very helpful responses.

[Michael Zinn]

I'm currently running out of labels and registers so here is a slow, compact version that only uses register I and .6 and only one extra label (for 15C):

Code:

; toBinary(x)
LBL 5:
  FIX 0
  0              ; put 0 on the stack as the result "variable"
  STO I          ; initialize exponent to 0
  x >< y

  LBL 6               ; begin while loop
    STO .6
    2
    GSB 2        ; (`mod` 2)
    RCL I
    10^x
    *
    +
    1
    STO + I
    R v
    RCL .6

    2              ;
    /              ; right shift
    INT            ;

    TEST 0 (x != 0)
      GTO 6         ; end while loop

  R v
  RTN

[Thomas Klemm]

This is another program to convert decimals to binary:

Code:

   001 {    44 25 } STO I
   002 {        8 } 8
   003 {       34 } X<=>Y
   004 { 42 21  0 } f LBL 0
   005 {        1 } 1
   006 {        0 } 0
   007 {       34 } X<=>Y
   008 {        2 } 2
   009 {       10 } /
   010 {    43 44 } g INT
   011 {    43 20 } g x==0
   012 {    22  1 } GTO 1
   013 {       33 } Rv
   014 {       20 } *
   015 {       33 } Rv
   016 {       20 } *
   017 { 44 40 25 } STO + I
   018 {       33 } Rv
   019 {    22  0 } GTO 0
   020 { 42 21  1 } f LBL 1
   021 {    45 25 } RCL I

It uses no registers apart from I.
Also it doesn't use MOD but only the INT function.

It's a translation of the following Python program:

Code:

def bin(n):
    s = n
    k = 8
    while n:
        n //= 2
        s += k * n
        k *= 10
    return s

Example

23
R/S

10111.


References

• Base Conversion
  

[Steve Simpkin]

(03-17-2018 06:06 PM)Michael Zinn Wrote:  ...
I actually tested that and it gave me 4, but I don't have a real calculator so I'm doing all this in the i11 Android app. Can anyone recommend a more accurate emulator?
...

Try JRPN 15C. It appears to be a true emulation of the HP-15C rather than a simulation.
https://play.google.com/store/apps/detai...ial.jrpn15

[johnb]

(03-17-2018 09:17 PM)Dieter Wrote:  From your blog post I understand that all this is new to you and something like ..."vintage computing", while most of the members here have grown up with all this, and RPN is nothing that one even has to think about – it feels natural and intuitive. ;-)

(03-18-2018 12:14 AM)Michael Zinn Wrote:  Yes, I see this as a fun vintage computing experience. I wanted to try something that was new to me and solving problems by programming the calculator is an interesting puzzle (It's very far removed from high level languages like Haskell or even Java).

I think most if not all of us here find this a laudable goal. At some point, to someone, *everything* becomes a vintage computing experience... there's a prof at Drexel University whom I follow, who is probably currently the world's foremost expert on programming the ENIAC! Now that's vintage!!

(03-17-2018 06:06 PM)michaelzinn Wrote:  Also, how exactly are numbers stored in registers? The app I'm using might be inaccurate here, do real HP calculators use decimals with a floating point? Or is it binary?

(03-17-2018 09:17 PM)Dieter Wrote:  No, it's decimal arithmetics (BCD). The internal registers consist of 7 bytes = 56 bits with one nybble (4 bits) for each digit in mantissa (10) and exponent (2), and two more for their respective signs.

There's another prof, this time at Auburn University, who has successfully instituted a policy that you don't graduate there with a CS degree without doing at least a one semester project implementation on "old iron," i.e. a vintage computer with an architecture unlike most current architectures.

Too many software engineers who grew up on Intel CPU chips assume that every digital computer has always been:
* binary
* two's complement
* little-endian
* "reals" represented by "mantissa & exponent" floating point
* hardware-implementation of subroutine call stack
* protected memory
etc...

The long road of computing development is far more interesting than that, however, and it's fascinating to sometimes find remnants of that in calculators or other interesting pieces of hardware!

(Yes, there have been machines that did base-10 in hardware (ENIAC was one!), or used one's complement or even weirder representations; fixed-point approximations of reals; other formats such as numerator/denominator; no hardware stack; no "call" or "return" instructions; flat address space; weird multiple address spaces; et cetera.)

[Thomas Klemm]

(03-03-2024 07:25 PM)Steve Simpkin Wrote:  It appears to be a true emulation of the HP-15C rather than a simulation.

Quote:About this app
Scientific calculator that simulates an HP-15C.

But I consider it a good simulation.
If you don't want to install it, you can also run it in a browser.

Here's the code that can be loaded using: File → Import Program → Import from Clipboard

Code:

   001 { 42 21 11 } f LBL A
   002 { 43  5  0 } g CF 0
   003 {        1 } 1
   004 {        5 } 5
   005 {    44 25 } STO I
   006 { 42 21  0 } f LBL 0
   007 {    45 25 } RCL I
   008 {    32 12 } GSB B
   009 {    44 24 } STO (i)
   010 { 42  5 25 } f DSE I
   011 {    22  0 } GTO 0
   012 { 43  4  0 } g SF 0
   013 {    43 32 } g RTN
   014 { 42 21 12 } f LBL B
   015 {        0 } 0
   016 {    44  0 } STO 0
   017 {       34 } X<=>Y
   018 { 42 21  1 } f LBL 1
   019 {    43 20 } g x==0
   020 {    22  4 } GTO 4
   021 {    44 .6 } STO 16
   022 { 43  6  0 } g F? 0
   023 {    22  2 } GTO 2
   024 {        2 } 2
   025 {    32 14 } GSB D
   026 {    45  0 } RCL 0
   027 {       13 } 10^x
   028 {       20 } *
   029 {       40 } +
   030 {        1 } 1
   031 { 44 40  0 } STO + 0
   032 {       33 } Rv
   033 {    45 .6 } RCL 16
   034 {        2 } 2
   035 {       10 } /
   036 {    43 44 } g INT
   037 {    22  1 } GTO 1
   038 { 42 21  2 } f LBL 2
   039 {        1 } 1
   040 {        6 } 6
   041 {    32 14 } GSB D
   042 {    43 20 } g x==0
   043 {    22  3 } GTO 3
   044 {    44 25 } STO I
   045 {       33 } Rv
   046 {    45 24 } RCL (i)
   047 { 42 21  3 } f LBL 3
   048 {    45  0 } RCL 0
   049 {       13 } 10^x
   050 {       20 } *
   051 {       40 } +
   052 {        4 } 4
   053 { 44 40  0 } STO + 0
   054 {       33 } Rv
   055 {    45 .6 } RCL 16
   056 {        1 } 1
   057 {        6 } 6
   058 {       10 } /
   059 {    43 44 } g INT
   060 {    22  1 } GTO 1
   061 { 42 21  4 } f LBL 4
   062 {       33 } Rv
   063 {    43 32 } g RTN
   064 { 42 21 14 } f LBL D
   065 {    44 .7 } STO 17
   066 {       10 } /
   067 {    42 44 } f FRAC
   068 {    45 .7 } RCL 17
   069 {       20 } *
   070 {    43 32 } g RTN

[Steve Simpkin]

(03-03-2024 09:01 PM)Thomas Klemm Wrote:  

(03-03-2024 07:25 PM)Steve Simpkin Wrote:  It appears to be a true emulation of the HP-15C rather than a simulation.

Quote:About this app
Scientific calculator that simulates an HP-15C.

But I consider it a good simulation.
If you don't want to install it, you can also run it in a browser.
...

I missed the part about being a simulation. I was going on the results of various calculations that appear to give the exact same answers as a real HP-15C.

[John Keith]

(03-03-2024 08:53 PM)johnb Wrote:  Too many software engineers who grew up on Intel CPU chips assume that every digital computer has always been:
* binary
* two's complement
* little-endian
* "reals" represented by "mantissa & exponent" floating point
* hardware-implementation of subroutine call stack
* protected memory
etc...

The long road of computing development is far more interesting than that, however, and it's fascinating to sometimes find remnants of that in calculators or other interesting pieces of hardware!

(Yes, there have been machines that did base-10 in hardware (ENIAC was one!), or used one's complement or even weirder representations; fixed-point approximations of reals; other formats such as numerator/denominator; no hardware stack; no "call" or "return" instructions; flat address space; weird multiple address spaces; et cetera.)

One of the more interesting ones: balanced ternary.

[Thomas Klemm]

(03-03-2024 09:15 PM)Steve Simpkin Wrote:  I was going on the results of various calculations that appear to give the exact same answers as a real HP-15C.

The random number generator is a dead giveaway:

(11-06-2014 08:03 PM)Thomas Klemm Wrote:  CLx
STO RAN#
RAN#
CLEAR PREFIX
1017980433

This simulator produces 6156294087 instead.

Apparently the dart:math.Random class is used:
RandomGenerator in jrpn/lib/jrpn15/model15c.dart

---

Cf. A Python program that simulates the RAN# function of the HP-15C