Re: Fibo Golf challenge on 3 monkeys

[ambrus]

Let's see. We already have lots of fibonacci generator threads, like (OT) Fibonacci numbers in Ruby - final shot - 24 chars, Golfing a fibonacci number generator, Fibonacci Numbers, Fibonacci numbers (again)¹ Fibonacci golf with one state variable¹. We can use some ideas from those threads.

Firstly, modifying my dc solution, we get

dc -e1dp[pdsd+ldrlxx]dsxx|head -20

Then there's the ruby one you can adapt

ruby '-wex=i=1;20.times{p x;x+=i=x-i}'

I'll try to improve these and update this node later if I can.

Update: longer variants of the ruby line are:

ruby '-wep 1,x=1;18.times{p x=(x/0.618).round}'

or

ruby '-we20.times{|x|p((1.61803**x/1.382).round)}'

Update: I forgot to tell, but for just the first twenty numbers, the shorter dc one should work fine as well:

dc -e1pd[pdk+Krlxx]dsxx|head -20

Update: The following which doesn't use head is even shorter

dc -e1pd[rpdk+Kd6666\>x]dsxx

The following is yet one character shorter, but it takes some seconds to compute because it computes square roots to thousands of decimal places.

dc -e1pd[rpdk+Kdv66\>x]dsxx

Update: Even shorter and does not have the speed penalty is this:

dc -e1pd[pdk+KrdZ5\>x]dsxx

Update: And you can cut one more character:

dc -e1d[prdk+KdZ5\>x]dsxx

Update 2008 oct 5: added two links marked by ¹.

[TimToady]

Not implemented yet because we just added it, but in Perl 6 you can just say:

.say for 1,1...{$^a+$^b}

or alternately:

.say for 1,1...&infix:<+>

The latter is likely to be more efficient, since it calls the builtin addition operator without the extra layer of function call implied by the first one (unless we get really fancy with the optimizer and notice it's an identity wrapper).

Either of these works because the ... operator is defined to pass the last N numbers in the list repeatedly to the generator function, where N is determined by the arity of the function, which is 2 in this case.

[RMGir]

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.

[ambrus]

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.

[whio]

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