Dr. John A Zoidberg - 1 year ago 156
Brainfuck Question

# Divmod algorithm in brainfuck

Can somebody please explain this code to me? I understand what it does but I don't understand how it works.

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

Answer Source

Here's what happens:

``````# >n 0 d
``````

This line, is a comment line telling you what the memory should be like before the operation. Dividend as `n`, divisor as `d`. According to the code the next 3 cells should be empty as well, but it is ignored here, assuming you have it empty by default.

For easier understanding, I'll now use 25/4 as an example:

``````ptr 000 001 002 003 004 005 006
val 025 000 004 000 000 000 000
``````

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

This line can be broken into parts for easier observation, but if you're just using it it's a magic loop:

``````[->+>-
``````

This part minuses the dividend, adds it back on the next cell for preservation, and minuses the divisor. The memory now is:

``````ptr 000 001 002 003 004 005 006
val 024 001 003 000 000 000 000
``````

``````[>+>>]
``````

This adds the removed one from the divisor, for preserving again, since we need it to loop back.

``````ptr 000 001 002 003 004 005 006
val 024 001 003 001 000 000 000
``````

Then, it moves 2 steps rightwards to cell `005`, then `006` because of a `>` in between, skipping the `[+[-<+>]>+>>]` since the cell is empty, then back to cell 000 because of this line:

``````<<<<<<
``````

The extra movement is important because, in order for the system not to loop back again, we need to move to an empty space. moving to `006` is basically because of the extra `>`, which is required for later usage.

Let's skip some steps, and move forward until the divisor becomes 0.

``````ptr 000 001 002 003 004 005 006
val 021 004 000 003 000 000 000
``````

It skips the `[>+>>]` since cell 2 is empty now, and then it moves to cell `003`.

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

Since `003` has a value, it has to run this line. adding one to the value to make it an complete loop, then shift the value back to `002` with the `[-<+>]`. The pointer ends at `003`, so it moves to `004` and to add the value by one to indicate a full cycle and thus one more to the quotient. It moves to `006` and back to `000`.

Repeat the whole thing, then we get:

``````ptr 000 001 002 003 004 005 006
val 000 025 003 001 006 000 000
``````

which is like the last line

``````# >0 n d-n%d n%d n/d
``````

as loop terminates because `000` is now empty. n is now fully shifted to the `001`, `002` and `003` shows the loop process of the divisor when the n is fully zeroed. `004` shows the total completed iteration of the divisor loop.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download