The plan
The factorial of a positive integer n is n times n minus 1, and so on down to 1. For 5 that is 5 × 4 × 3 × 2 × 1 = 120. The natural loop, like most Befunge loops, keeps two values: a counter that starts at n and counts down, and a running product that starts at 1.
On a stack, those two values collide. The loop body must multiply the product by the counter and also decrement the counter, and Befunge-93 cannot reach the second item of a three-item stack. Because the program stack only gives cheap access to its top, the simple fix is to keep the counter on the stack and park the product in a spare grid cell. This program uses the cell in column 0, row 9, far from the code.
The program
109p5v -1p90*g90:<
>: |
>$09g.@It prints 120. Here is how it reads.
Setup (first row, left to right). The digits 1, 0, 9 push three numbers, and put (p) pops a row, a column and a value, storing the value at that coordinate. So the product cell starts at 1. Then 5 pushes the counter, and v turns the pointer down.
Test (second row). This is the conditional branching step of the loop. The right arrow at column 5 sends the pointer east. Dup (:) copies the counter and the vertical-if (|) pops the copy. If it is zero the pointer goes down; otherwise it goes up into the loop body.
Body (first row, read right to left). After the pointer turns up from the vertical-if it lands on the left arrow at the end of the first row and travels west. The cells, in the order the pointer meets them, are :, 0, 9, g, *, 0, 9, p, 1, -. In words: duplicate the counter, read the product from the cell, multiply, store the new product back, then subtract 1 from the counter. The v at column 5 sends the pointer back down to the test.
Finish (third row). When the counter reaches 0, the pointer drops to the right arrow in the third row, pops the leftover 0 with $, reads the product with 09g, prints it with . and stops at @.
What the stack holds on each pass
The table lists the state after the loop body finishes, not counting the temporary copy used by the test.
| Pass | Counter before | Product before | Product after | Counter on stack after |
|---|---|---|---|---|
| 1 | 5 | 1 | 5 | 4 |
| 2 | 4 | 5 | 20 | 3 |
| 3 | 3 | 20 | 60 | 2 |
| 4 | 2 | 60 | 120 | 1 |
| 5 | 1 | 120 | 120 | 0 |
Inside a single pass with the counter at 4 and the product at 5, the stack goes like this, shown bottom to top:
:gives [4, 4]09ggives [4, 4, 5]*gives [4, 20]09ppushes 0 and 9 and then stores 20 in the cell, leaving [4]1-gives [3]
That is what tracing by hand looks like, and it is the quickest way to confirm that a loop body leaves the stack with exactly one counter on it. A body that leaves an extra value behind is the most common cause of a factorial loop going wrong.
The last pass multiplies by 1, which changes nothing. That is harmless, though you could trim it by stopping when the counter reaches 1 instead of 0. The simpler test is kept here because zero is exactly what the branching instructions look for.
Reading n from the user
To compute the factorial of a number typed in, replace the 5 in the setup with the ampersand input instruction, which reads an integer. Numeric input has its own quirks, such as what happens on bad text, so test it separately. Also note that the program as written does not handle 0 as input correctly in the usual mathematical sense: with a counter of 0 it skips the loop and prints the initial product, 1. That happens to match 0! = 1, but it is a result of the test order rather than a deliberate case.
Limits
- Overflow. Factorials grow fast. 12! is 479,001,600, which fits in a 32-bit signed integer, but 13! is 6,227,020,800, which does not. Many interpreters use cells of that size, but some use wider ones, so the point where results go wrong depends on the interpreter.
- Silent mistakes. Popping one value too many, a stack underflow, usually yields a zero rather than an error, which can hide a bug in a loop body.
- Negative input. A negative counter never reaches zero by counting down, so the loop would run until the numbers wrap around or the program is stopped.
- Scratch cell safety. Storing the product in a grid cell is only safe if nothing else uses that cell. Here row 9 is empty, so nothing is overwritten.
Keeping the product in a cell is a small taste of what grid variables offer. A factorial can also be done with no scratch cell at all, by pushing the counter values n, n−1, down to 1 and multiplying them together afterward, but then the program needs a way to know when only one value is left on the stack, which costs more instructions than it saves. The cell-based version is easier to read and to check.