Code patternsAdvanced: wrapping cells of a known widthWrite many numbers compactly as digits
Write many numbers compactly as digits
Puts a long row of fixed numbers on the tape with a few characters per number, instead of one plus sign per unit.
Watch it run
The form “Three digit places in base 5” works on 10 cells; the named ones are “number 0”, “number 1”, “number 2”, “number 3”, “number 4” and “number 5”. Press Play, drag the step slider forwards and back, or edit the numbers (13 to 262):
The figure needs JavaScript. The program below is the result for the example values.
A number written as plus signs costs its own value in characters. Written in digits it costs a few characters per digit: 200 is 1, 3, 0 in base 5 with digits from −2 to 2.
The row is written one digit place at a time, for all numbers at once. The text walks along the row and gives every cell its small top digit. Then one loop, [[-<+++++>]>], multiplies every cell by 5 into its left neighbour. Then the next digit is added, and so on.
That loop tests the cell it stands on to know whether the row has ended. So no cell may be zero on the way: every number starts at 1, and the digits are chosen with that in mind.
The code
This is the program the figure ran, written for these values. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
>>>>+>+>+>+>+>++++++++++<++++<<+++++++<++<+++[[-<+++++>]>]<<<<+<<--<[[-<+++++>]>]<<<++<+<<-<[[-<+>]>]
What it needs
- The row ends up three cells to the left of where it is first written: one cell per digit place.
- A zero cell after the row. Cells wide enough for the numbers (here above 255, so 16 or 32 bits).
- With this simple form the numbers must lie between 13 and 262.
Common mistakes
- A number that passes through zero between two digit places: the multiplying loop stops there and the rest of the row is lost.
- Thinking this saves steps. It saves characters; the steps are about the same.
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 |
|---|---|---|
| Three digit places in base 5 | about 7 per unit of every number | about 9 per number |
| The naive way: one plus per unit | the sum of the numbers | 1 per number |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Three digit places in base 5 | a = 100, 64, 200, 31, 127, 250 | 16 | 101 | 5,648 | 54 |
| Three digit places in base 5 | a = 262, 262, 262, 262, 262, … (12) | 16 | 255 | 22,747 | 122 |
| The naive way: one plus per unit | a = 100, 64, 200, 31, 127, 250 | 16 | 778 | 778 | 6 |
| The naive way: one plus per unit | a = 262, 262, 262, 262, 262, … (12) | 16 | 3,156 | 3,156 | 12 |
Against the naive way
The same row written with one plus sign per unit. Look at the length of the text.
The numbers, row by row
This pattern against the naive way, on 16-bit cells, measured when this page was written. The bars show the last row: the length of the two program texts.
| Values | Optimised steps | Plain steps | Characters | |||
|---|---|---|---|---|---|---|
| pattern | naive | pattern | naive | pattern | naive | |
| a = 100, 64, 200, 31, 127, 250 | 54 | 6 | 5,648 | 778 | 101 | 778 |
| a = 262, 262, 262, 262, 262, … (12) | 122 | 12 | 22,747 | 3,156 | 255 | 3,156 |
Other forms
to measure against The naive way: one plus per unit
Short to explain, long to write.
>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Run this form step by step
The form “The naive way: one plus per unit” works on 7 cells; the named ones are “number 0”, “number 1”, “number 2”, “number 3”, “number 4” and “number 5”. Press Play, drag the step slider forwards and back, or edit the numbers (13 to 262):
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Build toward a chatbot, lesson 8, "Size": holding 135 million weights.
- The chat model writes all its weights onto the tape this way before it starts: see How it works, section "A billion characters of numbers". Its encoder (compiler/smollm/pure/encode.js) uses more digit places and a final correction; this page shows the simplified form that Build toward a chatbot, lesson 8, "Size", uses.
Sources
- Source: This project: emit.js and patterns.js: the encoder of the chat program, simplified as in Build toward a chatbot, lesson 8, "Size".
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.