After working on the nearest Fibonacci number problem in
dc, I got to thinking about how one might implement other generalized Fibonacci sequences in the language. Nth-order sequences seemed like a fun little challenge, and since I was simply doing it for my own pleasure I went ahead and gave it prompts and user input:
% dc -e '[_nacci? ]n?1-sg[terms? ]n?2-snlgsi[0lid1-si1
G]sG[li;flid1-si0 M]dsMxf' _nacci? 4 terms? 20 20569 10671 5536 2872 1490 773 401 208 108 56 29 15 8 4 2 1 1 0 0 0
…gives us the first 20 terms of the tetranacci sequence. This interested me because unlike a simple Fibonacci iteration that can be handled on the stack with only rudimentary stack manipulation (
dsf+lfr), higher order ‘naccis need summation of more terms. For a defined number, I could simply use registers, but
dc does support arrays, so setting the order at runtime is plausible. There’s a bit going on here, so I’m going to start by rattling off all of the registers I use:
- The order (so, a g-nacci sequence)
- Number of terms to run through
- General counter
- Array used to temporarily hold the last sequence as it’s being summed
- Generalized Fibonacci generating macro
- Macro to retrieve previous sequence from f
- Zero-seed macro
- Counter for iterations (compares to n)
- Main macro
Now to break down what’s going on.
[_nacci? ]n?1-sg[terms? ]n?2-sn just prompts the user and inputs
n. We reduce each of these in the process to appease the loops. After doing this, we need to seed the sequence with
g-1 zeroes, and one one.
lgsi sets counter
g, and then the macro
Z, does nothing but put a zero on the stack and loop:
dsZx stores the macro and executes it; then
1 pushes the necessary one onto the stack such that we can begin.
[dls+ss]sS is our macro,
S, which is a simple summer for register
s. It duplicates the top of stack, recalls
s, adds the two together, and then writes that back to
s. The stack is returned to its original state.
Our next macro,
G, has a bit more going on:
[dls+ssli:flid1+silg>G]sG. It starts with a simple summer for register
dls+ss. This duplicates the stack, recalls
s, adds them and then overwrites
s with the new sum. The stack returns to its original state. The next thing we need to do is move the top of the stack into our holding array,
f. We’ll use our counter
i as an index, so we load
i and then do the array operation,
li:f. Every time we do these two things, our summation (the next number in the sequence) nears its next value, and our stack shrinks. The rest of the macro,
lid1+sig>G just handles incrementing
i and comparing it to our order,
g, determining whether or not to continue the loop.
[li;flid1-si0<R]sR repopulates the stack from array
f. Before calling
i is set to
g, and we use that as our array index to pull from, thus treating the array as a LIFO2.
li;f does this, and then the rest of the macro is (surprise, surprise) counter/loop handling.
Before we run macro
M, which is our main macro essentially, we set counter
z to our order number
g, which accounts for the fact that we already have our first few terms in assorted zeroes and a one.
[0si0sslGxlgsilRxlslzd1+szln>M]dsMx, starts out by resetting counter
i and the sum register
s to zero:
lGx runs macro
lgsi sets counter
i to our order
g, and then
lRx runs macro
ls puts our sum (the new Fibonacci value) at the top of the stack, and then the rest of the thing is counter/loop handling.
dsMx saves the macro as
M and also sets it running, while our last command,
f prints the entire stack.
- One might think that since I increment or decrement counter
ithree times, I could shave off bytes by making a macro of it, but no.
lid1-siand its incrementing twin are 7 bytes each, 21 in total. The generalized macro
[li+dsi]sIis 10 bytes, and then we need to call it with an increment or decrement instruction,
_1lIxtwice (10 bytes) and
1lIxonce (4 bytes). That’s 24 bytes. If we don’t generalize it, and just write a macro for the two decrements, we’re still at 24. ↩︎
- Which makes me think… could I have just used another stack for this? Yes, yes I could have – replacing
Lrespectively works a treat. Oops. ↩︎