The method in ordinary terms
To write a number in base b, divide it by b, note the remainder, and repeat with the quotient until the quotient is zero. The remainders are the digits, but they appear from the least significant end. Take 42 and base 2 (the number is just an example):
| Step | Number | Number ÷ 2 | Remainder |
|---|---|---|---|
| 1 | 42 | 21 | 0 |
| 2 | 21 | 10 | 1 |
| 3 | 10 | 5 | 0 |
| 4 | 5 | 2 | 1 |
| 5 | 2 | 1 | 0 |
| 6 | 1 | 0 | 1 |
Reading the remainders from the last to the first gives 101010, which is 32 + 8 + 2 = 42. Reading them in the order produced would give 010101, the wrong answer. This is the central difficulty: the program discovers the digits in the opposite order from the one in which they must be printed.
Why the stack helps
The program stack gives values back in reverse order. If every remainder is pushed as it is found, the last remainder, the most significant digit, sits on top. Popping and printing then gives the correct order with no extra work. The same property drives string reversal, and here it turns a nuisance into the solution.
There is one wrinkle. The program must know when to stop popping. A digit of 0 is a legitimate value, so you cannot stop at zero. The fix is a sentinel: push a value that can never be a digit, such as −1, before starting. When the printing loop meets that value it stops.
The program
01-76*v/2\%2:<
>: | v,+*86 <
>$ >:1+ |
@It prints 101010. The program has two loops.
Setup. 01- computes 0 − 1 and leaves −1 as the sentinel. 76* pushes 42. The v turns the pointer down.
Division loop. On the second row, > heads east, dup copies the number, and the vertical-if at column 13 pops the copy. A nonzero number sends the pointer up to the left arrow in the first row. The body executes right to left as :, 2, %, \, 2, /. With the number n on the stack:
:gives [n, n]2%gives [n, n mod 2]\swaps, giving [n mod 2, n]2/gives [n mod 2, n ÷ 2]
So the remainder is left underneath and the quotient stays on top for the next pass. After the first pass with 42 the stack is [−1, 0, 21]; after the second it is [−1, 0, 1, 10], and so on. This is the swap that stands in for the usual “keep a variable aside” step, and it works because the remainder never needs to be touched again until printing.
Hand-off. When the quotient reaches 0, the vertical-if sends the pointer down to the third row. The $ discards that final 0. The stack is now [−1, 0, 1, 0, 1, 0, 1] with the most significant digit on top.
Printing loop. The pointer then reaches a second loop. It duplicates the top value and adds 1; if the result is zero, the value was the −1 sentinel, so the vertical-if sends the pointer down to the @. Otherwise it goes up, pushes 6 and 8, multiplies to get 48 (the character code for the digit zero in ASCII), adds that to the digit, and prints it with the comma instruction. The v returns the pointer to the test. Each pass prints one digit, so the whole number appears in the right order.
Changing the base
For another base up to 9, replace both 2s in the division loop with the new base. With 8, the number 42 prints as 52, since 5 × 8 + 2 = 42. The program should print the same digits whichever interpreter you use.
Bases above 10 need letters. Adding 48 only works for digits 0 to 9, so a base-16 version needs a branch: if the digit is 10 or more, add a different offset to reach the letters. That is a job for conditional branching inside the printing loop, and it makes the layout larger. Planning where the extra rectangle goes, a matter of code layout, is as important as the arithmetic.
Edge cases and limits
- Zero. If the number is 0, the division loop is skipped, so the program prints nothing at all. A more careful version would special-case zero, one of several arithmetic edge cases worth handling.
- Negative numbers. Division and remainder on negative numbers can differ between interpreters, so this program is meant for non-negative values only.
- Letters. As above, only single-digit bases work as written.
- Reading the input. The number is hard-coded as 42 here. Reading it with numeric input would turn this into a small utility, but the two-loop structure would be the same.
If the output looks wrong, the usual suspect is the order of the swap in the body, and the quickest check is tracing by hand the first two passes. A wrong order can leave the quotient underneath where it will never be tested, and that often shows up as a loop that never ends.