BrainFuck part 11 - Iterative and recursive ways

DPAmar
3,021 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

The iterative way

Factorial can be computed using an iterative way : let result be 1, then for each value V between 1 and N, multiply result by V.

Let's start

  • Memory: N 0 0 0 0 0
  • Cursor: first cell
  • Input: any

Process

  • set result to 1
  • set current index to 0
  • invariant: result = (current index)! and first cell + current index = N
  • while first cell is not null
    • increase index
    • multiply result by current index
    • decrease first cell
  • loop
  • first cell = 0, so current index = N and result = N!

Code

>>>>+                        set result to 1 (and current index to 0)
<<<<[                        while first cell is not null
  >[->+>+<<]>[-<+>]>         copy current index
  [->[->+>+<<]>[-<+>]<<]     multiply result by current index
  >>>[-<<+>>]<<<<<+          increase current index and store result x new index into result
<-]                          decrease first cell and loop

Minified version

>>>>+<<<<[[->+>+<<]>>[-<<+>>]<-[->>>[-<+<+>>]<[->+<]<<]>[->>+<<]<<-]

Final state

  • Memory: 0 N 0 0 N!
  • Cursor: first cell
  • Input: unchanged
  • Output: unchanged

Test program

This programs prints x, code 120 = 5!

+++++>>>>+<<<<[>[->+>+<<]>[-<+>]>[->[->+>+<<]>[-<+>]<<]>>>[-<<+>>]<<<<<+<-]>>>>.
Open Source Your Knowledge: become a Contributor and help others learn. Create New Content