Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re^2: Fibo Golf challenge on 3 monkeys

by RMGir (Prior)
on Jul 17, 2007 at 11:17 UTC ( #626999=note: print w/replies, xml ) Need Help??

in reply to Re: Fibo Golf challenge on 3 monkeys
in thread Fibo Golf challenge on 3 monkeys

Very .... is "nice" the right term? :))

I know this is perlmonks and not dcmonks, but I'd love to see an expanded and explained version of a few of those dc variants...

I usually only use dc for simple arithmetic and base conversions, so those look like looking at APL and not knowing the keys, to me.


Replies are listed 'Best First'.
Re^3: Fibo Golf challenge on 3 monkeys
by ambrus (Abbot) on Jul 17, 2007 at 12:05 UTC

    Right... let's look at this first

    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.

      These tricks only work on the GNU version of dc, though. System V dc lacks the 'r' and 'K' commands.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://626999]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2018-01-20 16:06 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (227 votes). Check out past polls.