Code patternsArithmeticSaturating subtract
Saturating subtract
Subtracts, but stops at zero instead of wrapping round.
Watch it run
The form “Two cells” works on 4 cells, named “x”, “y”, “flag” and “zero”. 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.
A plain subtraction cannot stop at zero, because nothing in a flat loop looks at the cell. So we take single steps and look each time.
Each round takes 1 from the amount to subtract. Then an if and else: if the value still has something, take 1 from it; if it is empty already, clear what is left of the amount.
The cost is one round per unit actually subtracted. That is the price of every "do not go below zero" by counting.
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
- Two zero cells to the right of the value. The amount is used up.
- Any cell size, wrapping or not. The numbers are unsigned.
Common mistakes
- Looping on the value instead of on the amount: then the loop ends too early when the value is smaller.
- Using this on large numbers. With wrapping cells of a known width, the clamp by bits (see shift, round and clamp) costs the same for every number.
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 |
|---|---|---|
| Two cells | about 16 per unit taken off | about 8 per unit taken off |
| By a constant | about 17 per unit of the amount | about 8 per unit of the amount |
| The project form | grows with n × value | about 8 per unit of n |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| Two cells | x = 5; y = 3 | 8 | 27 | 71 | 33 |
| Two cells | x = 3; y = 5 | 8 | 27 | 49 | 25 |
| Two cells | x = 100; y = 250 | 8 | 27 | 1,601 | 801 |
| By a constant | amount n = 4; value = 3 | 8 | 31 | 73 | 34 |
| The project form | amount n = 4; value = 3 | 8 | 45 | 197 | 31 |
Other forms
By a constant
The amount is written into the program, in cell 0. The value is in cell 1.
++++[->>+<[->-]>[<<[-]>>->]<<<]
Run this form step by step
The form “By a constant” works on 4 cells, named “amount”, “value”, “flag” and “zero”. Press Play, drag the step slider forwards and back, or change amount n and value with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
The project form
Tests a copy of the value each round, so the cells may lie anywhere. Layout: value, counter, two scratch cells.
>++++[-<[->>+>+<<<]>>>[-<<<+>>>]<[<<->>[-]]<]
Run this form step by step
The form “The project form” works on 4 cells; the named ones are “value”, “counter” and “scratch”. Press Play, drag the step slider forwards and back, or change amount n and value with the sliders:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Less than: "is something left?".
- In the project:
satSubin emit.js. - Build toward a chatbot, lesson 4, "Only one question", is about this one question and what follows from it.
Sources
- Source: This project: emit.js and patterns.js: satSub; the two-cell loop here is our own.
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.