Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Fibonacci golf with one state variable

by aufflick (Deacon)
on Oct 05, 2008 at 09:50 UTC ( #715414=perlquestion: print w/replies, xml ) Need Help??
aufflick has asked for the wisdom of the Perl Monks concerning the following question:

I hesitate to start YAFGT (Yet Another Fibonacci Golf Thread), but I had an interesting idea today: a golfed Fibonacci generator with only one state variable. I ended up with two solutions I like.

The second is shorter, but the first has two nice features: no explicit assignment operators and only one type of quote used which allows easy one-lining:

perl -le 'print$2while s/(\d*):?(\d*)/($1+$2||1).":$1"/e' |head -10

$_="$':".($'+$`||1),print$`while x./:/

Both use a single state variable, but it's a colon separated string, so there are still really two state values.

Replies are listed 'Best First'.
Re: Fibonacci golf with one state variable
by JavaFan (Canon) on Oct 05, 2008 at 11:43 UTC
    Without eval, without quotes, without explicit assignment and without arithmetic:
    perl -lE 's//:o/;say length$1 while s/(.*):(.*)/$2:$1$2/'

      Hey that's neat! Of course the memory usage is far from constant, but great idea. Good use of say to save a few.

      Only nitpicks are that you do have explicit initialisation and the first output is zero which is not quite right. Oddly, I get no output unless I tweak it to print to STDERR which is some strange buffering difference - no idea why.

      ++ for thinking laterally :)

        Well, I'd argue that *not* outputting zero isn't quite right. Usually, the Fibonacci sequence is defined as F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2), n > 1. See for instance Sloane: The On-Line Encyclopedia of Integer Sequences and Graham, Knuth and Patashnik in Concrete Mathematics. Eric Weisstein defines the sequence as starting with F(1) = F(2) = 1 and then states it's conventional to define F(0) = 0.

      Heh! I had come up with exactly that! It's not shorter, though. And boy does it get slow fast.

      Save a char by dropping the "l" in "-lE".
      Save a char by dropping the space after "-E".

Re: Fibonacci golf with one state variable
by ambrus (Abbot) on Oct 05, 2008 at 11:51 UTC

    Just one state variable? Re: Fibo Golf challenge on 3 monkeys has such an example:

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

    It's not much longer than yours especially if you count that the second one needs a -l switch and fancy quoting to quote the apostrophes and double quotes.

      Except is that exactly the Fibonaci question, using an approximation golden ratio? I'll have to check on that...

        That's why it only prints the first few terms, with 18 hard-coded it. If you used the golden ratio more precisely, you'd get more terms. Two examples are the first snippet in Re: Fibonacci Numbers or the last one in Re: Fibonacci numbers (again).

        (By the way, if you want to know about the mathematics of this, I recommend Graham–Knuth–Patashnik: Concrete mathematics.)

Re: Fibonacci golf with one state variable
by dragonchild (Archbishop) on Oct 07, 2008 at 14:25 UTC
    How about a tail-recursive version with no state variables?
    perl -E 'sub f{say$_[0];goto&f($_[1],$_[0]+$_[1])}f(1,1)'
    And I'm sure that could be reduced further. And, no, the stack doesn't count as a state variable. :-p

    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

      Sure, of course...

      I'm wondering, though, why the goto&f? It works perfectly well as:

      perl -E 'sub f{say$_[0];f($_[1],$_[0]+$_[1])}f(1,1)' |head -10

      If you want to use the & form that saves on stack operations by not creating a new @_, you could do this (paying careful attention to the right to left execution):

      perl -E 'sub f{say$_[0];$_[1]=$_[1]+shift;&f}f(1,1)' |head -10

      Which is exactly the same length, but less operations. Now if only Perl auto-optimised tail recursion...

      It's a shame that unshift doesn't default to @_ like shift otherwise I could save one character by switching the order of the values on the stack:

      perl -E 'sub f{say$_[1];unshift@_,$_[0]+pop;&f}f(1,1)' |head -10

      Update: I just read the perldoc for goto and I have to say I didn't know that goto &NAME form, so thanks for the learning exercise!. Like my form it won't result in recursive stack blowout. Without studying the internals too carefully I don't know which would result in less operations. Maybe a benchmark will show.

Re: Fibonacci golf with one state variable
by ysth (Canon) on Oct 06, 2008 at 03:07 UTC
Re: Fibonacci golf with one state variable
by Skeeve (Vicar) on Oct 05, 2008 at 22:30 UTC

    Not the shortest, but how do you like this? It prints the whole sequence upt to the first number needing an exponent.

    perl -e '$_||="0$/1";s;(.+)$/(.+)$;"$1$/$2$/".($1+$2);ge while!/e/;pri +nt'

    BTW: What's "say"? My perdoc doesn't tell me anything about it.

      "BTW: What's "say"? My perdoc doesn't tell me anything about it."

      It's like print, but appends a newline. See say.

      I'm so adjective, I verb nouns!

      chomp; # nom nom nom

      It's new in 5.10, and so is -E.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://715414]
Approved by Corion
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (7)
As of 2018-06-20 16:19 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (116 votes). Check out past polls.