Code patternsArithmeticDivide, with remainder
Divide, with remainder
Divides one cell by another, or by a constant, and gives the quotient and the remainder.
Watch it run
The form “By a cell” works on 6 cells; the named ones are “n”, “d”, “remainder”, “quotient” and “zero”. Press Play, drag the step slider forwards and back, or change n and d with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
Division is counting: take 1 from n and 1 from the divisor, again and again. Every time the divisor reaches zero, one more "whole" has been taken out: add 1 to the quotient and fill the divisor up again.
To fill it up again the loop keeps a second count that goes up while the divisor goes down. That count is also the remainder when n runs out.
The clever part is the pointer. [>+>>] and the loop after it are an if and else on the divisor that end on the same cell both ways.
Why this is costly. One round per unit of n, and the loop is not flat. Dividing 1,000,000 takes about 7 million optimised steps. For a divisor that is a power of two there is a much faster way: shift, round and clamp.
The code
This is the program the figure ran. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-<<
What it needs
- Main form: the six cells n, d, 1, 0, 0, 0. The pattern puts the 1 there itself.
- The divisor must be at least 1. A divisor of 0 acts as "cell size" (256 on 8-bit cells).
- Any cell size. n and d are used up.
Common mistakes
- Using the well-known shorter loop with a divisor of 1. It fails: see the note "Wrong as often given" under this list.
- Reading the raw result: before the tidy-up the cells hold d − remainder and remainder + 1, not d and the remainder.
Wrong as often given
The shorter loop that is usually quoted, [->-[>+>>]>[+[-<+>]>+>>]<<<<<], is correct for a divisor of 2 or more. With a divisor of 1 the pointer walks off to the left. The wiki says so; many copies of the snippet do not. The main form of this page (the first figure) is the wiki's "fixed version", which starts the remainder cell at 1.
Each wrong form is run, and it fails in exactly this way.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| By a cell | about 22 per unit of n | about 7 per unit of n; 9 when d is 1 |
| By a constant | about 22 per unit of n | about 7 per unit of n |
| The short loop (divisor 2 or more) | about 22 per unit of n | about 7 per unit of n |
| Remainder only | about 27 per unit of n | about 11 per unit of n |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| By a cell | n = 17; d = 5 | 8 | 43 | 388 | 130 |
| By a cell | n = 255; d = 10 | 8 | 43 | 5,657 | 1,840 |
| By a cell | n = 255; d = 1 | 8 | 43 | 6,134 | 2,300 |
| By a constant | d = 10; n = 173 | 8 | 53 | 3,861 | 1,251 |
| The short loop (divisor 2 or more) | n = 17; d = 5 | 8 | 30 | 371 | 126 |
| Remainder only | n = 17; d = 5 | 8 | 24 | 460 | 193 |
Other forms
By a constant
The divisor is written into the program.
>++++++++++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-<<
Run this form step by step
The form “By a constant” works on 6 cells; the named ones are “n”, “d”, “remainder”, “quotient” and “zero”. Press Play, drag the step slider forwards and back, or change d and n with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
The short loop (divisor 2 or more)
One character shorter per round and no 1 to set up. The result is raw: d − remainder, remainder, quotient.
[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
Run this form step by step
The form “The short loop (divisor 2 or more)” works on 6 cells; the named ones are “n”, “d − rem”, “remainder”, “quotient” and “zero”. Press Play, drag the step slider forwards and back, or change n and d with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
Remainder only
Layout: zero, n, d, remainder, two zero cells. The pointer starts on n. d ends as d − remainder.
[>->+<[>]>[<+>-]<<[<]>-]
Run this form step by step
The form “Remainder only” works on 6 cells; the named ones are “zero”, “n”, “d − rem” and “remainder”. Press Play, drag the step slider forwards and back, or change n and d with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Print a number in decimal divides by 10 once per digit.
- Build toward a chatbot, lesson 4, "Only one question", measures how slow dividing by counting is.
- The chat program never divides this way: it multiplies by a reciprocal from a table (see table lookup as a decision tree) and shifts (see shift, round and clamp).
Sources
- Source: Esolang wiki: Brainfuck algorithms: sections "Divmod" (the short loop and the "Fixed Version") and "Modulo".
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.