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)

Pascal's triangle

Context

Pascal's triangle is a triangular array of binomial coefficients: cell k of row n indicates how many combinations exist of n things taken k at a time.
Pascal's triangle looks like

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

One can prove that a given cell  is the sum of 2 cells from previous row: the one just above and the one on top left.
Given that, let's see how we can generate the Nth row of Pascal's triangle

Initial state

• Memory: N 0 0 0
• Cursor: on third cell
• Input: any

Process

• First, let's initialize the first row of the triangle
• Set third cell to 1
• Then, while our counter N is not null
• Decrease counter
• Generate next row
• Go to array's last cell
• Move current cell twice on the right (next 2 cells)
• Go to previous cell and loop
• This will generate next row. Actually, move is a "decrease here / increase there" process, so the first moves will transform 
• ... A B C 0 into ... A B 0 C C
• then into ... A 0 B (B+C) C
• then into ... 0 A (A+B) (B+C) C
• Finally, move the whole new row one cell to the left (because of an extra 0 introduced by steps above)
• Go back to counter

Code - try it

initialize first row
>>+<<
[
  decrease counter
  -
  go to last cell
  >>[>]<
  [
    move twice
    [->+>+<<]
    go to previous cell
    <
  ]
  move whole array to the left
  >>[[-<+>]>]
  back to counter
  <<[<]<
]

Final state

• Memory: 0 0 Nth row of Pascal's triangle
• Cursor: first cell
• Input: unchanged
• Output: unchanged 

Note: because of cell size limitation, the row is computed modulo 256.
And because of that and 'one-cell' array implementation, this algorithm will fail as soon as one cell equals 0 modulo 256.

Anyway, this should not occur until counter = 256, meaning that it would overflow the cell limit for counter itself.

Any triangle row generated through this algorithm is therefore valid as long as it can be generated.

Integer square root, round 2

Context

The Newton's method we used to compute integer square root is generally a very efficient algorithm to compute integer square roots.
However, using BrainFuck, the algorithm itself takes time to be processed, a lot of instructions are needed in order to iterate on different approximations.

Another intuitive but generally inefficient way to compute integer square root is to iterate on all integers and compute their squares until we go over our target number.
A bit less naive approach is to compute the difference between 2 squares, and subtract this difference to N while it's positive.
Example: 27

• 1: remove 1, result is 26
• 2: remove 3 (2*2 - 1*1), result is 23
• 3: remove 5 (3*3 - 2*2), result is 18
• 4: remove 7 (4*4 - 3*3), result is 11
• 5: remove 9 (5*5 - 4*4), result is 2
• 6: remove 11 (6*6 - 5*5), result is negative, so integer square root is 5

We'll see that, due to the nature of BrainFuck, this algorithm is actually really more efficient than Newton's method.

Initial state

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

Process

• Store 1 (square difference) on third cell and 1 (actual result) on fourth
• While A is not null
• remove 1
• remove 1 to square difference
• If square difference is null
• Copy actual result's double on third cell
• Increase both actual result and cell square difference by 1
• Decrease result by 1 (because the current result is over our target)

Code - try it

start from 1
>>>+>+<<<<

while N is not null
[
  decrease N
  -
  set else bit
  >>+
  decrease square difference
  >-
  if current square difference is null
  [<-]<[-
    reinit square difference
    copy current integer double
    >>[-<++>>+<]>[-<+>]<
    increase both integer and square difference by 1
    +<+
    <
  <]
  <
]
decrease result by 1 and print
>>>[-]>-
[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]

Final state

• Memory: 0 0 0 D R with R=isqrt(A) and D the remaining part of the square difference 
• Cursor: first cell
• Input: unchanged
• Output: unchanged

This algorithm takes about 15 times less instructions to be executed...

Fibonacci numbers

Context

Fibonacci sequence F is defined by :

• F(1) = F(2) = 1
• F(n+2) = F(n+1) + F(n) for any n > 1

Hence, the sequence is 1, 1, 2, 3, 5, 8, ...

Let's display all Fibonacci numbers up to the Nth one, N given by user, using a comma-separated display

Initial state

• Memory: empty
• Cursor: first cell
• Input: a number N > 1

Process

