The algorithm
The greatest common divisor of two positive integers is the largest integer that divides both. Euclid’s method finds it without factoring: replace the pair (a, b) with (b, a mod b), and repeat until the second number is zero. The first number is then the answer.
With a = 48 and b = 18 (example values):
| Step | a | b | a mod b |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| 4 | 6 | 0 | stop |
The answer is 6. Each step is a division with remainder, which makes this a good fit for a language where the remainder instruction is available and the loop test is naturally “is it zero?”
Where the stack runs short
Put a and b on the program stack as [a, b]. The next pair should be [b, a mod b]. Computing a mod b with the remainder instruction consumes both numbers, and b is needed again afterward. You would like a rotation that pulls the third item to the top, but Befunge-93 has only dup, swap and discard. The standard workaround is to copy b into a spare grid cell before dividing and read it back afterward. This is the same grid variables idea used in other programs in this cluster, and it keeps the stack shallow.
The program
68*92*v\g90%p90:<
>: |
>$.@It prints 6. Reading it as the pointer would:
Setup. 68* pushes 48 and 92* pushes 18, giving [48, 18]. The v sends the pointer down to the second row.
Test. The right arrow heads east, dup copies b, and the vertical-if pops the copy. If b is zero the pointer drops to the third row. Otherwise it goes up into the loop body.
Body. On the first row the pointer travels west. The cells it meets are :, 0, 9, p, %, 0, 9, g, \. With [a, b]:
:gives [a, b, b]09pstores the top copy of b in the cell at column 0, row 9, leaving [a, b]%gives [a mod b]09greads b back, giving [a mod b, b]\swaps, giving [b, a mod b]
The new pair is ready, and the v returns the pointer to the test. For 48 and 18 the stack after each pass is [18, 12], then [12, 6], then [6, 0]. At that point the test sees zero and exits.
Finish. The right arrow in the third row sends the pointer east. $ discards the zero and . prints the remaining value, 6, before @ ends the program.
Why the exit works so cleanly
The loop’s stopping rule is that b equals zero, and the branching instructions already branch on zero. No comparison instruction is needed, so the test costs just a dup and a vertical-if. Many algorithms need extra instructions to turn a condition into a zero or nonzero flag. Euclid’s method needs none, which is a small reason it is a favorite first algorithm for Befunge.
It also always ends. The second number strictly decreases each pass, because a mod b is less than b, and it cannot go below zero, so the loop is bounded for non-negative inputs. Proving that kind of thing about arbitrary grid programs is much harder, and a general version of the question runs into the halting problem; here the guarantee comes from the mathematics of remainders, not from the language.
Variations and cautions
- Order of inputs. If a is smaller than b, the first pass computes a mod b = a and swaps the pair, so the method still works; it just spends one extra step.
- Zero inputs. If b starts at 0 the program prints a without looping. If a is 0 and b is positive, the first pass gives (b, 0) and the answer is b, which matches the usual convention. If both are zero the answer prints 0, which is a convention rather than a mathematical result.
- Negative inputs. The remainder of negative numbers can vary between interpreters, so stay with non-negative values.
- The scratch cell. Row 9 must be free. If your layout grows, move the cell rather than let code and data overlap.
- Reading inputs. Replace the two hard-coded numbers with two uses of the integer input instruction, which is the usual numeric input route, to make a small calculator; the loop does not change.
- Underflow. If the stack holds fewer values than an instruction needs, a stack underflow typically supplies zeros instead of failing, so a wrong result is more likely than an error message.
Tracing by hand with pencil and paper, writing the stack as a row after each instruction, is a reliable way to catch a swapped operand. It also shows the one subtle point of the body: after the remainder, the order of the two stack items is the reverse of what the next pass needs, which is why the final swap is there. Without it, the program would divide in the wrong order and, for most inputs, give wrong answers.