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