Code patternsAdvanced: wrapping cells of a known widthShift, round and clamp
Shift, round and clamp
Divides a signed number by a power of two, rounds it, and keeps the result between −128 and 127.
Watch it run
The form “Divide by 2ᵏ, round, clamp to −128…127” works on 12 cells; the named ones are “X” and “result”. Press Play, drag the step slider forwards and back, or change shift k and X with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
Dividing by 2ᵏ means: throw away the k lowest bits. The bit peel reads the bits one by one, so it can simply not write the low ones.
Rounding is free: add half of 2ᵏ before the division. Negative numbers are free too: add a fixed offset first so that everything is positive, and take it off the result.
The limits are checked without comparing. A second copy of the number has every peeled bit taken off again. If that copy is not zero at the end, the number was outside the range, and only then are the high bits looked at to see on which side.
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:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[-<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>>>]<<<<<<[->>+>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<<<]>>>>>>[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[-<<<<++>>>>]<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[->++<]<<<<[->+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<]>>>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<->>>>>+<]>[-<+>]<<<<<<<->>>]<[-<+>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<<-->>>>>>+<]>[-<+>]<<<<<<<-->>>]<<[->+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<]>>>[-<++++++++++++++++>]<[[-]>>>[-<<<<---->>>>>+<]>[-<+>]<<<<<<<---->>>]<[-<+>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++++++++>]<[[-]>>>[-<<<<<-------->>>>>>+<]>[-<+>]<<<<<<<-------->>>]<<[->+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<]>>>[-<++++>]<[[-]>>>[-<<<<---------------->>>>>+<]>[-<+>]<<<<<<<---------------->>>]<[-<+>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++>]<[[-]>>>[-<<<<<-------------------------------->>>>>>+<]>[-<+>]<<<<<<<-------------------------------->>>]<<[->+>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[[-]>>>[-<<<<---------------------------------------------------------------->>>>>+<]>[-<+>]<<<<<<<---------------------------------------------------------------->>>]<[-<+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[[-]>>>[-<<<<<-------------------------------------------------------------------------------------------------------------------------------->>>>>>+<]>[-<+>]<<<<<<<<+>>>>]>>>[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]<<<<<[->+>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[[-]>>>>[-<<<<<->>>>+>]<[->+<]<<<<<<<++>>>>]<[-<+>>++++++++++++++++++++++++++++++++<]>[[-]>>>>[-<<<<<<-->>>>>+>]<[->+<]<<<<<<<++++>>>>]<<[->+>++++++++++++++++<<]>>[[-]>>>>[-<<<<<---->>>>+>]<[->+<]<<<<<<<++++++++>>>>]<[-<+>>++++++++<]>[[-]>>>>[-<<<<<<-------->>>>>+>]<[->+<]<<<<<<<++++++++++++++++>>>>]<<[->+>++++<<]>>[[-]>>>>[-<<<<<---------------->>>>+>]<[->+<]<<<<<<<++++++++++++++++++++++++++++++++>>>>]<[-<+>>++<]>[[-]>>>>[-<<<<<<-------------------------------->>>>>+>]<[->+<]<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>]<<[->>+<<]>>[[-]<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>]>>>>[-]<<<<<<<<[->-------------------------------------------------------------------------------------------------------------------------------->>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<[<[-]>>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[->>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]<<<<[->>+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<]>>>>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<->>>>>+<]>[-<+>]<<<<]<[-<<+>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<<<-->>>>>>>+<]>[-<+>]<<<<]<<<[->>+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<]>>>>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<---->>>>>+<]>[-<+>]<<<<]<[-<<+>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++++++++++++++++++++++++++++++++>]<[[-]>>>[-<<<<<<-------->>>>>>>+<]>[-<+>]<<<<]<<<[->>+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<]>>>>[-<++++++++++++++++>]<[[-]>>>[-<<<<---------------->>>>>+<]>[-<+>]<<<<]<[-<<+>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++++++++>]<[[-]>>>[-<<<<<<-------------------------------->>>>>>>+<]>[-<+>]<<<<]<<<[->>+>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<<]>>>>[-<++++>]<[[-]>>>[-<<<<---------------------------------------------------------------->>>>>+<]>[-<+>]<<<<]<[-<<+>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<]>>[-<++>]<[[-]>>>[-<<<<<<-------------------------------------------------------------------------------------------------------------------------------->>>>>>>+<]>[-<+>]<<<<]>>>[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]<<<<<<[->>+>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<]>>>[[-]>>>>[-<<<<<->>>>+>]<[->+<]<<<]<[-<<+>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[[-]>>>>[-<<<<<<<-->>>>>>+>]<[->+<]<<<]<<<[->>+>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<<]>>>[[-]>>>>[-<<<<<---->>>>+>]<[->+<]<<<]<[-<<+>>>++++++++++++++++++++++++++++++++<]>[[-]>>>>[-<<<<<<<-------->>>>>>+>]<[->+<]<<<]<<<[->>+>++++++++++++++++<<<]>>>[[-]>>>>[-<<<<<---------------->>>>+>]<[->+<]<<<]<[-<<+>>>++++++++<]>[[-]>>>>[-<<<<<<<-------------------------------->>>>>>+>]<[->+<]<<<]<<<[->>+>++++<<<]>>>[[-]>>>>[-<<<<<---------------------------------------------------------------->>>>+>]<[->+<]<<<]<[-<<+>>>++<]>[[-]>>>>[-<<<<<<<-------------------------------------------------------------------------------------------------------------------------------->>>>>>+>]<[->+<]<<<]>>>>[-]>+<<<<<<<<[[-]>>>>>>>>-<<<<<<<<]>>>>>>>>[-<<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>>>>>>]<<<<<<<<]<--------------------------------------------------------------------------------------------------------------------------------
Open in the playground11,212 characters
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.
- Ten scratch cells. The input is used up. The true value must fit the cell, and k + 8 must be less than the cell width.
Common mistakes
- Letting the sum wrap before it is clamped. A clamp cannot repair a number that has already gone round.
- Using this for a divisor that is not a power of two. For that the project multiplies by a reciprocal from a table first (see table lookup as a decision tree).
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 |
|---|---|---|
| Divide by 2ᵏ, round, clamp to −128…127 | tens of thousands and more | 75 to 100 inside the range, about 160 when the result is clamped |
| The naive way: divide by counting | grows with X × 2ᵏ | about 11 per unit of X |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Divide by 2ᵏ, round, clamp to −128…127 | shift k = 7; X = 11,868 | 32 | 11,212 | more than 30,000,000 | 94 |
| Divide by 2ᵏ, round, clamp to −128…127 | shift k = 7; X = −3,000 | 32 | 11,212 | more than 30,000,000 | 76 |
| Divide by 2ᵏ, round, clamp to −128…127 | shift k = 7; X = 99,999 | 32 | 11,212 | more than 30,000,000 | 156 |
| Divide by 2ᵏ, round, clamp to −128…127 | shift k = 4; X = 1,000 | 32 | 11,691 | more than 30,000,000 | 75 |
| The naive way: divide by counting | shift k = 7; X = 11,868 | 32 | 172 | 13,316,525 | 131,538 |
| The naive way: divide by counting | shift k = 7; X = 300 | 32 | 172 | 424,053 | 4,017 |
| The naive way: divide by counting | shift k = 4; X = 1,000 | 32 | 113 | 163,234 | 11,155 |
Against the naive way
The same division by counting: take 2ᵏ units off, add 1 to the result, again and again. That baseline does not even clamp, and it only takes numbers that are not negative.
The numbers, row by row
This pattern against the naive way, on 32-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 | |
| shift k = 7; X = 11,868 | 94 | 131,538 | more than 30,000,000 | 13,316,525 | 11,212 | 172 |
| shift k = 7; X = 300 | 79 | 4,017 | more than 30,000,000 | 424,053 | 11,212 | 172 |
| shift k = 4; X = 1,000 | 75 | 11,155 | more than 30,000,000 | 163,234 | 11,691 | 113 |
Measured in the project on the sums of a real layer (64 inputs, shift 10, 32-bit cells): about 100 optimised steps per result with the peel, against 1.2 to 1.5 million by counting. measured in the project
Other forms
to measure against The naive way: divide by counting
Rounds, but does not clamp, and X must not be negative.
>>++++++++[-<<++++++++>>]<<>>>+++++++++++[-<+++++++++++>]<+++++++<<[->>->>>+<<<[->+>+<<]>>[-<<+>>]<[>>-<<[-]]>>[<<<<+>>+++++++++++[-<+++++++++++>]<+++++++>>>[-]]<<<<<]>>[-]
Open in the playground172 characters
Run this form step by step
The form “The naive way: divide by counting” works on 6 cells; the named ones are “X”, “result” and “counter”. Press Play, drag the step slider forwards and back, or change shift k and X with the sliders:
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. Build toward a chatbot, lesson 9, "One number of the model", uses it for one number of the model.
- In the chat model:
requantin patterns.js. Every number the model works out goes through it, which keeps the values small: see How it works, section "Multiply and add".
Sources
- Source: This project: emit.js and patterns.js: requant, requantCore, requantCount (the baseline).
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.