Examine individual changes

'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". If a cell is used for both input and output, it will be denoted as: {cell name} when it contains the input and {cell name}' (prime) when it contains the output. 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. ==Comment loop== Loops can be used as block [[comment|comments]] when the cell value is known to be zero. This is useful, because it allows using brainfuck instructions freely, such as <code>,</code> and <code>.</code>, which are commonly used for punctuation. The only restriction is that any <code>[</code> and <code>]</code> characters must be matched, as they are parsed as loops. A loop at the start of the program is a header comment: ['''''comment''''']''code'' To make no assumption about the initial cell value, clear it first: ''code''[-]['''''comment''''']''code'' Since loops only terminate when / if the current cell is zeroed, comments can safely be placed directly behind any other loop. For example: ''code'',[.,]['''''comment''''']''code'' 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). ---- ==Read all characters into memory== ,[>,] ==Read until newline/other char== ----------[++++++++++>,----------]++++++++++ Adjust the number of +/- to the char code you want to match. Omit the final + block to drop the char. Requires wrapping. ==Read until any of multiple chars== +>[ >, (-n1)[(+n1)[>+<-]]>[<+>-]< (-n2)[(+n2)[>+<-]]>[<+>-]< etc ] (+/-n1) means repeat that operator n1 times. n1, n2 etc are the char codes you want to match. One line for each. ==x = 0== ===Wrapping=== x[-] ===Non-wrapping=== Attribution: [[User:quintopia|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. ---- Attribution: [[User:JHM|JungHwan Min]] x >[-] >[-] << [ >+[-<+>>+<] <[>]> [ +[-<+<->>] <[->+<] ] >[-<+>] << ] >[-]< Uses x and two cells to the right of it. Originally posted at [https://codegolf.stackexchange.com/a/118441/60043 Code Golf Stack Exchange]. ---- ==x = y== temp0[-] x[-] y[x+temp0+y-] temp0[y+temp0-] ---- ==x´ = x + y== ===Wrapping=== temp0[-] y[x+temp0+y-] temp0[y+temp0-] ---- y[-x+y]x ==x´ = x - y== ===Wrapping=== temp0[-] y[x-temp0+y-] temp0[y+temp0-] ---- ==x´ = x * y== temp0[-] temp1[-] x[temp1+x-] temp1[ y[x+temp0+y-]temp0[y+temp0-] temp1-] ---- ==x´ = x * x== Attribution: [[User:Softengy|Softengy]] ([[User talk:Softengy|talk]]) 15:44, 7 April 2020 (UTC) Uses the fact that '''x * x = <math>\sum_{i=0}^{x-1} 2*i+1</math>''' x[temp0+x-] temp0[-[temp1+x++temp0-]x+temp1[temp0+temp1-]temp0] ---- ==x´ = x / y== Attribution: [[User:calamari|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] === Wrapping === Attribution: [[User:Softengy|Softengy]] ([[User talk:Softengy|talk]]) 17:06, 7 April 2020 (UTC) This algorithm will compute x / y, put the remainder into x and put the quotient into q x[ temp1+[ y[x-[temp1+†]temp1-temp0+y-] temp0[y+temp0-]q+temp1 ] ] x[y[temp0+x+y-]temp0[y+temp0-]q-†] † Move to any location with a value of 0 ---- ==x´ = x^y== Attribution: [[User:chad3814|chad3814]] temp0[-] x[temp0+x-] x+ y[ temp1[-] temp2[-] x[temp2+x-] temp2[ temp0[x+temp1+temp0-] temp1[temp0+temp1-] temp2-] y-] ---- ==swap x, y== temp0[-] x[temp0+x-] y[x+y-] temp0[y+temp0-] ===Wrapping=== Another algorithm: x[-temp0+y-x] y[-x+y] temp0[-y+x+temp0] ==x = -x== ===Wrapping=== temp0[-] x[temp0-x-] temp0[x-temp0+] ===Non-Wrapping=== Requires another variable signx, where 0 = positive, 1 = negative. temp0[-]+ signx[temp0-signx-] temp0[signx+temp0-] ---- ==x´ = not x (bitwise)== ===Wrapping=== temp0[-] x- [temp0-x-] temp0[x+temp0-] Another version: x-[[-]+y](y-1) Note that y is just for pointer-placing. Remember to let x be the #x th(x>=1) and y to be greater than x. ===Non-Wrapping=== 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== ===To the right=== [>] ===To the left=== [<] ---- ==Find a non-zeroed cell== Attribution: [[User:Epsilon|Epsilon]] ===To the right=== +[>[<-]<[->+<]>]> ===To the left=== +[<[>-]>[-<+>]<]< '''Note: It is assumed that the cell the pointer starts on is zeroed. Problems may occur if it is not.''' ---- ==Move pointer x (empty) cells== Attribution: [[User:Kman|Kman]] Move your pointer to the right/left as many times as the value of x. (Non-Wrapping) ===To the Right=== (pointer on cell x) >++[-[+>]+[<]>-]>[[-]>] ===To the Left=== (pointer on cell x) <++[-[+<]+[>]<-]<[[-]<] '''Note:''' *All cells between x and x±x are zeroed unless you remove the [-] from the [[-]>]-s. If you do, they will all be incremented. *If there are n nonzero cells between x and x±(x+n) (watch out, recursive), you will 'skip' the nonzero cells. *Ensure there are zeroed cells before/after (moving right/left) cell x, or the one next to cell x will become the new "cell x". *If you are expecting to move as low as 1 cells, remove the >++/<++ from the beginning, and you will move x-1. (As shown, only works with x>1) ---- ==x(y) = z (1-d array) (2 cells/array element)== Attribution: [[User:calamari|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)== Attribution: [[User:calamari|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)== Attribution: [[User:Tritonio|Tritonio]] 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 [https://www.inshame.com/2008/02/efficient-brainfuck-tables.html this article]. ---- ==x = y(z) (1-d array) (1 cell/array element)== Attribution: [[User:Tritonio|Tritonio]] 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== ===Wrapping=== Attribution: [[User:calamari|Jeffry Johnston]] The algorithm returns either 0 (false) or 1 (true) and preserves y. temp0[-] temp1[-] x[temp1+x-]+ y[temp1-temp0+y-] temp0[y+temp0-] temp1[x-temp1[-]] ---- 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[-]] It is similar to [[Brainfuck_algorithms#z_.3D_x_xnor_y_.28boolean.2C_logcial.29|z = x xnor y]]. ---- ==x´ = x != y== Attribution: [[User:calamari|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[-]] It is similar to [[Brainfuck_algorithms#z_.3D_x_xor_y_.28boolean.2C_logcial.29|z = x xor y]]. ---- Attribution: [[User:YuvalM|Yuval Meshorer]] Sets x to be 1 if x == y, 0 otherwise. x[ y-x-] y[[-] x+y] ---- ==x´ = x < y== 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== 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== Attribution: [[User:ais523|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 y-x. (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)== Attribution: [[User:quintopia|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. z and the four cells to its right 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+>> [->-[>]<<] <[ (y>=x) - >>[ (y>x) <<+>>[+] ]< ] >>[ (x>y) [+] ] <<< (put an {if 0, then do} algorithm here to run code conditional on y=x) †The polarity of these lines should be reversed if x and y are negative. ---- ==x´ = not x (boolean, logical)== Attribution: [[User:calamari|Jeffry Johnston]] The algorithm returns either 0 (false) or 1 (true). temp0[-] x[temp0+x[-]]+ temp0[x-temp0-] ---- Attribution: [[User:Sunjay|Sunjay Varma]] Another version for when you can consume x (mutate its value). Also assumes that x is either 0 or 1. If you do not want to consume x, you can still use this algorithm. Just copy x to another cell, then apply the operation. The algorithm returns either 0 (false) or 1 (true). temp0[-]+ x[-temp0-x]temp0[x+temp0-] ---- Modification of Sunjay's version above. temp0[-]+ x[[-]temp0-x]temp0[-x+temp0] Then there's undoubtedly no mistake. When x>1, the result will be as same as x=1 . ---- Attribution: [[User:YuvalM|Yuval Meshorer]] Even another version that consumes x. Returns 0 (false) if x is 1 (true) and 1 if x is 0. temp0[-] x[temp0-x-]temp0+ ---- Attribution: [[User:A]] It is based on x=x==y, where I set y into 0. y+x[-y-x]+y[x-y[-]]x ---- Attribution: [[User:tommyaweosme|tommyaweosme]] Uses 1 cell to right ->+<[>+<[-]]>[<+>-]<- ---- Attribution: [[User:Waso|Waso]] A more efficient algorithm that also uses one cell to the right: -[>+<+]>[-<+>]< ---- ==y = not x (boolean, logical)== Attribution: [[User:FSHelix|FSHelix]] A harder-to-understand version, which preserves x but needs 3 continuous cells in total.<br /> Maybe using it for calculating "y = not x" is not necessary, but I think this idea will be quite useful in some cases.<br /> In fact the idea is also embodied in other codes in this page.<br /> #Define these 3 cells as x, y=1 and t=0.<br /> x>y[-]+>t[-]<<x [>y[-]]>[>t] According to whether x==0 or not, there are two different run modes because the position of the pointer changes in the "[]" loop.<br /> The following is the process of the second line, "*" means the pointer is here.<br /> If x==0: If x!=0: x y t x y t *0 1 0 *1 1 0 [>y[-]] *0 1 0 [>y[-]] 1 *0 0 [>y[-]]> 0 *1 0 [>y[-]]> 1 0 *0 [>y[-]]>[>t] 0 1 *0 [>y[-]]>[>t] 1 0 *0 ---- ==x´ = x and y (boolean, logical)== Attribution: [[User:calamari|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[-]] ] ---- ==z = x and y (boolean, logical) (wrapping)== Attribution: [[User:Sunjay|Sunjay Varma]] Consumes x and y (leaves them as zero at the end of the algorithm) and stores the result in z. For short-circuit evaluation, don't evaluate x or y until just before they are used. The algorithm returns either 0 (false) or 1 (true). z[-] x[ y[z+y-] x- ] y[-] ---- Attribution: [[User:YuvalM|Yuval Meshorer]] Consumes x and y and outputs 1 in z if both x and y are 1, else 0. z[-] x[ -y[-z+y] x] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="3" | OUTPUT |- ! x !! y !! !! x !! y !! z |- | 0 || 0 || || 0 || 0 || 0 |- | 0 || 1 || || 0 || 0 || 0 |- | 1 || 0 || || 0 || 0 || 0 |- | 1 || 1 || || 0 || 0 || 1 |} ---- ==z = x nand y (boolean, logical)== Attribution: [[User:FSHelix|FSHelix]] Consumes x and y and outputs 0 in z if both x and y are 1, else 1. z[-]+ x[ y[z-y-] x- ] y[-] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="3" | OUTPUT |- ! x !! y !! !! x !! y !! z |- | 0 || 0 || || 0 || 0 || 1 |- | 0 || 1 || || 0 || 0 || 1 |- | 1 || 0 || || 0 || 0 || 1 |- | 1 || 1 || || 0 || 0 || 0 |} ---- ==x´ = x or y (boolean, logical)== ===Wrapping=== Attribution: [[User:calamari|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[-]] ---- Attribution: [[User:YuvalM|Yuval Meshorer]] Returns 1 (x = 1) if either x or y are 1 (0 otherwise)<br /> If you use it in the case that x>1 or y>1,please make sure it won't cause overflow problem.<br /> For example,if x=1 and y=255, than x will be 0. x[ y+x-] y[ x+y[-] ] ---- ==z = x or y (boolean, logical)== Attribution: [[User:Sunjay|Sunjay Varma]] Consumes x and y (leaves them as zero at the end of the algorithm) and stores the result in z. For short-circuit evaluation, don't evaluate x or y until just before they are used. If you don't care about short-circuit evaluation, temp0 can be removed completely. If temp0 is removed and both x and y are 1, z will be 2, not 1. This is usually not a problem since it is still non-zero, but you should keep that in mind.<br /> Or there's a way to fix it, add these codes to the end: z[x+z[-]] x[z+x-] The algorithm returns either 0 (false) or 1 (true). z[-] temp0[-]+ x[ z+ temp0- x- ] temp0[- y[ z+ y- ] ] y[-] ---- Attribution: [[User:YuvalM|Yuval Meshorer]] Consumes x and y, does not use a temporary cell. Makes z 1 (true) or 0 (false) if either x or y are one. z[-] x[y+x-] y[[-] z+y] ---- Required structure: 0 0 x y ^ With the cursor pointing at x, the value of the logical operation x or y will be stored in the left most cell. The values of x and y will be preserved [<<->]<+[<]+>[-<->>+>[<-<<+>>]<[-<]]> Shorter version: [<<+>]>[<<[>]<[-]+>]<[>>] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="4" | OUTPUT |- ! x !! y !! !! x !! y !! z !! temp0 |- | 0 || 0 || || 0 || 0 || 0 || style="text-align: center;" | 0 |- | 0 || 1 || || 0 || 0 || 1 || style="text-align: center;" | 0 |- | 1 || 0 || || 0 || 0 || 1 || style="text-align: center;" | 0 |- | 1 || 1 || || 0 || 0 || 1 || style="text-align: center;" | 0 |} ---- ==x´ = x nor y (boolean, logical)== Attribution: [[User:FSHelix|FSHelix]] Consumes x and y and outputs 0 in x if both x and y are 1, else 1. Used an extra cell "z" to avoid the overflow problem like the one mentioned in [[Brainfuck_algorithms#x_.3D_x_or_y_.28boolean.2C_logical.29|x = x or y]]. x[z+x[-]] y[z+y[-]] z[x+z[-]] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="2" | OUTPUT |- ! x !! y !! !! x !! y |- | 0 || 0 || || 0 || 1 |- | 0 || 1 || || 0 || 0 |- | 1 || 0 || || 0 || 0 |- | 1 || 1 || || 0 || 0 |} ---- ==z = x xor y (boolean, logical)== Attribution: [[User:YuvalM|Yuval Meshorer]] Consumes x and y. Makes z 1 (true) or 0 (false) if x does not equal y. Finishes at y. z[-] x[y- x-] y[z+ y[-]] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="4" | OUTPUT |- ! x !! y !! !! x !! y !! z |- | 0 || 0 || || 0 || 0 || 0 |- | 0 || 1 || || 0 || 0 || 1 |- | 1 || 0 || || 0 || 0 || 1 |- | 1 || 1 || || 0 || 0 || 0 |} ---- ==z = x xnor y (boolean, logical)== Attribution: [[User:FSHelix|FSHelix]] Consumes x and y. Makes z 1 (true) or 0 (false) if x equal y. Finishes at y. z[-]+ x[ y- x- ] y[ z- y[-] ] ---- {| class="wikitable" |- ! colspan="2" | INPUT !! !! colspan="4" | OUTPUT |- ! x !! y !! !! x !! y !! z |- | 0 || 0 || || 0 || 0 || 1 |- | 0 || 1 || || 0 || 0 || 0 |- | 1 || 0 || || 0 || 0 || 0 |- | 1 || 1 || || 0 || 0 || 1 |} ---- ==z = MUX(a, x, y) (boolean, logical)== Attribution: [[User:YuvalM|Yuval Meshorer]] If a is equal to 1, then z is equal to y. Otherwise, if a is equal to 0, z will be equal to x. When done, a, x, and y will all be 0 regardless of their starting values. e.g: IN: x = 0, y = 1, a = 1 OUT: x = 0, y = 0, a = 0, z = 1 z[-] y[ a[z+a-] y-] x[ a-[ [-]z[-]+ a] x-] a[-] ---- {| class="wikitable" |- ! colspan="3" | INPUT !! !! colspan="4" | OUTPUT |- ! a || x !! y !! !! z |- | 0 || 0 || 0 || || 0 |- | 0 || 0 || 1 || || 0 |- | 0 || 1 || 0 || || 1 |- | 0 || 1 || 1 || || 1 |- | 1 || 0 || 0 || || 0 |- | 1 || 0 || 1 || || 1 |- | 1 || 1 || 0 || || 0 |- | 1 || 1 || 1 || || 1 |} ==while (x) { code }== Attribution: [[User:Sunjay|Sunjay Varma]] To implement a while loop, you need to evaluate the condition x both before the loop and at the end of the loop body. '''''evaluate x''''' x[ '''''code''''' '''''evaluate x again''''' x ] ---- Attribution: [[User:Morganbarrett|Morgan Barrett]] If the predicate is sufficiently complicated, you can get away with only evaluating it once like so: temp0[-]+[ temp0- '''''evaluate x'''''[ '''''code''''' temp0+ † ] temp0 ] † Move to any location with a value of 0 ---- ===break and continue=== Attribution: [[User:Sunjay|Sunjay Varma]] To implement break and continue statements in loops, consider that the following two pieces of pseudocode are functionally equivalent: while (foo) { if (bar == foo) { if (x > 2) { break; } else { // do stuff } // do stuff } // update foo for the next iteration } // Equivalent without break statement: while (foo) { shouldBreak = false if (bar == foo) { if (x > 2) { shouldBreak = true } else { // do stuff } // don't evaluate any more code in the loop after breaking if (!shouldBreak) { // do stuff } } if (shouldBreak) { // so that the loop stops foo = 0 } else { // update foo for the next iteration } } Notice that we need to guard '''all''' code ''after'' the break statement in the loop to prevent it from running. We don't need to guard in the else statement immediately after the break statement because that will never run after the break statement has run. This approach allows us to implement break and continue statements in brainfuck despite the lack of sophisticated jump instructions. All we're doing is combining the concept of an if statement (defined below) with the while loop we just defined and applying it here. Implementing a continue statement is the same thing except you never guard the loop updating code: while (foo) { if (bar == foo) { if (x > 2) { continue; } else { // do stuff } // do stuff } // update foo for the next iteration } // Equivalent without continue statement: while (foo) { shouldContinue = false if (bar == foo) { if (x > 2) { shouldContinue = true } else { // do stuff } // don't evaluate any more code in the loop after continuing if (!shouldContinue) { // do stuff } } // This code stays the same after a continue because we still want to move on to the next iteration of the loop // update foo for the next iteration } To implement both break and continue, you can compose the concepts here and make any combination you want. You can consider break and continue statements to be "sugar" that needs to be "desugared" in your brainfuck code. ==do { code } while (x)== Attribution: [[User:None1|None1]] temp[-]+[ '''''code''''' '''''evaluate x''''' x ]temp- The program needs one temporary byte and clears it and the pointer stops at <code>x</code>, <code>x</code> is evaluated once per loop ==if (x) { code }== temp0[-] temp1[-] x[temp0+temp1+x-]temp0[x+temp0-] temp1[ '''''code''''' temp1[-]] or alternatively: temp0[-] x[ '''''code''''' temp0 ]x or alternatively if you don't need x anymore: x[ '''''code''''' x[-] ] ---- ==if (x == 0) { code }== The code examples in the following section work for this: [[Brainfuck_algorithms#if_.28x.29_.7B_code1_.7D_else_.7B_code2_.7D|if (x) { code1 } else { code2 }]]. Just have "code1" be empty. ==if (x) { code1 } else { code2 }== Attribution: [[User:calamari|Jeffry Johnston]] (39 OPs) temp0[-] temp1[-] x[temp0+temp1+x-]temp0[x+temp0-]+ temp1[ '''''code1''''' temp0- temp1[-]] temp0[ '''''code2''''' temp0-] ---- Attribution: Daniel Marschall (33 OPs) temp0[-]+ temp1[-] x[ '''''code1''''' temp0- x[temp1+x-] ] temp1[x+temp1-] temp0[ '''''code2''''' temp0-] ---- Attribution: Ben-Arba (25 OPs) 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. temp0[-]+ temp1[-] x[ '''''code1''''' x>-]> [< '''''code2''''' x>->]<< ---- ==switch (x) {case 1: code1, case 2: code 2}== flag[-]+ x [ case 1 ------ [ case 2 ----- [default case] flag [case 1: [-] empty the flag '''''code1''''' ] x ] flag [case 2: [-] empty the flag '''''code2''''' ] x ] The way it works is: subtract the case values from the given <code>x</code> and check the <code>flag</code>. If the <code>flag</code> is still there, then run the case code. If it's empty (at least one case code ran), then do nothing. Clears both <code>x</code> and <code>flag</code> == x = pseudo-random number== Attribution: [[User:calamari|Jeffry Johnston]] This algorithm employs a [[Wikipedia:Linear congruential generator|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-] ---- Attribution: [[User:Cinnamony|Cinnamony]] ,[>++<-]>++++<,>[<+>-] This simple script takes 2 inputs, and the cell next to x, and generates something pseudorandom based off it. It: * Asks for input * Multiplies by 2 and stores in cell x+1 * Adds 4 to cell x+1 * Goes back to cell x and asks for input * Adds cell x and cell x+1. If you inputted the ASCII codes for 87 and 96, you would get 274, wrapping to 19. == Divmod == [[File:3_Number_of_operations_in_divmod.jpeg|200px|thumb|right]] [[File:4_Number_of_operations_in_divmod.jpeg|200px|thumb|right]] 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 This algorithm doesn't work when the divisor is 0 or 1. The pictures show its efficiency intuitively. ---- Attribution: [[User:FSHelix|FSHelix]] Modification of the version above. # >n d [->[->+>>]>[<<+>>[-<+>]>+>>]<<<<<] >[>>>]>[[-<+>]>+>>]<<<<< # >0 d-n%d n%d n/d It works when divisor >= 1, but doesn't preserve n. I've tested it for times with n = 0 ~ 255 and d = 1 ~ 255, including extreme data. ---- [[File:1_Number_of_operations_in_divmod.jpeg|200px|thumb|right]] [[File:2_Number_of_operations_in_divmod.jpeg|200px|thumb|right]] Attribution: [[User:FSHelix|FSHelix]] Another version of divmod, does not preserve n. It uses 7 cells and more time to calculate, and contains 2 layers of If-Else Structure(may be optimized in future). However, it can deal with n, d = 0 ~ 255. Note that when d = 0, it returns n/d = 0 and n%d = n. All inputs have been tested out. # >n 1 d 1 0 0 0 >+>>+<<< [ [ ->->>>>>+<<<<-[>-]>[ >>+>[-<<<<+>>>>]<< ]<[-]+<< ]>>>[>]<<<[-]+< ] # >0 1 d-n%d 1 0 n/d n%d The pictures show its efficiency intuitively. It's obvious that versions above are faster than this. The second version's maximum number of operations is 2.30 times this. ===Fixed Version=== # >n d 1 0 0 0 [->-[>+>>]>[[-<+>]+>+>>]<<<<<] # >0 d-n%d n%d+1 n/d 0 0 Works for all cell values. With division by zero treated as division by MaxCell+1. == Modulo == If we do not need to compute the quotient as well, the following approach is shorter than the divmod algorithm. # 0 >n 0 d 0 0 0 [>+>->+<[>]>[<+>-]<<[<]>-] # 0 >0 n d-n%d n%d 0 0 As an additional advantage, this algorithm works even if the divisor is 1. If n doesn't have to be preserved, the following variant can be used instead. # 0 >n d 0 0 0 [>->+<[>]>[<+>-]<<[<]>-] # 0 >0 d-n%d n%d 0 0 == Print value of cell x as number (8-bit) == Attribution: itchyny, [https://stackoverflow.com/questions/12569444/printing-a-number-in-brainfuck/13946554#13946554 on Stack Overflow] x >>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[- <+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++ <]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]< ---- <pre> x >>++++++++++<< // set n to 10: 0' {x} 0 n '2 [->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<] // divmod; resulting in: 0' 0 n {0} n%d n/d '4 >>[-] 0 10 0 e0 e1&2 >>>++++++++++< // set n to 10 [->-[>+>>]>[+[-<+>]>+>>]<<<<<] // divmod; resulting in: 3' e0 _ {0} e1 e2 '7 >[-] >> // all digits seperated: 0' x _ e0 _ _ e1 {e2} '7 [ // if e2 then: >++++++[-<++++++++>] add 48 (ascii 0) <. print e2 <<+ add one to _ {_} e1 (to flag that e2 was not zero) >+ add one to e1 >[-] clear e2 ] < [ // if e1 || e2 then: (one was added to e1 when e2 was processed) <[->-<] if flag was set; remove one from e1 ++++++[->++++++++<] add 48 (ascii 0) >. print e1 [-] clear e1 ] << ++++++[-<++++++++>] // add 48 (ascii 0) <. // print e0 (always printed) [-] // clear e0 <<[-<+>] // move x from '1 to '0 < // {x} (8 cells used) </pre> ==Summing 1~n== Attribution: [[User:YuvalM|Yuval Meshorer]] Copies n-1 to the cell to the right of n and n-2 to the cell to the right of that and so on until 0. Then, sums from 1 to n. Uses n+3 temp cells to the right of n [>+<-]> [[>+>+<<-]>>[-<<+>>]<-]<[[>[<+>-]]<<] >[<+>-] ---- Attribution: [[User:A]] Puts the sum from 1 to y (inclusive) into z. x must be 1. x[-]+y[x[-z+temp0+x]temp0[-x+temp0]x+y-] == Print value of cell x as number for ANY sized cell (eg 8bit, 100000bit etc) == Improved version using updated division routine. All used cells are cleared before and after use. This code is a little faster than before and has been tested with very large values; but as the number of BF instructions is proportional to the number being printed anything over a couple of billion needs an interpreter that can recognise the <code>[->-[>+>>]>[[-<+>]+>+>>]<<<<<]</code> fragment as a divmod (taking care to ensure that the prerequisites are met). // Print value // Cells used: V Z n d 1 0 0 0 // V is the value you need to print; it is not modified // Z is a zero sentinal and tmp // All cells Z and up are cleared by this routine >[-]>[-]+>[-]+< // Set n and d to one to start loop [ // Loop on 'n' >[-<- // On the first loop <<[->+>+<<] // Copy V into N (and Z) >[-<+>]>> // Restore V from Z ] ++++++++++>[-]+>[-]>[-]>[-]<<<<< // Init for the division by 10 [->-[>+>>]>[[-<+>]+>+>>]<<<<<] // full division >>-[-<<+>>] // store remainder into n <[-]++++++++[-<++++++>] // make it an ASCII digit; clear d >>[-<<+>>] // move quotient into d << // shuffle; new n is where d was and // old n is a digit ] // end loop when n is zero <[.[-]<] // Move to were Z should be and // output the digits till we find Z < // Back to V This alternative runs about a quarter as many BF instructions and is shorter. However, a normally optimising interpreter runs it at about the same speed. It requires about three times as many already cleaned cells two of which are to the left of the cell to be printed. All cells, including the value printed, are cleared after use. >> x >+ [[-]< [->+< [->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+< [->[-]>>+>+<<<] ]]]]]]]]< ]>>[>]++++++[-<++++++++>]>> ]<<<[.[-]<<<] ==Input a decimal number== Attribution: Urban Müller (1993) Value is input into the current cell, uses three more cells to the right. End of the number is a newline, or eof. All other character are treated the same as digits. Works correctly with bignum cells. [-]>[-]+ // Clear sum [[-] // Begin loop on first temp >[-], // Clear the inp buffer to detect leave on eof and input [ +[ // Check for minus one on eof -----------[ // Check for newline >[-]++++++[<------>-] // Subtract 38 to get the char in zero to nine <--<<[->>++++++++++<<] // Multiply the existing value by ten >>[-<<+>>] // and add in the new char <+>] ] ] <] < // Current cell is the number input ---- Attribution: [[User:tommyaweosme|tommyaweosme]] ,>++++++++[<------>-]< Subtracts 48 from input, turning the input into a single digit. ---- Attribution: [[User:tommyaweosme|tommyaweosme]] ,>++++++++[<------>-],>++++++++[<------>-],>++++++++[<------>-]<<[>>++++++++++<<-]<[>>>>++++++++++<<<<-]>>>>[>++++++++++<-]>[<<+>>-]<<<[>+<-]>[<<<+>>>-] Turns the input into 3-digit number. ==Count up with step x, from y to infinity== x[[-y+temp+x]temp[-y+x+temp]x] ==while(c=getchar()!=X)== Uses X to represent the getchar-until char. Needs overflow and underflow in TIO. Preserves result(equal 0, unequal 1)in t1. Preserves x and y. <pre> yXx+[,[-t1+t3+x]y[-t2+t4+y]t1[-x+t1]t2[-y+t2]t3[-t4+t3]t4[++t3]t4[-t1+t4]t1] </pre> == See also == * [[Brainfuck]] * [[Brainfuck constants]] * [[Brainfuck bitwidth conversions]] * [[BrainClub]] (contains algorithms usable for stack-based programming, you might understand them if you understand Forth) * [[FBP]], an implementation in c++ that uses these algorithms * [[BFFuck]], a high-level language that compiles to [[brainfuck]] that uses these algorithms (its compiler is in Python) * [https://github.com/bf-enterprise-solutions/str.bf Brainfuck Enterprise Solutions' str.bf] as a collection of string manipulation algorithms. [[Category:Programming techniques]] [[Category:Examples]] [[Category:Brainfuck]]'