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)

Shifts

Context

Right or left bit shifts are operators in algorithmic, with a general syntax >> or <<.
These operators append B bits at the beginning or end of A, and therefore truncate the last or first B bits of A.
Example: 47 << 2 = 188, as 47 is 00101111, and 10111100 = 188 in base 10.
One useful application is the multiplication / division by powers of 2. Actually, X<<Y = X*2^Y, and X>>Y = X/2^Y.
Let's implement operations <<1 and >>1, namely multiplication / division by 2.

Initial state

• Memory: X 0 0
• Cursor: first cell
• Input: any

Process - left shift

• While first cell is not null
• Remove 1 to first cell
• Add 2 to second cell
• Loop invariant: first cell + (second cell) / 2 = X
• When first cell is null: second cell equals 2X

Code - try it

[->++<]

Final state - left shift

• Memory: 0 2X
• Cursor: first cell
• Input: unchanged
• Output: unchanged

Process - right shift

• Division by 2 can be implemented in a different way than regular division:
• While first cell if not null
• Remove 1 to first cell
• If possible, remove 1 again to first cell, increase third cell and stay on second
• Move right (i.e. on second cell if first is now null, third otherwise, and third is not null in this case)
• Move left if current is not null (i.e. fallback on second cell in all case)
• Loop invariant: first cell + 2*third cell = X or X-1
• When first cell is null: third is half X, rounded to floor

Code - try it

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

 Final state - right shift

• Memory: 0 0 X/2
• Cursor: first cell
• Input: unchanged
• Output: unchanged

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

Euclidean division

Context

Euclidean division is an operation on A (dividend) and B (divisor) that returns Q (quotient) and R (remainder), with

• A=B * Q + R
• 0 <= R < B

In BrainFuck, this can be implemented like this

• Decrease dividend
• Increase remainder
• Decrease divisor
• If divisor = 0
• then remainder = initial divisor, rebuild initial divisor from remainder
• reset remainder
• increase quotient

Initial state

• Memory: A, 0, 0, 0, B, 0
• Cursor: first cell
• Input: any

Process

• While first cell is not null
• Decrease first cell (dividend)
• Increase second (remainder)
• Increase fourth (bit else)
• Decrease fifth (divisor)
• While divisor is not null
• move back to bit else, reset and stay on it
• Move to previous cell (bit else if divisor was null, third cell = 0 otherwise)
• If current cell is not null (so, on bit else)
• move second cell to fifth (rebuild divisor)
• Increment sixth cell (quotient)
• reset bit else
• move to third cell
• Loop invariants
• second + fifth cell = initial divisor
• (second + fifth)*sixth + second + first = initial dividend
• When first cell is null, dividend = divisor * sixth + second; so Q is in sixth cell, and R in second

Code 

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

Final state

• Memory: 0, R, 0, 0, B', Q with B' = B-R
• Cursor: first cell
• Input: any
• Output: unchanged

Note: we can add some extra code to:

• Start with memory A, B, 0, 0, 0, 0
• Clean result to have Q, R, 0, 0, 0, 0

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