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.
- 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) and1lIx
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:
andli;
withS
andL
respectively works a treat. Oops. ↩︎