Fibonacci golf with one state variable

aufflick has asked for the wisdom of the Perl Monks concerning the following question:

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/'` [download]	[reply] [d/l]
Re^2: Fibonacci golf with one state variable by aufflick (Deacon) on Oct 05, 2008 at 11:54 UTC
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 :)	[reply] [d/l]
Re^3: Fibonacci golf with one state variable by JavaFan (Canon) on Oct 05, 2008 at 13:21 UTC
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.	[reply]
Re^4: Fibonacci golf with one state variable by aufflick (Deacon) on Oct 06, 2008 at 03:13 UTC
Re^2: Fibonacci golf with one state variable by ikegami (Patriarch) on Oct 05, 2008 at 12:18 UTC
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".	[reply]
Re^2: Fibonacci golf with one state variable by ambrus (Abbot) on Oct 15, 2009 at 17:39 UTC
See also Fibonacci numbers using regexes (threes are wild).	[reply]
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}'` [download] 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.	[reply] [d/l]
Re^2: Fibonacci golf with one state variable by aufflick (Deacon) on Oct 05, 2008 at 11:56 UTC
Except is that exactly the Fibonaci question, using an approximation golden ratio? I'll have to check on that...	[reply]
Re^3: Fibonacci golf with one state variable by ambrus (Abbot) on Oct 05, 2008 at 12:25 UTC
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.)	[reply] [d/l]
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)'` [download] 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: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply] [d/l]
Re^2: Fibonacci golf with one state variable by aufflick (Deacon) on Oct 08, 2008 at 02:05 UTC
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` [download] 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` [download] 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` [download] 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.	[reply] [d/l] [select]
Re: Fibonacci golf with one state variable by ysth (Canon) on Oct 06, 2008 at 03:07 UTC
Just for fun: `perl -E'sub f{$_[0]<2\|\|f($_[0]-1)+f($_[0]-2)}say f$f++while 1'` [download] -- Online Fortune Cookie Search Office Space merchandise	[reply] [d/l]
Re: Fibonacci golf with one state variable by Skeeve (Parson) 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'` [download] BTW: What's "say"? My perdoc doesn't tell me anything about it. `s$$([},&%#}/&/]+}%&{});#$&&s&&$^X.($'^"%]=\&(\|?{%` `+`.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e	[reply] [d/l] [select]
Re^2: Fibonacci golf with one state variable by Lawliet (Curate) on Oct 05, 2008 at 22:32 UTC
"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	[reply] [d/l]
Re^2: Fibonacci golf with one state variable by ikegami (Patriarch) on Oct 05, 2008 at 23:01 UTC
It's new in 5.10, and so is `-E`.	[reply] [d/l]