Euclidean division

Context

Euclidean division is an operation on A (dividend) and B (divisor) that returns Q (quotient) and R (remainder), with

• A=B * Q + R
• 0 <= R < B

In BrainFuck, this can be implemented like this

• Decrease dividend
• Increase remainder
• Decrease divisor
• If divisor = 0
• then remainder = initial divisor, rebuild initial divisor from remainder
• reset remainder
• increase quotient

Initial state

• Memory: A, 0, 0, 0, B, 0
• Cursor: first cell
• Input: any

Process

• While first cell is not null
• Decrease first cell (dividend)
• Increase second (remainder)
• Increase fourth (bit else)
• Decrease fifth (divisor)
• While divisor is not null
• move back to bit else, reset and stay on it
• Move to previous cell (bit else if divisor was null, third cell = 0 otherwise)
• If current cell is not null (so, on bit else)
• move second cell to fifth (rebuild divisor)
• Increment sixth cell (quotient)
• reset bit else
• move to third cell
• Loop invariants
• second + fifth cell = initial divisor
• (second + fifth)*sixth + second + first = initial dividend
• When first cell is null, dividend = divisor * sixth + second; so Q is in sixth cell, and R in second

Code 

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

Final state

• Memory: 0, R, 0, 0, B', Q with B' = B-R
• Cursor: first cell
• Input: any
• Output: unchanged

Note: we can add some extra code to:

• Start with memory A, B, 0, 0, 0, 0
• Clean result to have Q, R, 0, 0, 0, 0

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