The Brainfuck language, as its name suggests, presents many challenges to users by being opaque and minimalist. Basic operations in any higher-level languages become difficult in Brainfuck because users need to reason about the particulars of tasks that are usually presented as keywords and built-in functions.
Division is one such difficulty. To find a way to recreate the division operator, users might pick up the Divmod algorithm provided at Esolangs , which describes it as "clever." An unassociated explainer forum I ran across called it "magic."
It's certainly clever. But I'd like to remove some of the magic and reduce the fog surrounding this version of division and modulo.
The Divmod Algorithm From Esolangs
Esolangs offers multiple versions of Divmod. I will explain more about this particular iteration.
[-<-[>+>>]>[+[-<+>]>+>>]<<<<<]
This algorithm uses 6 consecutive cells to complete the division of one number from one separate number.
To start, you supply cells C0 with your dividend and C1 with your divisor. Your register would look like this:
| C0: Dividend | C1: Divisor | C2: blank | C3: blank | C4: blank | C5: blank |
|---|---|---|---|---|---|
| 7 | 2 | 0 | 0 | 0 | 0 |
When the operation has finished, the algorithm will have altered cell C1 and provided the result (integer division) in C3 and the remainder (modulo) in C2. It will have used C4 and C5 as placeholders during its operation. Division of 7 / 2 would change your register to this:
| C0: Dividend | C1: Divisor - (Dividend % Divisor) | C2: Remainder | C3: Result | C4: Tmp | C5: Tmp |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 3 | 0 | 0 |
The logic I explain below applies to other versions that users like FSHelix have created.
You can view this same example with indentation and spacing at the bottom of this article: Indented Code With Commentary
This code assumes you start with a blank register where all values have been initialized to 0.
Line 1 increases the counter in C0 to 7. Line 2 increases C1 to 2. Line 3 moves back to C0. Line 4 completes division of C0 / C1 (or 7 / 2).
+++++ ++
> ++
<
[-<-[>+>>]>[+[-<+>]>+>>]<<<<<]
Like many complex operation in Brainfuck, Divmod uses a series of loops to achieve its goal. By bolding the [ and ] characters and the text within them, I'll highlight the loops below and their relevant parts of the whole.
[-<-[>+>>]>[+[-<+>]>+>>]<<<<<]
The outer-most loop runs until the dividend in C0 has been exhausted. It always:
This allows the dividend to decrease with each run and informs other parts of the code about whether or not --- because of the content of C1 --- an even division has been completed.
The single > seen after the first loop is this outer loop's check for an full division. See the next section, First Inner Loop, for further information about that > character.
[-<-[>+>>]>[+[-<+>]>+>>]<<<<<]
The algorithm always reaches this loop with the cursor placed at C1. If the value of C1 is not 0, the loop proceeds:
This inner loop will execute as long as C1 (divisor) hasn't been reduced to 0 by the preceding code in the outer loop. Its function is to temporarily store part of the divisor in C2 (remainder).
This algorithm works its way through the dividend and divisor one unit at a time, so when this loop stores part of C1 (divisor) in C2 (remainder), it's doing that because it needs to keep track of how much of the divisor it has checked to see if it fits completely into C0 (dividend).
As a result, when C1 (divisor) doesn't completely fit, its unused parts are left in C2 (remainder).
As mentioned in the previous section, the close of this inner loop is immediately followed by a > character as part of the outer loop. When this instruction is reached, the cursor moves either to C2 (remainder) if a complete division has occurred or to C5 (tmp) if not.
This inner loop affects which path you will take after encountering the > here. This inner loop always ends at C4 (tmp), which is always 0. Therefore, when the > moves the cursor to C5, which is also always 0, the second inner loop will not run.
[-<-[>+>>]>[+[-<+>]>+>>]<<<<<]
This loop only executes when the cursor has reached C2 (remainder), and that only happens after a full division of divisor into dividend has occurred.
Because this algorithm works through the divisor one unit at a time, the first inner loop always copies C1 (divisor) into C2 (remainder) by those individual units.
As long as there is some dividend and divisor to work through, the algorithm must keep track of the divisor (by copying it to C2). It does this until the divisor is exhausted; then this inner loop resets C1 (divisor).
This loop always:
+ operatorYou can think of C2 (remainder) as a placeholder for all the references to C1 (remainder) that have been made. When the entire Divmod operation has finished, either C2 will contain a non-zero value, which signals that a full division was not completed and therefore this inner loop wasn't run one or more times, or C2 will be 0, which means that the initial C1 (divisor) cleanly fits into the initial C0 (dividend).
I do hope this makes the Divmod algorithm at least a little less hazy. It can be difficult to mentally track all the moving pieces of any Brainfuck code, but by breaking it down into manageable sections, the individual parts aren't too complex on their own.
The "magic" and "clever[ness]" here, I think, comes largely from the use of temporary variables and the understanding of how division can work in units.
This Divmod doesn't take the number 2 as a whole and try to fit it into the number 7 as a whole an X-count of times. Instead, it counts down the dividend and divisor by 1 with each run of the outer loop.
Use of the temporary cells C4 and C5 give the algorithm a place to look when it needs a 0 to skip a loop.
Mandatory, non-conditional operators also help keep the algorithm consistent. I'm particularly impressed with the mandatory + at the beginning of the second inner loop because it allows the algorithm to run through the entire divisor, skip the first inner loop (that would normally copy the divisor into the remainder for future access), and fully replenish that temporary copy so it can be copied back to the original divisor cell for use in another run of the outer loop.
(C0 ; C1 ; C2 ; C3 ; C4 ; C5 )
(DIVIDEND; DIVISOR MINUS (DIVIDEND % DIVISOR); REMAINDER ; RESULT IN INT ARITHMETIC ; TMP; TMP)
+++++ ++ add 7 to c0
> ++ add 2 to c1
< c0
[ if dividend has value remaining
- > - always subtract 1 from dividend and divisor
at c1
[ if divisor has value remaining
after each full division: this loop will skip
> + >> copy C1 divisor to c2 remainder
finish at c4 tmp
] continue if c4 tmp == 0
> c2 remainder if full division has occurred
c5 tmp if not
[ this loop only occurs when a full division is realized
+ and completes the transfer of c1 divisor to c2 remainder
by adding 1 here
in first internal loop: this gave c2 remainder value to make this loop possible
[ from c2 remainder this always runs
- < + > then proceed to subtract from c2 remainder
and add back to c1 divisor until c2 remainder is empty
this is what empties the remainder when full division is realized
and keeps the remainder when a full division hasn't completed
since this loop never runs if c5 tmp == 0
]
> + c3 is increased when a full division is realized
>> c5 will always(?) be 0
]
<<<<< return to c0
] divide again if c0 > 0