brhfl.com

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]¹. 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². 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.