Code patternsArithmeticMultiply two cells
Multiply two cells
Multiplies two numbers that are both on the tape.
Watch it run
The form “x becomes x × y” works on 4 cells, named “x”, “y”, “scratch” and “counter”. Press Play, drag the step slider forwards and back, or change x and y with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
x × y is "add y, x times". The outer loop counts x down. Each round copies y into the answer (see copy a value).
It is a loop inside a loop. The inner loops are flat and cost one optimised step each, but the outer loop is not flat: its cost is a few steps for every unit of x.
That is fine for small numbers and hopeless for large ones. And a negative x on a wrapping cell is a very large number.
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: two scratch cells that are zero. y is kept, x is replaced by the product.
- Any cell size. Too large a product wraps.
- For numbers that may be large or negative, see signed multiplication by shift-and-add.
Common mistakes
- Looping on the larger number. The cost follows the outer counter: put the smaller one there.
- Forgetting that −3 on 32-bit cells means 4,294,967,293 rounds.
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 |
|---|---|---|
| x becomes x × y | 13 to 16 × x × y | 3 + 4x |
| Adding the product to a third cell | about 18 × a × b | 2 + 5a |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| x becomes x × y | x = 6; y = 7 | 8 | 38 | 656 | 27 |
| x becomes x × y | x = 15; y = 17 | 8 | 38 | 3,578 | 63 |
| x becomes x × y | x = 255; y = 255 | 8 | 38 | 849,668 | 1,023 |
| Adding the product to a third cell | a = 6; b = 7 | 8 | 50 | 959 | 32 |
Other forms
Adding the product to a third cell
acc gets a × b added; a and b are kept. This is the text the project generator writes. Layout: a, b, acc, two scratch cells.
[->>>+<<[->+>>+<<<]>>>[-<<<+>>>]<<<<]>>>[-<<<+>>>]
Run this form step by step
The form “Adding the product to a third cell” 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", shows why this is the second obstacle.
- Built on it in this library: square and powers of two, and powers.
- In the project:
addMulin emit.js, kept only as the slow way to measure against.
Sources
- Source: Esolang wiki: Brainfuck algorithms: section "x = x * y".
- Source: This project: emit.js and patterns.js: addMul.
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.