16-bit values: be smart (5)

Context

We now have conversion operators to handle 16-bit integers. We also created a piece of code to display 16-bit integers as decimal numbers.
The code was quite verbose however. Using those operators, one should really be careful regarding the "type" used. Do not use 16-bit integers when it's not needed.

Here, for example, we have

• One integer N (16-bit)
• divided by ten
• divisor is always 10: 8-bit
• remainder is always less than ten: 8-bit
• quotient may be more than 256: 16-bit
• else flag used by division: 8-bit
• Take remainder and add 48 to have a char
• 48 can be added using 6x8, all of them (including remainder) are always less than 256: 8-bit
• Clear remaining part of divisor: 8-bit
• Move quotient and start again: 16-bit

There is a huge place to improve code here.

The best way is probably to write BF instructions for 8-bit and plain text instructions for 16-bit, and finally replace plain text, to avoid mistakes.

Example:

WHILE

    RIGHT

    >>>++++++++++<<<

    LEFT

    WHILE

        MINUS

        RIGHT

        +>>+>-[-<]<[> RIGHT PLUS LEFT <-<<[->>>+<<<]>]<

        LEFT

    LOOP

    RIGHT

    <++++++[->++++++++<]>>>>[-]

......

LOOP

[.[-] <<< LEFT]

Then, replace WHILE, RIGHT, ... (and you can also remove all '< >' or '> <')

Minified code to print 2056 - 75% smaller - try it

>>>++++++++>++++++++[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>>>>++++++++++<<<<<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]+>[<-]<[->>-<<<]>>->>>>+>>+>-[<-]<[->>>>>+<+>[<-]<[->>+<<<]><<<<<<[->>>+<<<]>]<<<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>++++++[->++++++++<]>>>>[-]>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]+>[<-]<[->>-<<<]>>-<<<<+<+>[<-]<[->>+<<<]>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]<<[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]<<[.[-]<<<<<<<]

16-bit values: summary and application (4)

Context

Here is a summary of our structures, and operations implemented to handle the basic 8 ones

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Cursor on A

Operation	"4 cells"	"3 cells"
,(read)	,>[-]<	,>[-]<
.(print)	.	.
<(move left)	<<<<	<<<
>(move right)	>>>>	>>>
+(inc)	+<+>[<-]<[->>+<<<]>>	+[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>+<<]>
-(dec)	<+>[<-]<[->>-<<<]>>-	[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>-<<]>-
[(while)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>
](loop)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Application

Let's reuse our previous "decimal printing" algorithm, and replace each instruction by its new implementation, to print a large number (let's say 2056)

Code - 4 cells structure - try it

generate 2056 using 4 cells structure
>>>>>>++++++++>++++++++<
decimal print algorithm rewritten using instruction replacements
>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>>>>>>>>>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>+<+>[<-]<[->>+<<<]>>>>>>>>>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<<+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<+<+>[<-]<[->>+<<<]>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<<<<<<<<<<<<<+<+>[<-]<[->>+<<<]>>>>>>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<+>[<-]<[->>-<<<]>>-.>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Note: 3 cells version's code is about 50% longer, but it's also 3 times longer to execute...

Calc tool

Context

Let's implement a calculation tool. Inputs will be operations as [operand 1][operator][operand 2] and output will be the operation with its result

Initial state

• Memory: empty
• Cursor: first cell
• Input: an operation [operand][operator][operand] where operatands are numbers in base 10, and operator one of + - * /

Process

• Read input - memory after reading should be operand operator_flag operand 0 0 0 0 ....
• Print char (faster than rebuilding it afterwards)
• Use a switch/case
• If it's a *, set operator flag to 0 (do nothing) and start reading a new integer
• Same for +, - and * but set operator flag to 1, 2 or 3
• Otherwise, it's a digit: build integer
• multiply previously read integer by 10
• add the new digit
• Move operator to have operand 0 operand operator flag switch_flag
• Set switch_flag to 1 and use another switch/case
• Flag is 0: multiply numbers and store result in second cell
• Flag is 1 or 2: same, but sums up or subtract numbers
• Flag is 3: move operand 2, then perform division
• Display = symbol
• Display result
• If it's 0, then display '0'
• Otherwise, display the computed integer