• First, let's store the comma code, to display it more quickly
• Then, read the number N
• Initialize the sequence with values 1 and 1
• Display "1,1" as the first sequence values
• Decrease counter N by 2 (because first 2 values are already displayed)
• While counter is not null
• Decrease counter
• Copy the second value of the sequence
• Compute the sum of the 2 current sequence values
• Store the second's copy as first, and sum as new second
• Print comma
• Copy / print newly computed sum

Code - try it

store comma
>++++[-<+++++++++++>]

read number
>,[>++++++[-<-------->]>+++++++++[-<<<[->+>+<<]>>[-<<+>>]>]<<[-<+>],]

print first numbers (1)
<<+++++.-----.+++++.-----

initialize sequence
>-->+>+

start loop
<<
[-
  move / copy second
  >>[->+>+<<]
  sum first / second
  <[->>>+<<<]
  move second to first place
  >>[-<<+>>]
  move / copy sum
  >[-<<+>>>+<]
  print comma
  <<<<<.
  print number
  >>>>>>[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]<<<<
]

Final state

• Memory: 44 0 F(N-1) F(N)
• Cursor: second cell
• Input: empty
• Output: all Fibonacci numbers up to F(N), comma-separated

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.

Integer square root using Newton's method

Context

The integer square root is the operation that returns the integer part of a square root. Namely, isqrt(n) is the biggest integer k so that (k+1)^2 > n.
In most programming languages, there is a fast implementation for this operation, using Newton's method.

Considering a function f, so that f(z) = 0 and let's find z: Newton's method states that, starting with a 'good' value x0, we can define x1 = x0 - f(x0)/f'(x0), and use this formula as a recursive definition, to finally converge to z.

Applied to square root, we have a function f(x) = x^2-n, which is null for x = sqrt(n). So, starting with x0=n, and using the recurrence formula x(k+1) = (x(k) + n/(x(k)) / 2, we can converge to n's square root.

And applied to integers, this gives us:

• Start with X = N
• Define Y = (X+N/X) / 2
• N/X is euclidian quotient
• division by 2 can be done using a shift...
• If X > Y then assign value Y to variable X and loop
• Returns X

Example: sqrt(57)

• X = 57, Y = (57 + 57/57) / 2 = 29
• X = 29, Y = (29 + 57/29) / 2 = 15
• X = 15, Y = (15 + 57/15) / 2 = 9
• X = 9, Y = (9 + 57/9 ) / 2 = 7
• X = 7, Y = (7 + 57/7) / 2 = 7
• Result is 7, and actually 7x7 = 49 < 57 < 8*8 = 64

Example (limit case): sqrt(63)

• X = 63, Y = (63 + 63/63) / 2 = 32
• X = 32, Y = (32 + 63/32) / 2 = 16
• X = 16, Y = (16 + 63/16) / 2 = 9
• X = 9, Y = (9 + 63/9) / 2 = 8
• X = 8, Y = (8 + 63/8) / 2 = 7
• X = 7, Y = (7 + 63/7) / 2 = 8
• Result is 7, and we can see here that X = Y is not a valid stop condition. It has to be X ≤ Y !

Initial state

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

Process

• Here is what our memory should looks like when starting a loop
• N [loop indicator] [current value X] 0 0 0 0 0 0 0 0
• Set loop indicator to 1 and current value to N
• Then, while loop indicator is 1
• Reset loop indicator
• Note
• X will be needed
• once to compute Y
• once to be compared to Y
• once to be the final result, if needed
• N will be needed
• once to compute Y
• Hence, copy N once and X twice to get a memory like this
• N 0 X 0 X N 0 0 0 X 0
• Divide N by X. Division also produces R and R'
• R being the remainder
• and R' so that X = R+R'
• N 0 X 0 X 0 R 0 0 R' N/X
• Compute 2Y, by adding X to N/X, so by adding R and R' to N/X
• N 0 X 0 X 0 0 0 0 0 2Y
• Note: Y will be needed
• once to be compared to X
• once to replace X if needed
• Hence, divide 2Y by 2 and store the results at the right places
• N 0 X Y X 0 0 0 Y 0 0
• Compare Y and X
• N 0 X res 0 0 0 0 Y 0 0
• If res = 1
• set loop indicator to 1
• reset X
• copy Y where X stands

Code - try it

initialize memory
[->+>+<<]>[-<+>]+
Memory : N 1 X 0 0 0 0 0 0 0 0
[
  reset loop indicator
  -
  copy X twice
  >[->+>+>>>>>+<<<<<<<]>[-<+>]
  copy N
  <<<[->+>>>>+<<<<<]>[-<+>]
  Memory: N 0 X 0 X N 0 0 0 X 0

  divide N by X
  >>>>[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]
  Memory: N 0 X 0 X 0 R 0 0 R' N/X

  add X to quotient
  >[->>>+<<<]>>>[->+<]
  Memory: N 0 X 0 X 0 0 0 0 0 2Y

  divide 2Y by 2 and store result twice)
  >[-[-<<+<<<<<+>>>>>>]<[>]>]
  Memory: N 0 X Y X 0 0 0 Y 0 0

  compare Y less than X
  <<<<<+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<<
  Memory: N 0 X res 0 0 0 0 Y 0 0

  if true replace X by Y and loop
  [
    set loop indicator
    -<<+
    reset X
    >[-]
    replace by Y
    >>>>>>[-<<<<<<+>>>>>>]<<<<<
  ]
  go back to loop indicator
  <<
]

