Context
Multiplication is a mathematical operation that avoids N successive additions.However, BrainFuck only allows increments and decrements. Even additions are implemented by successive '+1' operations, and multiplication will also be implemented by "successive-succesive +1"
So, to compute A*B we need to sum A, B times. And as sum destroys one of the operands, we need to copy A before (or while) summing. Optionally, we may also move the result to first cell
Initial state
- Memory: A, B, 0, 0
- Cursor: first cell
- Input: any
Process
- While first cell is not null
- Decrease first cell
- While second cell is not null
- Decrease second cell
- Increase third / fourth cells
- Loop invariant: first cell + third cell = B, third and fourth cells incremented by the same number
- When first cell equals 0, third cell equals B, fourth cell incremented by B
- Move third cell to second
- Loop invariant: fourth cell = (A - first cell)xB, second cell = B, third cell = 0
- When first cell equals 0, second equals B, third equals 0, fourth equals AxB
- Optionally, clear second cell, move fourth cell to first
Code
[->[->+>+<<]>[-<+>]<<]>[-]>>[-<<<+>>>]<<<
Final state
- Memory: AxB, 0, 0, 0
- Cursor: first cell
- Input: any
- Output: unchanged
Aucun commentaire:
Enregistrer un commentaire