Divmod algorithm in brainfuck

Question

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

Sullins

Answer 1

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.

Zincography

Answer 2

The algorithm in the question does not handle division by 1. Here is a variant where division by 1 and 0 are handled correctly:

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

the result of division by zero will have n as the mod and 0 as the division result.

source: https://esolangs.org/wiki/Brainfuck_algorithms#Divmod_algorithm

Royster