Brainfuck algorithms

From Esolang
Jump to: navigation, search

This article presents a number of algorithms for use with the Brainfuck language.

In the interest of generality, the algorithms will use variable names in place of the < and > instructions. Temporary cells are denoted "temp". When using an algorithm in a program, replace the variable names with the correct number of < or > instructions to position the pointer at the desired memory cell.

Example:

If "a" is designated to be cell 1, "b" is cell 4, and the pointer is currently at cell 0, then:

a[b+a-]

becomes:

>[>>>+<<<-]

If a particular algorithm requires cell value wrapping, this will be noted, along with a non-wrapping version, if known. Certain assumptions, such as that a temporary memory cell is already zero, or that a variable used for computation can be left zeroed, are not made. Some optimizations can therefore be performed when exact conditions are known.

Header comment[edit]

The usefulness of this type of comment is that instructions commonly used for punctuation (such as "," and ".") may be used freely. The use of "[" and "]" inside a comment should be avoided, unless they are matched. This commenting style does not work well for internal code comments, unless strategically placed where the cell value is known to be zero (or can be modified to be zero and restored):

[comment]

To make no assumption about the initial cell value, use:

[-][comment]

Since loops only terminate when / if the current cell is zeroed, comments can safely be placed directly behind any other loop.

,[.,][comment]

EsoAPI 1.0 installation check[edit]

Attribution: Jeffry Johnston

+>.++++++++.[++++++[>++>+++++>++++++++>+++++++>+<<<<<-]>>-.>+++.----.<
----.+++++++++++++++.-------.<++++.>>+++.>+++.<-.++++.>++++.<---.>----
.-.>-.---.>>]<[ EsoAPI compatible program -]

Read all characters into memory[edit]

,[>,]

x = 0[edit]

Wrapping[edit]

x[-]

Non-wrapping[edit]

Attribution: User:quintopia

This will clear a cell no matter its sign in an unbounded signed implementation. Also clobbers the cell to the left of x and the cell to the right of temp.

temp[-]†
>[-]†
x<[-]>[†
  temp>-[x+temp+>+]
  x[temp>]
  <[+[x-temp>-<-]x<]
  >
]
temp[-]
>[+]

† Each of these lines should have their polarities reversed if temp, the cell to the right of temp, and the cell to the left of x, respectively, contain a negative value.

Note that rather than just clearing the two cells at temp, one could condition upon the sign that x had.


x = y[edit]

temp0[-]
x[-]
y[x+temp0+y-]
temp0[y+temp0-]

x = x + y[edit]

Wrapping[edit]

temp0[-]
y[x+temp0+y-]
temp0[y+temp0-]

x = x - y[edit]

Wrapping[edit]

temp0[-]
y[x-temp0+y-]
temp0[y+temp0-]

x = x * y[edit]

temp0[-]
temp1[-]
x[temp1+x-]
temp1[
 y[x+temp0+y-]temp0[y+temp0-]
temp1-]

x = x / y[edit]

Attribution: Jeffry Johnston

temp0[-]
temp1[-]
temp2[-]
temp3[-]
x[temp0+x-]
temp0[
 y[temp1+temp2+y-]
 temp2[y+temp2-]
 temp1[
  temp2+
  temp0-[temp2[-]temp3+temp0-]
  temp3[temp0+temp3-]
  temp2[
   temp1-
   [x-temp1[-]]+
  temp2-]
 temp1-]
 x+
temp0]

swap x, y[edit]

temp0[-]
x[temp0+x-]
y[x+y-]
temp0[y+temp0-]

x = -x[edit]

Wrapping[edit]

temp0[-]
x[temp0-x-]
temp0[x-temp0+]

Non-Wrapping[edit]

Requires another variable signx, where 0 = positive, 1 = negative.

temp0[-]+
signx[temp0-signx-]
temp0[signx+temp0-]

x = not x (bitwise)[edit]

Wrapping[edit]

temp0[-]
x-
[temp0-x-]
temp0[x+temp0-]

Non-Wrapping[edit]

Produces an answer for 8-bit cells. For other sized cells, set temp1 to 2^(bits)-1.

temp0[-]
temp1[-]+++++++++++++++[temp0+++++++++++++++++temp1-]
x[temp0-x-]
temp0[x+temp0-]  

Find a zeroed cell[edit]

To the right[edit]

[>] 

To the left[edit]

[<]

x(y) = z (1-d array) (2 cells/array element)[edit]

Attribution: Jeffry Johnston

The cells representing x, temp0, and temp1 must be contiguous, with x being the leftmost cell and temp1 the rightmost, followed by adequate memory for the array. Each array element requires 2 memory cells. The pointer ends at x.

temp0[-]
temp1[-]
temp2[-]
y[temp1+temp2+y-]temp2[y+temp2-]
z[temp0+temp2+z-]temp2[z+temp2-]
x>>[[>>]+[<<]>>-]+
 [>>]<[-]<[<<]
 >[>[>>]<+<[<<]>-]
 >[>>]<<[-<<]

