The sequence and the state it needs
The Fibonacci sequence starts 1, 1 and each later term is the sum of the previous two: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. To generate it one term at a time, a program needs the last two terms. Call them p (previous) and c (current). One step replaces the pair (p, c) with (c, p + c).
In most languages that is three assignments with a temporary variable. On the program stack the pair lives as [p, c] with c on top, and the step must produce [c, p + c]. The addition consumes both values, but c is needed again afterward. That is the same difficulty seen in Euclid’s method, and it calls for a duplicate of c to survive the addition.
Dup, swap and the missing rotation
Some stack languages provide a rotate or an “over” operation that copies the second item to the top. Befunge-93 has neither. It has dup (:), swap (\) and discard ($), plus get and put for the grid. A tempting plan is to dup c, add, and swap, but the arithmetic works out wrong: dup gives [p, c, c], adding the top two gives [p, 2c], and p is lost. What is needed is to get at p underneath, and that takes a rotation of three items.
The program here sidesteps the problem with a scratch cell, one of the simplest grid variables. Before adding, store a copy of c in a grid cell. After the addition, read it back and swap. That leaves [c, p + c].
The program
01v\g90+p90:.:<
>:55*2*`! |
@It prints 1 1 2 3 5 8 13 21 34 (each number followed by a space). The two characters in the second row that may look unusual are the backtick, which is the greater-than instruction, and !, which is logical not.
Setup. 0 and 1 push the starting pair [0, 1]. The v turns the pointer down to the second row.
Test. The right arrow sends the pointer east. : copies c, 55*2* computes 5 × 5 × 2 = 50, and the backtick compares: it pushes 1 if c is greater than 50 and 0 otherwise. Then ! inverts that, so the result is 1 when c is 50 or less and 0 when c is above 50. The vertical-if pops this flag. A 1 sends the pointer up into the body; a 0 sends it down to @, ending the program. Inverting the flag is a small trick for making “keep going” correspond to nonzero, which suits this branching instruction.
Body. The pointer travels west along the first row, meeting :, ., :, 0, 9, p, +, 0, 9, g, \. With [p, c]:
:gives [p, c, c].prints c and pops it, leaving [p, c]:gives [p, c, c]09pstores c in the cell at column 0, row 9, leaving [p, c]+gives [p + c]09greads c back, giving [p + c, c]\swaps, giving [c, p + c]
Then the arrow at the left end sends the pointer down to the test again.
The stack, pass by pass
| Pass | Pair before | Printed | Pair after |
|---|---|---|---|
| 1 | [0, 1] | 1 | [1, 1] |
| 2 | [1, 1] | 1 | [1, 2] |
| 3 | [1, 2] | 2 | [2, 3] |
| 4 | [2, 3] | 3 | [3, 5] |
| 5 | [3, 5] | 5 | [5, 8] |
| 6 | [5, 8] | 8 | [8, 13] |
| 7 | [8, 13] | 13 | [13, 21] |
| 8 | [13, 21] | 21 | [21, 34] |
| 9 | [21, 34] | 34 | [34, 55] |
After pass 9 the new top value is 55, which is above 50, so the test sends the pointer to the end. The 55 is never printed; the stop check happens before the next print. If you prefer to stop on a different bound, change the numbers in 55*2*. A larger bound needs a larger constant, which in Befunge means building the number from digits and arithmetic.
Counting terms instead of bounding values
Another way to end the loop is to count terms rather than compare against a limit, but that needs a second counter, which means another stack item or another scratch cell. Bounding by value is shorter here. Counting is the better choice if you need exactly the first 20 terms, for instance.
Limits
- Growth. The terms grow roughly by a factor of 1.6 each step, so a fixed-width integer eventually overflows. The exact limit depends on the interpreter, and results beyond it may be wrong or wrap around. Some arithmetic edge cases like this are covered separately.
- The scratch cell. Row 9 is assumed empty. Do not reuse it for something else in the same program.
- Starting values. Starting from [0, 1] prints 1 first, and the leading 0 term is never printed. To show it, print before the first step.
- Readability. The body is written backward along the top row, so it reads right to left. Good code layout helps; even a short comment on paper next to the program saves time later.
The generator is also a natural companion to a countdown program, since both revolve around a value that changes each pass until a test fails. Writing a stack-only version, where you leave every term on the stack and print them at the end, is a good exercise in the style of concatenative languages: it is possible for a short run but quickly becomes awkward without a way to reach into the stack.