Content is user-generated and unverified.

Nth Fibonacci number in Brainfuck

Problem

Read an integer N ≥ 1 and output the Nth Fibonacci number using the 1-indexed sequence with F(1) = 1 and F(2) = 1.

Strategy

The program stores numbers in BCD (Binary-Coded Decimal) — one cell per decimal digit, five digits total — so it can handle values up to 99 999. That covers F(1) through F(25) = 75 025.

Phases

Parse N from ASCII decimal into a single-byte counter (reuses the digit-detection race from the integer-sum program)
Decrement counter by 1 (N − 1 iterations produce F(N))
Initialize a = 0, b = 1 in 5-digit BCD
Loop (N − 1) times: b_new = a + b, a_new = b_old, using digit-by-digit addition with carry normalisation
Print b as decimal with leading-zero suppression

BCD addition with carry

For each digit position (ones through ten-thousands):

Add A[i] to B[i] (move, destructive)
Add incoming carry to B[i]
Normalise: if B[i] ≥ 10, subtract 10 and set carry for position i + 1

The ≥ 10 check uses the same "race two counters" technique as the input-parser's digit detection: copy the digit value, subtract 10, then race the result against a fresh counter of 10. If the counter is still positive after the race, the subtraction was valid (digit was ≥ 10).

EOF portability

Every , is preceded by [-] so the program works correctly on interpreters where , on EOF leaves the cell unchanged.

Memory layout

text

  Cells   Purpose
  ─────   ──────────────────────────────
   0– 4   A[0..4]  BCD digits (ones at 0)
   5– 9   B[0..4]  BCD digits
  10–14   T[0..4]  temp copy of B (for old-B → A)
  15      carry flag (BCD addition)
  16      loop counter (N − 1)
  17      leading-digit flag (output)
  20–26   input-parse temps + digit-check
  30–37   BCD normalisation work cells

Raw code (4556 characters)

brainfuck