Final state

• Memory: N 0 R 0 0 0 0 0 R' 0 0 where R = isqrt(N) and R' = R unless N = R^2 + 1 (then, R' = R+1)
• Cursor: second cell
• Input: unchanged
• Output: unchanged

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)

Read decimal number

Context

Given an input '123', reading input will populate cells with values [49], [50] and [51] (ASCII codes of 1, 2 and 3). Here, we want to read 123 as a number, and have one unique value [123].
Therefore, we'll have to:

• Read a char
• Convert it to a digit (-48)
• Multiply the previous result by 10, and add the new digit

Initial state

• Memory: 0, 0, 0, 0
• Cursor: first cell
• Input: a decimal number

Process

• Move to second cell (first is for result)
• While a digit is read
• Convert to decimal digit (-48)
• Multiply first cell by 10 and add current digit
• Loop invariant: first cell = current read number (decimal)
• When all chars are read, first cell equals number to read

Code 

>,[
  >++++++[-<-------->]
  remove 48
  +++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]
  add first cell 9 times to second
  <[-<+>]
  add second cell to first (result: first cell * 10 plus second cell)
  ,
  read next char
]<

Code (minified)

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

Final state

• Memory: number value (decimal)
• Cursor: first cell
• Input: empty
• Output: unchanged

Example

Live 'Decimal to ASCII' converter: type a number (e.g. 122) to see the corresponding ASCII char in output (e.g. 'z')

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

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

Multiply numbers

Context

Multiplication is a mathematical operation that avoids N successive additions.
However, BrainFuck only allows increments and decrements. Even additions are implemented by successive '+1' operations, and multiplication will also be implemented by "successive-succesive +1"
So, to compute A*B we need to sum A, B times. And as sum destroys one of the operands, we need to copy A before (or while) summing. Optionally, we may also move the result to first cell

Initial state

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

Process

• While first cell is not null
• Decrease first cell
• While second cell is not null
• Decrease second cell
• Increase third / fourth cells
• Loop invariant: first cell + third cell = B, third and fourth cells incremented by the same number
• When first cell equals 0, third cell equals B, fourth cell incremented by B
• Move third cell to second
• Loop invariant: fourth cell = (A - first cell)xB, second cell = B, third cell = 0
• When first cell equals 0, second equals B, third equals 0, fourth equals AxB
• Optionally, clear second cell, move fourth cell to first

Code 

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

Final state

• Memory: AxB, 0, 0, 0
• Cursor: first cell
• Input: any
• Output: unchanged

Subtract numbers

Context

Brainfuck only allows increase / decrease values by 1.
So, like sum, to compute a A-B, we need to remove 1 to A, and do it B times

Initial state

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

Process

• Move to B
• While B cell is not null, decrease B and A by 1
• Loop invariant: difference of both cells is A-B
• When second cell equals 0, then first equals A-B
• Move back to A

Code

>[-<->]<

Final state

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

Sum numbers

Context

Brainfuck only allows increase / decrease values by 1.
So, to compute a sum A+B, we need to add 1 to A, and do it B times.

Initial state

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

Process

• Move to B
• While B cell is not null, decrease B and increase A by 1
• Loop invariant: sum of both cells is A+B
• When second cell equals 0, then first equals A+B
• Move back to A

Code

>[-<+>]<

Final state

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