dc -e1dp[pdsd+ldrlxx]dsxx|head -20
This is my original infinite fibonacci sequence generator from Re: Fibonacci numbers (again), but I quickly added a head statement to limit it to 20 lines and a p statement to print an addittional 1 (this latter extra can be eliminated, but this was just the first attempt).
In this, you have to look at the loop body, which is pdsd+ldr which breaks into six statements: p d sd + ld r. It's easiest if we trace through the execution of this in a later iteration. (The stack is shown with the top first.)
stack cmd meaning
8 5
p prints the top of stack with a newline, without popping
8 5
d duplicate top of stack
8 8 5
sd store pop to named register "d"
8 5
+ push sum of two pops
13
ld push contents of register "d"
8 13
r swap top two elements of stack
13 8
As you can see, the stack contains a fibonacci number and the previous one before executing these statements, which they will advance to the next elements of the sequence, and print an element as a side-effect.
At the beginning, we initialize the stack to two fibonacci numbers 1 1 by the statements 1d. Now you only have to understand the looping, which is done with recursion in dc. The loop itself is a string (which you create with square brackets). After those six statements, it does lx x which loads the same string from register "x" and executes it, while we start the loop by d sx x which duplicates the string, stores one copy to register "x", then executes it the first time.
Now I basically use two tricks to make this shorter. The first one is to use k and K commands instead of sd and ld. These store in the special "scale" register, which affects the results in division and modulo and other similar operations, but that won't make too much difference in our script. That register can only store a nonnegative integer and is usually capped from above, but if we need only the first twenty elements, that's not a problem.
The second is that instead of using |head -20, I limit the loop to the first 20 numbers in the dc script itself. This is done by the >x statement which compares two popped numbers and runs the macro in register "x" iff the first number is greater than the second. In the final version, I use the comparision on the length (number of digits, Z) of a fibonacci number with 5, because this seems to be the shortest. Other attempts (not all in the thread) compare a counter in a register I decrease every time, the fibonacci number itself, the square root of the fibonacci number, and the stack length (z) which then I increased by leaving an unused stack element in every iteration.
Update: fixed link to original post about dc fibonacci.
| 