Code patternsAdvanced: wrapping cells of a known widthSigned multiplication by shift-and-add
Signed multiplication by shift-and-add
Multiplies two numbers from the tape, negative ones too, at a cost that does not depend on the numbers.
Watch it run
The form “acc gets a × b added” works on 11 cells; the named ones are “a”, “b” and “acc”. Press Play, drag the step slider forwards and back, or change a and b with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
This is long multiplication in base 2. Read a bit by bit with the bit peel. For every set bit j, add b × 2ʲ to the answer.
b × 2ʲ is the pattern multiply by a constant, a flat loop: one step, and b is kept with a second step.
The top bit of a signed number counts negative, so for that one bit the same loop subtracts. Nothing else is needed for negative numbers.
So the cost is about 25 steps for the eight tests and 5 more for every set bit of a: 28 to 60 in all, whether b is 7 or 7 million.
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.
- Eight scratch cells. a is read as a signed 8-bit number; b may be any value. Both are kept.
Common mistakes
- Peeling the wider of the two numbers. The cost follows the bits of a: peel the narrow one.
- An a outside −128…127: only its low 8 bits are used.
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 |
|---|---|---|
| acc gets a × b added | tens of thousands and more | about 25 + 5 per set bit of a |
| The naive way: repeated addition | grows with a × b, each read as a count | 2 + 5 × a, with a read as a count |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| acc gets a × b added | a = 6; b = 7 | 32 | 3,093 | more than 30,000,000 | 36 |
| acc gets a × b added | a = 100; b = −60 | 32 | 3,093 | more than 30,000,000 | 42 |
| acc gets a × b added | a = −25; b = −60 | 32 | 3,093 | more than 30,000,000 | 58 |
| acc gets a × b added | a = −128; b = −128 | 32 | 3,093 | more than 30,000,000 | 28 |
| The naive way: repeated addition | a = 6; b = 7 | 8 | 50 | 959 | 32 |
| The naive way: repeated addition | a = 100; b = −60 | 8 | 50 | 375,005 | 502 |
| The naive way: repeated addition | a = −25; b = −60 | 8 | 50 | 866,255 | 1,157 |
Against the naive way
The same product by repeated addition, the loop of multiply two cells. A negative a is a huge count there: −3 on 16-bit cells is 65,533 rounds.
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: optimised steps.
| Values | Optimised steps | Plain steps | Characters | |||
|---|---|---|---|---|---|---|
| pattern | naive | pattern | naive | pattern | naive | |
| a = 6; b = 7 | 32 | 32 | 502,023 | 959 | 2,041 | 50 |
| a = 100; b = −60 | 38 | 502 | 22,688,925 | more than 30,000,000 | 2,041 | 50 |
| a = −25; b = −60 | 54 | 327,557 | more than 30,000,000 | more than 30,000,000 | 2,041 | 50 |
Measured in the project on 16-bit cells with both numbers between −127 and 127: about 43 optimised steps per product, against about 195,000 by repeated addition. measured in the project
Other forms
to measure against The naive way: repeated addition
The loop of multiply two cells. Correct for negative numbers on wrapping cells, and very slow for them.
[->>>+<<[->+>>+<<<]>>>[-<<<+>>>]<<<<]>>>[-<<<+>>>]
Run this form step by step
The form “The naive way: repeated addition” works on 5 cells; the named ones are “a”, “b”, “acc” and “scratch”. Press Play, drag the step slider forwards and back, or change a and b 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 6, "Two numbers from the tape", multiplies −25 by −60 with it.
- In the chat model:
mulAccanddotVarin patterns.js. It is what makes attention possible, because there both numbers come from the tape: see How it works, section "Looking back at the other words". - Build toward a chatbot, lesson 10, "Looking back", uses it twice.
Sources
- Source: This project: emit.js and patterns.js: mulAcc; the baseline is addMul in emit.js.
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.