Code - try it

Codes:
Multpily 42
Add 43
Subtract 45
Divide 47

>,[
  print char
  .
  subtract 42
  >++++++[-<------->]+<
  [
    not a multiplication
    -
    [
      not an addition
      --
      [
        not a subtraction
        --
        [
          not a division
          this is a digit
          build number
          ->++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]
        ]>[-
          this is a division
          set operation flag to 3 and start new number
          <+++>>>
        ]<
      ]>[-
        this is a subtraction
        set operation flag to 2 and start new number
        <++>>>
      ]<
    ]>[-
      this is an addition
      set operation flag to 2 and start new number
      <+>>>
    ]<
  ]>[-
    this is a multiplication
    start new number
    >>
  ]
  read next char
  <,
]
move operator
<<[->>+<<]>>
>+<[
  not a multiplication
  -
  [
    not an addition
    -
    [->-<
      division
      move operand 2
      <[->>+<<]
      divide
      <<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]
      clear and move result
      >[-]>>>[-]>[-<<<<+>>>>]<<
    ]>[-
      subtraction
      <<<<[->+<]>>[-<->]>>
    ]<
  ]>[-
    addition
    <<[-<+>]<<[->+<]>>>>
  ]<
]>[-
  multiplication
  <<<<[->>[-<+>>+<]>[-<+>]<<<]
  clean operands
  >>[-]>>
]

print =
+++++++++[-<+++++++>]<--.[-]

<+<[>-<
  print result if not 0
  [>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]
]>[
  or print 0
  +++++++[-<++++++>]<.[-]
]

Final state

• Memory: empty
• Cursor: second cell
• Input: empty
• Output: the operation followed by equal sign and its result

Note: of course, this is a calc tool valid in the Z/256Z group, meaning that all inputs and results are taken modulo 256. Moreover, the division is actually an euclidean division, so result is not displayed completely (only the quotient is)

Display all prime numbers

Context

A prime number is a number that allows only 2 distinct divisors: 1 and itself.
First prime numbers are 2, 3, 5, 7, 11 ...
Computing all prime numbers up to a limit can be implemented using a sieve, that works like this

• Generate an array of all integers from 2 up to the limit
• Go to the first non-null item in the array
• This number N is prime
• Then, reset array items every N cells starting from this one

Example: 2 is prime, and all multiple of 2 are removed, then 3 is a prime and all multiples of 3 are removed, including 6 that will be reset twice (once for 2, and once for 3), then 4 is null (reset by 2), so move to 5, ...

Initial state

• Memory: empty
• Cursor: first cell
• Input: any

Process

