Fibonacci Series in One Line of Perl
Not ground breaking but here are the first 20 terms in the Fibonacci Series.
Code
perl -e'@p=(0,1);until($#p>20){print"$p[-2]\n”;push @p,$p[-2]+$p[-1]}’
Output
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Can you do better? What about different languages?
Update: it has been suggested that for languages such as Java and C to be included in this experiment, that only the total number of pure source characters be included in the count. Therefore my perl solution in the comments below has 56 pure source characters.
For more information on the Fibonacci Series see http://en.wikipedia.org/wiki/Fibonacci_number
-3Monkeys
Popularity: 69% [?]
(6 votes, average: 5.17 out of 10)
Loading ...
subscribe
July 12th, 2007 at 10:52 pm
Here it is in PHP:
echo fibonacci_terms(20);
Writing fibonacci_terms is left as an exercise for the reader.
July 13th, 2007 at 2:36 am
I was thinking about this on the drive home and remembered that I had used an array construct to avoid a count comparison. I thought to myself, “I could kill a few characters out of that by using for instead of until, and using a alpha range opposed to a numeric range. My improvement below reduce the total characters to 65 from 70.
perl -e’@p=(0,1);for(A..T){print”$p[-2]\n”;push@p,$p[-2]+$p[-1]}’
July 13th, 2007 at 5:28 am
Yes, but which compiles down to the fewest bytes of machine code? (no i didn’t actually try to assemble this, but it seems about right to me)
section .data
string: db “%i\n”,0
section .code
start:
xor edx, edx
.loop:
call fibo
push eax
push string
call printf
add esp, byte 4
inc edx
cmp edx, 20
jl .loop
xor eax, eax
retn
fibo:
cmp edx, 1
jle .zeroone
dec edx
call fibo
push eax
dec edx
call fibo
add [esp], eax
add edx, byte 2
pop eax
retn
.zeroone
mov eax, edx
retn
July 13th, 2007 at 5:30 am
ruby -e ‘p,c=0,1;20.times{p p;c=p+p=c}’
30 characters of pure source.
This works too:
p=0;c=1;20.times{p p;c=p+p=c}
…and is the same number of characters, but the top one is harder to read, so it must be better.
And just to show how uselessly verbose some languages are, here’s one in Java (105 chars):
class T{public static void main(String[] a){int p=0;c=1;while(p<4181){System.out.println(p);c=p+(p=c);}}
July 13th, 2007 at 11:00 am
Got it to this in Groovy:
i=[0,1];(2..19).each{i<<i[it-2]+i[it-1]};i
July 13th, 2007 at 11:20 am
1st attempt, 52 bytes :
perl -e ‘$p=0;$l=1;($l,$p)=($p,$l+$p),print$l.”\n”while$l
July 13th, 2007 at 11:25 am
I’ll try again, with slightly better code! 52 bytes :
$p=0;$l=1;($l,$p)=($p,$l+$p),print”$l\n”while$l<4181
and 51, if you allow multiple line entries :
$p=0;$l=1;($l,$p)=($p,$l+$p),print”$l
“while$l<4181
July 13th, 2007 at 11:50 am
p,n,i=0,1,0
while i
July 13th, 2007 at 11:52 am
2 characters better than the previous perl version (and it doesn’t print that wrong leading 0):
perl -e’@p=(1,1);map@p=(@p,$p[-1]+$p[-2]),A..T;$,=”\n”;print@p’
This would be MUCH shorter in APL. Now if only I remembered my APL…
July 13th, 2007 at 2:45 pm
Here’s a ruby one-liner to get the first n numbers of the Fibonacci sequence:
def fib(n)n==1?[0]: n==2?[0,1]:(p=fib(n-1);p<<p[-2]+p[-1])end
so puts fib(20) would give you what you want
July 13th, 2007 at 3:05 pm
A fib battle huh? Let’s get the Haskell on here:
fib = 1 : 1 : zipWith (+) fib (tail fib)
That’s for an infinite list of fib.
to get the first 20 from that list:
take 20 fib
July 13th, 2007 at 4:32 pm
[...] leo en 3monkeyweb una especie de reto en donde con una linea de perl se escriben los primeros 20 numeros de la serie [...]
July 13th, 2007 at 4:33 pm
Javascript, 52 chars
p=1;for(k=0;k
July 13th, 2007 at 5:08 pm
I don’t think it’s worth competing what language will produce worse complicated tiny code.
Just tell me what is 100000th Fibonacci number.
When you’ll get old waiting for this:
p=0;c=1;100000.times{p p;c=p+p=c}
Just use good implementation (e.g. in Python):
from math import log
def fibonacci_number(num):
if num > 1, a + ((b * c)
July 13th, 2007 at 5:11 pm
Awful! It ate my code… How can you talk about programming while having broken blog script?
I don’t think it’s worth competing what language will produce worse complicated tiny code.
Just tell me what is 100000th Fibonacci number.
When you’ll get old waiting for this:
p=0;c=1;100000.times{p p;c=p+p=c}
Just use good implementation (e.g. in Python):
from math import log
def fibonacci_number(num):
__if num < 2: return num
__num -= 1
__b, c, d, e = 1, 0, 0, 1
__for i in range(int(log(num)/log(2))):
____if num & 1:
______x = d * b
______d, e = x + d * c + e * b, x + e * c
____a = b * b
____num, b, c = num >> 1, a + ((b * c) << 1), a + c * c
__f = b + c
__return d * (b + f) + e * f
print fibonacci_number(10000)
And keep away from dangerous 1-line “smart” code.
Anyway, Ruby code is fun, respect Daniel!
July 13th, 2007 at 6:08 pm
>> Writing fibonacci_terms is left as an exercise for the reader.
July 13th, 2007 at 7:05 pm
In python (either in a file or interpretted [2 lines]):
x,y=0,1;
while y < 16000: print x; x,y=y,x+y
looks like 42 to me …
July 13th, 2007 at 7:20 pm
@Mike G. 0 *is* the first term in the sequence, see the Wikipedia article from the post.
July 14th, 2007 at 5:26 am
@3Monkeys
See! I’m not the only one who has math books saying 1,1,2,3,…
July 14th, 2007 at 6:30 am
http://www.masio.com.mx/2007/07/13/fibonacci-en-una-linea/es/
3Monkeys: I had to edit this post to get the JavaScript to appear.
Solutions in 53 and 52 characters
k=0;p=1;while(k<4182){document.write(k);t=p;p+=k;k=t}
p=1;for(k=0;k<4182;){document.write(k);t=p;p+=k;k=t}
July 14th, 2007 at 9:54 am
Ok, ate my code too (guess it didn’t like the less than sign?):
p,n=0,1
for i in range(20):print p;p,n=n,n+p
So different version - 44 chars of Python (the previous was 50)
July 14th, 2007 at 9:58 am
ack - didn’t see analyst’s version…
July 14th, 2007 at 12:53 pm
In one-line of a-lot of shell scripting languages, it can be done in 71 chars…
echo “0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181″
This would be the shortest “algorithm” if the challenge was to print the first 5 terms…
July 17th, 2007 at 10:57 am
I can do 25 characters from an earlier fibonacci golf I did.
dc -e1d[prdk+KdZ5\>x]dsxx
See http://www.perlmonks.com/?node_id=626425 for the discussion thread.
July 17th, 2007 at 11:01 am
Oh, you have to start with zero? I looked only at the command at the perlmonks discussion thread which starts from one, and assumed that it’s correct. Adapting my solution is an exercise to the reader (I think it will cost one more character).
July 17th, 2007 at 11:10 am
I can’t seem to do it easily with just one extra character in a hurry, only two, but I’m too lazy to experiment more, sorry.
July 17th, 2007 at 6:46 pm
28 source characters in forth (could be 26 if I made the name a single character)
: fib 1 0 20 0 ?DO dup . dup rot + LOOP ;
July 18th, 2007 at 10:06 am
Perl, 41B :
perl -l12e ‘$_=1;($_,$?)=($?,$_+$?),print while$_<4e3′
July 23rd, 2007 at 1:33 am
Believe it or not, Fortran 77 is fairly respectable on this. 41 characters, counting one byte for each end of line image
i=0
j=1
do1n=1,20
print*,i
k=i+j
i=j
1j=k
July 23rd, 2007 at 2:27 am
@Jim, I’m impressed by the terseness of the Fortran solution. No way COBOL could do that
August 17th, 2007 at 8:06 pm
I’m very rusty on my APL but:
APL:
+\iota 20
where “iota” is really one character, the “iota” character
August 18th, 2007 at 9:38 pm
OK, i got my APL wrong… apologies. that’s the cumulative sum, not fibonacci…
September 27th, 2007 at 3:51 pm
[...] OMG: Fibonacci series in one line of perl. [...]
September 30th, 2007 at 9:20 am
http://www.vidul.com/articles/2007/07/19/fibonacci-formula
#!/usr/bin/env ruby #21 chars
x=1;loop{p$.+=x=$.-x}
#!/usr/bin/env perl #27 chars
print$}+=$.=$}-$.||1while.1
December 4th, 2007 at 8:59 pm
[...] probably seen various folks talking about how fewer lines of code are better. Every language partisan wants to prove that their language is more expressive than [...]
December 20th, 2007 at 12:25 am
I thought the contest was for 1,1,2,3…and whipped up this:
perl -e ‘$a=1;$a+=$b,print$b=$a-$b,$/for(A..T)’
which at 38 chars I think is a winner in the perl, starting at F(1)=1 category…
unfortunately adapting it to 0,1,1… bumps it up 11 characters to 49 chars:
perl -e ‘print 0,$/;$a=1;$a+=$b,print$b=$a-$b,$/for(A..T)’
Of course I just now see that there is a perlmonks thread about this which probably kicks my tail…
March 9th, 2008 at 7:52 pm
print reduce (lambda x,y: (x[1],x[0]+x[1], x[2]+[x[1]]), xrange(10), (0,1,[]))[2]
python 1 liner… 74 chars
April 10th, 2008 at 3:07 am
[...] OMG: Fibonacci series in one line of perl. [...]
October 5th, 2008 at 7:46 am
I just blogged the following:
perl -le ‘print$2while s/(\d*):?(\d*)/($1+$2||1).”:$1″/e’ |head -10
Notice that it contains no explicit assignment operations nor any explicit initialisation. It also (unlike some of the others above, notably the 27 character implementation) contains both of the leading 1s in the sequence.
http://mark.aufflick.com/blog/2008/10/05/fibonacci-perl-golf
October 5th, 2008 at 9:38 am
Relaxing my no-explicit asssignment rule, I can get the solution down to 37 characters. It’s tough to fit into a one-liner though–since both quotes are used, shell escaping would be required:
$_=”$’:”.($’+$`||1),print$`while x./:/