## 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. *N*th-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 LIFO^{2}. `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.

- 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. ↩︎ - 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. ↩︎