>>>>>>>>>>>>>>>>>>>>[-],[>+>+<<-]>>[<<+>>-]<--------------------------
---------------------->++++++++++<[->[>+>+<<-]>>[<<+>>-]+<[<->>-<[-]]>
[<<<[-]>>>-]<<<]>>>>>[-]<<<<[>>>>+<<<<-]<[-]>>>>>[<<<<<<<<<<[>>>>>+<<<
<<-]>>>>>[<<<<<++++++++++>>>>>-]<[>+>+<<-]>>[<<+>>-]<-----------------
-------------------------------[<<<<<+>>>>>-]<[-],[>+>+<<-]>>[<<+>>-]<
------------------------------------------------>++++++++++<[->[>+>+<<
-]>>[<<+>>-]+<[<->>-<[-]]>[<<<[-]>>>-]<<<]>>>>>[-]<<<<[>>>>+<<<<-]<[-]
>>>>>]<<<<<<<<<<-<<<<<<<<<<<+>>>>>>>>>>>[<<<<<<<<<<<[>>>>>+>>>>>>>>>>>
>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<
<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<<<<<<<<<
[>>>>>+>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>
>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>-]<<<<<<<<<<<
<<<<<<<<<<<<[>>>>>+>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>
>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>-]<<<<
<<<<<<<<<<<<<<<<<<[>>>>>+>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<-]>>>
>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>-]<<<
<<<<<<<<<<<<<<<<<<[>>>>>+>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<-]>>>>>
>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>-]<<<<<<<<
<<<<<<<[-]<<<<<<<<<<<<<<<[>>>>>+<<<<<-]>>>>>>>>>>>>>>>[<<<<<<<<<<+>>>>
>>>>>>-]<<<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<<<
<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>
>>>>>>>>>>>>-]>---------->++++++++++<[>[>+>+<<-]>>[<<+>>-]+<[<-<->>>-<
[-]]>[<<<[-]>>>-]<<<]>>+<[<<<<<<<<<<<<<<<<<<<<<<<<<<<---------->>>>>>>
>>>+>>>>>>>>>>>>>>>>>>-<[-]]>[-]<<<[-]>[-]<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<[>>>>>+<<<<<-]>>>>>>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<<<[>>>>>>>>
>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>
[<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>-]>---------->++++++
++++<[>[>+>+<<-]>>[<<+>>-]+<[<-<->>>-<[-]]>[<<<[-]>>>-]<<<]>>+<[<<<<<<
<<<<<<<<<<<<<<<<<<<<---------->>>>>>>>>+>>>>>>>>>>>>>>>>>>-<[-]]>[-]<<
<[-]>[-]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>+<<<<<-]>>>>>>>>>>>>>[<<<<<
<<<+>>>>>>>>-]<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<
<<<-]>>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>
>>>>>>-]>---------->++++++++++<[>[>+>+<<-]>>[<<+>>-]+<[<-<->>>-<[-]]>[
<<<[-]>>>-]<<<]>>+<[<<<<<<<<<<<<<<<<<<<<<<<<<---------->>>>>>>>+>>>>>>
>>>>>>>>>>>>-<[-]]>[-]<<<[-]>[-]<<<<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>+<<<
<<-]>>>>>>>>>>>>[<<<<<<<+>>>>>>>-]<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>+>+<<<
<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<+>>
>>>>>>>>>>>>>>>>>>>>-]>---------->++++++++++<[>[>+>+<<-]>>[<<+>>-]+<[<
-<->>>-<[-]]>[<<<[-]>>>-]<<<]>>+<[<<<<<<<<<<<<<<<<<<<<<<<<---------->>
>>>>>+>>>>>>>>>>>>>>>>>>-<[-]]>[-]<<<[-]>[-]<<<<<<<<<<<<<<<<<<<<<<<<<<
<[>>>>>+<<<<<-]>>>>>>>>>>>[<<<<<<+>>>>>>-]<<<<<[<<<<<<<<<<+>>>>>>>>>>-
]>[<<<<<<<<<<+>>>>>>>>>>-]>[<<<<<<<<<<+>>>>>>>>>>-]>[<<<<<<<<<<+>>>>>>
>>>>-]>[<<<<<<<<<<+>>>>>>>>>>-]>>-]>[-]<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>+
>+<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<
<+>>>>>>>>>>>>>>>>>>>>>>-]<[>+<[-]]<<<<<<<<<<<<<[>>>>>>>>>>>>>+>>+<<<<
<<<<<<<<<<<-]>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>-]<[<+>-]<
[>+<[-]]>[<<<<<<<<<<<<<<<<<<<<<<++++++++++++++++++++++++++++++++++++++
++++++++++.[-]>>>>>>>>[-]+>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<<<<<<<<[>>>>
>>>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>[
<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>-]<[>+<[-]]<<<<<<<<<<<<
<[>>>>>>>>>>>>>+>>+<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<+>>
>>>>>>>>>>>>>-]<[<+>-]<[>+<[-]]>[<<<<<<<<<<<<<<<<<<<<<<<++++++++++++++
++++++++++++++++++++++++++++++++++.[-]>>>>>>>>>[-]+>>>>>>>>>>>>>>-]<<<
<<<<<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<<
<<-]>>>>>>>>>>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>
>>>>>>>>-]<[>+<[-]]<<<<<<<<<<<<<[>>>>>>>>>>>>>+>>+<<<<<<<<<<<<<<<-]>>>
>>>>>>>>>>>>[<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>-]<[<+>-]<[>+<[-]]>[<<<<<<
<<<<<<<<<<<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++.[-]
>>>>>>>>>>[-]+>>>>>>>>>>>>>>-]<<<<<<<<<<<<<<<<<<<<<<<<<[>>>>>>>>>>>>>>
>>>>>>>>>>+>+<<<<<<<<<<<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>>>>>>>>>>>[<<<<
<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>-]<[>+<[-]]<<<<<<<<<<<<
<[>>>>>>>>>>>>>+>>+<<<<<<<<<<<<<<<-]>>>>>>>>>>>>>>>[<<<<<<<<<<<<<<<+>>
>>>>>>>>>>>>>-]<[<+>-]<[>+<[-]]>[<<<<<<<<<<<<<<<<<<<<<<<<<++++++++++++
++++++++++++++++++++++++++++++++++++.[-]>>>>>>>>>>>[-]+>>>>>>>>>>>>>>-
]<<<<<<<<<<<<<<<<<<<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++
+++++.

Test results

text

 N   F(N)     Status
───  ───────  ──────
  1  1        OK
  2  1        OK
  5  5        OK
  7  13       OK
 10  55       OK
 12  144      OK
 15  610      OK
 17  1597     OK
 20  6765     OK
 25  75025    OK

All 25 values from F(1) to F(25) verified under both EOF = 0 and EOF = unchanged semantics.

Limits

Five BCD digits cap the output at 99 999, so N ≤ 25 (F(25) = 75 025). F(26) = 121 393 needs a sixth digit and would require a minor extension (one more cell per register and one more addition round).

Content is user-generated and unverified.