## Nth-order Fibonacci sequence in dc

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<Z]dsZx1[dls+ssli:flid1+silg>G]sG[li;flid1-si0<R]sRlgsz[0si0sslGxlgsilRxlslzd1+szln>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:

g:
The order (so, a g-nacci sequence)
n:
Number of terms to run through
s:
Sum
i:
General counter
f:
Array used to temporarily hold the last sequence as it’s being summed
G:
Generalized Fibonacci generating macro
R:
Macro to retrieve previous sequence from f
Z:
Zero-seed macro
z:
Counter for iterations (compares to n)
M:
Main macro

Now to break down what’s going on. `[_nacci? ]n?1-sg[terms? ]n?2-sn` just prompts the user and inputs `g` and `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 `i` to `g`, and then the macro `Z`, does nothing but put a zero on the stack and loop: `[0lid1-si1<Z]`1. `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 `s`, `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.

Macro `R`, `[li;flid1-si0<R]sR` repopulates the stack from array `f`. Before calling `R`, `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. `M`, `[0si0sslGxlgsilRxlslzd1+szln>M]dsMx`, starts out by resetting counter `i` and the sum register `s` to zero: `0si0ss`. `lGx` runs macro `G`, `lgsi` sets counter `i` to our order `g`, and then `lRx` runs macro `R`. `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.

1. One might think that since I increment or decrement counter `i` three times, I could shave off bytes by making a macro of it, but no. `lid1-si` and its incrementing twin are 7 bytes each, 21 in total. The generalized macro `[li+dsi]sI` is 10 bytes, and then we need to call it with an increment or decrement instruction, `_1lIx` twice (10 bytes) and `1lIx` once (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. ↩︎
2. Which makes me think… could I have just used another stack for this? Yes, yes I could have – replacing `li:` and `li;` with `S` and `L` respectively works a treat. Oops. ↩︎