The code up through "-]+" creates a trail of 1's that the later loops will use to find the destination cell. The cells are grouped as "data cell, 1-cell". The destination cell is "data cell, 0-cell", so that the "[>>]" stops in a useful place. The x cell is always 0, and serves as the left-side stop for the "[<<]" statements (notice that t1 is cleared by the first loop, but the loop's trailing "+" converts it to the first 1-cell in the trail). Next, the trail is followed and "[-]" clears the destination cell. The array is now prepared, so an add-to loop of the form "temp0[dest+temp0-]" moves the value in temp0 to the destination cell. Finally, with ">[>>]" the trail of 1's is followed one last time forward, and cleared on the way back, ending at the left stop, x. Contiguous memory required for the array is 3 + 2 * number of array elements.


x = y(z) (1-d array) (2 cells/array element)[edit]

Attribution: Jeffry Johnston

The cells representing y, temp0, and temp1 must be contiguous, with x being the leftmost cell and temp1 the rightmost, followed by adequate memory for the array. Each array element requires 2 memory cells. The pointer ends at y.

x[-] 
temp0[-]
temp1[-]
z[temp1+temp0+z-]temp0[z+temp0-]
y>>[[>>]+[<<]>>-]+[>>]<[<[<<]>+< (pointer is at y)
 x+
y>>[>>]<-]<[<<]>[>[>>]<+<[<<]>-]>[>>]<<[-<<]

x(y) = z (1-d array) (1 cell/array element)[edit]

Attribution: Konstantinos Asimakis

The cells representing space, index1, index2 and Data must be contiguous and initially empty (zeroed), with space being the leftmost cell and Data the rightmost, followed by adequate memory for the array. Each array element requires 1 memory cell. The pointer ends at space. index1, index2 and Data are zeroed at the end.

z[-space+data+z]space[-z+space]
y[-space+index1+y]space[-y+space]
y[-space+index2+y]space[-y+space]
>[>>>[-<<<<+>>>>]<[->+<]<[->+<]<[->+<]>-]
>>>[-]<[->+<]<
[[-<+>]<<<[->>>>+<<<<]>>-]<<

For an explanation on how this algorithm works read this article.


x = y(z) (1-d array) (1 cell/array element)[edit]

Attribution: Konstantinos Asimakis

The cells representing space, index1, index2 and Data must be contiguous and initially empty (zeroed), with space being the leftmost cell and Data the rightmost, followed by adequate memory for the array. Each array element requires 1 memory cell. The pointer ends at data. index1, index2 and Data are zeroed at the end.

z[-space+index1+z]space[-z+space]
z[-space+index2+z]space[-z+space]
>[>>>[-<<<<+>>>>]<<[->+<]<[->+<]>-]
>>>[-<+<<+>>>]<<<[->>>+<<<]>
[[-<+>]>[-<+>]<<<<[->>>>+<<<<]>>-]<<
x[-]
data[-x+data]

x = x == y[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-]
temp1[-]
x[temp1+x-]+
y[temp1-temp0+y-]
temp0[y+temp0-]
temp1[x-temp1[-]]

And if you don't need to preserve x or y, the following does the task without requiring any temporary blocks. Returns 0 (false) or 1 (true).

x[-y-x]+y[x-y[-]]

x = x != y[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-]
temp1[-]
x[temp1+x-]
y[temp1-temp0+y-]
temp0[y+temp0-]
temp1[x+temp1[-]]

x = x <= y[edit]

Attribution: Ian Kelly

x and y are unsigned. temp1 is the first of three consecutive temporary cells. The algorithm returns either 0 (false) or 1 (true).

temp0[-]
temp1[-] >[-]+ >[-] <<
y[temp0+ temp1+ y-]
temp0[y+ temp0-]
x[temp0+ x-]+
temp1[>-]> [< x- temp0[-] temp1>->]<+<
temp0[temp1- [>-]> [< x- temp0[-]+ temp1>->]<+< temp0-]

x = x < y[edit]

Attribution: Ian Kelly

x and y are unsigned. temp1 is the first of three consecutive temporary cells. The algorithm returns either 0 (false) or 1 (true).

temp0[-]
temp1[-] >[-]+ >[-] <<
y[temp0+ temp1+ y-]
temp1[y+ temp1-]
x[temp1+ x-]
temp1[>-]> [< x+ temp0[-] temp1>->]<+<
temp0[temp1- [>-]> [< x+ temp0[-]+ temp1>->]<+< temp0-]

z = x ≥ y[edit]

Attribution: User:ais523

This uses balanced loops only, and requires a wrapping implementation (and will be very slow with large numbers of bits, although the number of bits otherwise doesn't matter.) The temporaries and x are left at 0; y is set to x-y. (You could make a temporary copy of x via using another temporary that's incremented during the loop.)

temp0[-]temp1[-]z[-]
x[ temp0+
       y[- temp0[-] temp1+ y]
   temp0[- z+ temp0]
   temp1[- y+ temp1]
   y- x- ]

z = sign(x-y)[edit]

Attribution: User:quintopia