• First, define a 'comma' on first cell (code: 44), because we'll display comma-separated numbers, so it avoids building the comma everytime.
• Note: this is equivalent to a constant value in other programming languages...
• Then, generate all numbers from limit to 2, in decreasing order, in a 2-cells array, but this time it'll be [{value, 1}]  instead of [{1, value}] (code is a bit shorter)
• Generate the limit (using '-', we'll have 255, the biggest possible value)
• Set next cell to 1
• While current value is not null
• Copy 2 cells ahead
• Set next cell to 1
• Decrease copied value by 1, and stay on this value
• Result will be an array from 255 to 0, let's just remove the extra cells at the end.
• Finally, go to the first cell
• If value is not null
• Print the number
• Print comma
• Copy / move it twice: one for backup, one for counter
• Iterate on all array cells
• Move 2-cells block to the right
• Decrease counter. If null
• Reset copied cell
• Reset counter to initial value (copy from backup)
• Move whole array at its original position
• Go to next cell

Code - try it

generate comma
>++++[-<+++++++++++>]
generate all numbers from max to 2
>-[[->+>+<<]>[-<+>]+>-]<-<-<

[
  go to current number
  -<
  [
    number is not null: prime
    copy twice and print
    [->>+>>+<<<<]
    >>>>[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]
    print comma
    <<<<[<<]<.>>>[>>]
    copy counter
    >[->+>>+<<<]>[-<+>]<

    for each cell
    <<<[
      move
      -<[->>+<<]>>>+
      go to counter and decrease then check if null
      [>>]+<-[>-]>[-
        reset last copied cell
        <<[<<]>[-]>[>>]
        reset counter
        >>[-<+<<+>>>]<[->+<]
      ]
      process next cell
      <<<[<<]<<
    ]
    move back all cells
    >>>>[<[-<<+>>]<+>>->>]
    clear counters
    <[-]>>>[-]<<<<<
  ]
  process next number
  <
]

Final state

• Memory: 44 0 0 0 (44 is code for comma)
• Cursor: second cell
• Input: unchanged
• Output: all primes below 255, comma separated, with extra comma - note that extra comma can be removed by adding a Backspace character (code = 10). Simply add ++++++++++. at the end of the code.

Read comma-separated numbers

Context

Let's have an input like '12,34,56,78,9,100'. The goal is to have an array of numbers [12], [34], ... in memory, reading comma-separated decimal numbers. To achieve it, we'll have to

• Read a char
• If it's a comma (ASCII code 44), then start a new number
• Otherwise it's a digit, add it to ten times the current number

Note: this post is strongly related to array definition and read decimal number ones

Initial state

• Memory: 0, 0, 0, 0...
• Cursor: first cell
• Input: comma-separated decimal numbers (A,B,C,...)

Process

• Leave one cell to delimit array, plus one cell for current first integer read
• While a character is read
• Remove 44 (',' ASCII code)
• Set else bit
• If result is not null
• It's a digit. Remove 4 to get the decimal digit value
• Update current integer
• Otherwise
• Start a new integer 

Code 

>>
array delimiter and first integer (currently 0)
,[
  >++++[-<----------->]+<
  remove 44 (comma ASCII code) and set bit else
  [>-<
    if read value is not 44 => it is a digit
    ----
    remove 4 again (to remove 48 which is 0's ASCII code)
    >+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]
    multiply current integer by ten and add new digit
  ]
  >[-
    else
    >
    move to next integer
  ]<
,]

Code (minified)

>>,[>++++[-<----------->]+<[>-<---->+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]]>[->]<,]

Final state

• Memory: 0,A,B,C,...,0
• Cursor: on final 0 (end of array)
• Input: empty
• Output: unchanged

Example

Live 'Comma-separated decimal to ASCII' converter: type comma-separated ASCII code to display the corresponding string (e.g. input 50,48,49,55 produces 2017)

Print code as decimal number

Context

Memory cells contain values, that can be easily displayed (using .).
However, this displays the value as an ASCII character. In order to display the integer value (in base 10), we need to

• Do successive euclidean divisions on the value and its successive quotients, to get digits (successive reminders)
• As remainder can be 0, store remainder + 1
• Add 47 to each digit (ASCII code for 0, stored as 1 according to line above) and display the char

Initial state

• Memory: 0, A, 0, ...
• Cursor: second cell
• Input: any

Process

• While current cell is not null
• Divide by ten (see Euclidean division article)
• Move remainder+1 to current cell, quotient to next cell
• Move cursor to quotient
• Memory state: 0, a, b, c, d, ..., 0, with a, b, c, d, ... digits of A, in reverse order
• Move to left (first digit of A)
• While current cell is not null
• Add 48 (6*8 is faster)
• Remove 1 and print char
• Clear
• Move right

Code

[
  >>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]
  (divide by ten)

  >+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<
  (move results to the right place)
]
<[>++++++[<++++++++>-]<-.[-]<]
(display result)

Code (minified)

[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]

Final state

• Memory: 0
• Cursor: first cell
• Input: any
• Output: A, written in base 10