Code patternsAdvanced: wrapping cells of a known widthThe bit peel
The bit peel
Reads a number bit by bit, at a fixed cost per bit, instead of counting it down unit by unit.
Watch it run
The form “Eight bits of a number” works on 16 cells; the named ones are “x”, “bit 0”, “bit 1”, “bit 2”, “bit 3”, “bit 4”, “bit 5”, “bit 6” and “bit 7”. Press Play, drag the step slider forwards and back, or change x with the slider:
The figure needs JavaScript. The program below is the result for the example values.
On a cell that wraps, multiplying by 2 pushes the top bit out of the cell. Multiply by enough twos and only one bit of the number is left inside: the cell is non-zero exactly when that bit is set.
And multiplying is a flat loop: one step. So "is bit j set?" becomes a question brainfuck can ask, at a cost that does not depend on the number.
The peel asks it for the lowest bit first. If the bit is set, it is taken off the number, so that the next test sees one bit again. Eight bits take 23 to 56 optimised steps: 23 when one bit is set, 56 when all eight are. The size of the number does not come into it.
Everything on the advanced pages is "peel some bits and do something for each set bit".
The code
This is the program the figure ran, written by the generators for these values and this cell size. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>>>>>+<<<<<[->+>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[[-]>>>[-<<<<->>>>>+<]>[-<+>]>>+<<<<<<]<[-<+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[[-]>>>[-<<<<<-->>>>>>+<]>[-<+>]>>>+<<<<<<<]<<[->+>++++++++++++++++++++++++++++++++<<]>>[[-]>>>[-<<<<---->>>>>+<]>[-<+>]>>>>+<<<<<<<<]<[-<+>>++++++++++++++++<]>[[-]>>>[-<<<<<-------->>>>>>+<]>[-<+>]>>>>>+<<<<<<<<<]<<[->+>++++++++<<]>>[[-]>>>[-<<<<---------------->>>>>+<]>[-<+>]>>>>>>+<<<<<<<<<<]<[-<+>>++++<]>[[-]>>>[-<<<<<-------------------------------->>>>>>+<]>[-<+>]>>>>>>>+<<<<<<<<<<<]<<[->+>++<<]>>[[-]>>>[-<<<<---------------------------------------------------------------->>>>>+<]>[-<+>]>>>>>>>>+<<<<<<<<<<<<]<[->+<]>[[-]>>>>>>>>>>>>>+<<<<<<<<<<<<<]>>>[-]
What it needs
- Cells that wrap at a known width. The program text is made for that width (8, 16 or 32 bits) and gives wrong answers on any other.
- To be fast it needs an interpreter that does a flat loop in one step. In plain steps the shifts are long loops and the gain is lost.
- Six scratch cells, zero before and after. The number is used up.
Common mistakes
- Running the 8-bit text on 16-bit cells: the bits no longer fall out where the text expects.
- Peeling from the top bit down. The low bits must be gone first, or the test sees several bits at once.
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 |
|---|---|---|
| Eight bits of a number | hundreds to tens of thousands: each shift is a long loop | about 18 + 5 per set bit |
| The naive way: halve eight times | about 55 per unit of x | about 16 per unit of x |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Eight bits of a number | x = 1 | 8 | 828 | 482 | 23 |
| Eight bits of a number | x = 100 | 8 | 828 | 30,836 | 33 |
| Eight bits of a number | x = 255 | 8 | 828 | 78,975 | 56 |
| The naive way: halve eight times | x = 1 | 8 | 624 | 204 | 64 |
| The naive way: halve eight times | x = 100 | 8 | 624 | 5,621 | 1,630 |
| The naive way: halve eight times | x = 255 | 8 | 624 | 14,041 | 4,065 |
Against the naive way
The same eight bits by halving the number eight times with the division loop of divide, with remainder.
The numbers, row by row
This pattern against the naive way, on 8-bit cells, measured when this page was written. The bars show the last row: optimised steps.
| Values | Optimised steps | Plain steps | Characters | |||
|---|---|---|---|---|---|---|
| pattern | naive | pattern | naive | pattern | naive | |
| x = 1 | 23 | 64 | 482 | 204 | 828 | 624 |
| x = 100 | 33 | 1,630 | 30,836 | 5,621 | 828 | 624 |
| x = 255 | 56 | 4,065 | 78,975 | 14,041 | 828 | 624 |
Other forms
to measure against The naive way: halve eight times
Each bit is the remainder of a division by 2. Works on any cell size, and costs time for every unit of the number.
>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>+<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>+<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>+<<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>>+<<<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>>>+<<<<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>>>>+<<<<<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>>>>>+<<<<<<<<<<<]>[-<<<+>>>]<<<>++>+<<[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>[-]>-[->>>>>>>>>>>>+<<<<<<<<<<<<]>[-<<<+>>>]<<<
Run this form step by step
The form “The naive way: halve eight times” works on 15 cells; the named ones are “x”, “bit 0”, “bit 1”, “bit 2”, “bit 3”, “bit 4”, “bit 5”, “bit 6” and “bit 7”. Press Play, drag the step slider forwards and back, or change x with the slider:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Build toward a chatbot, lesson 5, "Peeling off bits", builds it up from a single doubling.
- In the chat model:
peelin patterns.js. Its division, its multiplication and its lookups all rest on it: see How it works, section "Why it does not take a year". - Built on it in this library: shift, round and clamp, signed multiplication, table lookup.
Sources
- Source: This project: emit.js and patterns.js: peel.
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.