This is a comparison of two numbers for non-wrapping implementations. The signs of the two numbers must be known. Part of it can also be used to find the sign of an unknown number if both it and its opposite are available. The four cells to the right of z must be free and clear (and will be again when the algorithm terminates), an assumption that must be made in a non-wrapping implementation, as the direction to clear these cells could not be known to this algorithm. The code blocks indicated by parenthetical comments could contain code which depends on the result of the comparison; there is no particular reason in practice to wait for the value of z to be set to one of {-1,0,1}.

x[z>>+>-x-]†
y[z>>->+y-]†
z+>>
[->-[>]<<]
<[
  (x>y)
  +
  >>[+]
]
>>[
  (y>x)
  [+]
  <<<->>
]
<<-
(y=x)

†The polarity of these lines should be reversed if x and y are negative.


x = not x (boolean, logical)[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-]
x[temp0+x[-]]+
temp0[x-temp0-]

x = x and y (boolean, logical)[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 1 (true).

temp0[-]
temp1[-]
x[temp1+x-]
temp1[
 temp1[-]
 y[temp1+temp0+y-]
 temp0[y+temp0-]
 temp1[x+temp1[-]]
]

x = x or y (boolean, logical)[edit]

Wrapping[edit]

Attribution: Jeffry Johnston

The algorithm returns either 0 (false) or 255 (true).

temp0[-]
temp1[-]
x[temp1+x-]
temp1[x-temp1[-]]
y[temp1+temp0+y-]temp0[y+temp0-]
temp1[x[-]-temp1[-]]

if (x) { code }[edit]

temp0[-]
temp1[-]
x[temp0+temp1+x-]temp0[x+temp0-]
temp1[
 code
temp1[-]]

or alternatively:

temp0[-]
x[
 code
temp0
]x 


if (x == 0) { code }[edit]

Attribution: Jeffry Johnston (39 OPs)

temp0[-]
temp1[-]
x[temp0+temp1+x-]temp0[x+temp0-]+
temp1[temp0-temp1[-]]
temp0[
 code
temp0-]

Daniel Marschall (33 ops):

temp0[-]+
temp1[-]
x[temp0-x[temp1+x-]]
temp1[x+temp1-]
temp0[
 code
temp0-]

if (x) { code1 } else { code2 }[edit]

Attribution: Jeffry Johnston (39 OPs)

temp0[-]
temp1[-]
x[temp0+temp1+x-]temp0[x+temp0-]+
temp1[
 code1
 temp0-
temp1[-]]
temp0[
 code2
temp0-]

Attribution: Daniel Marschall (32 OPs)

temp0[-]+
temp1[-]
x[
 code1
 temp0-
 x[temp1+x-]
]
temp1[x+temp1-]
temp0[
 code2
temp0]

This is an alternate approach. It's more efficient since it doesn't require copying x, but it does require that temp0 and temp1 follow x consecutively in memory.

Attribution: Ben-Arba (25 OPs)

temp0[-]+
temp1[-]
x[
 code1
 x>-]>
[<
 code2
 x>->]<<

x = pseudo-random number[edit]

Attribution: Jeffry Johnston

This algorithm employs a linear congruential generator of the form:

V = (A * V + B) % M

Where:

A = 31821, B = 13849, M = period = 65536, V = initial seed
 

A and B values were obtained from the book:

Texas Instruments TMS320 DSP DESIGNER'S NOTEBOOK Number 43 Random Number Generation on a TMS320C5x, by Eric Wilbur

Assumes 8-bit cells. After the code is executed, the variable "x" holds a pseudo-random number from 0 to 255 (the high byte of V, above). The variable cells "randomh" and "randoml" are the internal random number seed and should not be altered while random numbers are being generated.

temp0[-]
temp1[-]
temp2[-]
temp3[-]
temp4[-]
temp5[-]
randomh[temp0+randomh-]
randoml[temp1+randoml-]
temp3+++++++[temp2+++++++++++@temp3-]
temp2[
 temp0[randomh+temp3+temp0-]
 temp3[temp0+temp3-]
 temp1[randomh+temp3+temp4+temp1-]
 temp4[temp1+temp4-]
 temp3[
  randoml+[temp4+temp5+randoml-]
  temp5[randoml+temp5-]+
  temp4[temp5-temp4[-]]
  temp5[randomh+temp5-]
 temp3-]
temp2-]
++++++[temp3++++++++temp2-]
temp3-[
 temp1[randomh+temp2+temp1-]
 temp2[temp1+temp2-]
temp3-]
temp0[-]temp1[-]+++++[temp0+++++temp1-]
temp0[
 randoml+[temp1+temp2+randoml-]
 temp2[randoml+temp2-]+
 temp1[temp2-temp1[-]]
 temp2[randomh+temp2-]
temp0-]
++++++[randomh+++++++++temp0-]
randomh[x+temp0+randomh-]
temp0[randomh+temp0-]

Divmod algorithm[edit]

A clever algorithm to compute div and mod at the same time:

# >n 0 d
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
# >0 n d-n%d n%d n/d

If one does not need to preserve n, use this variant:

# >n d
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
# >0 d-n%d n%d n/d

Print value of cell x as number[edit]

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

Solution from Stack Overflow.

See also[edit]