Search

mercredi 8 février 2017

Multiply numbers

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