NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

niceperl (8613)

niceperl
(email not shown publicly)

Journal of niceperl (8613)

Saturday September 13, 2008
04:53 AM

fibonacci numbers

[ #37432 ]
I wrote a small script in Perl to calc the N first terms of Fibonacci serie:

#-- fibo script

sub fibo {
return 1 if( \$_[0] < 2 ) ;
return fibo(\$_[0]-1) + fibo(\$_[0]-2);
}

for(\$i=0; \$i<=40; \$i++) {
\$f = fibo(\$i);
print "\$i : \$f\n";
}

#-- eof fibo.pl

I tried to calc the first 40 numbers, it tooks in my PC about 16 minutes. I weren't worried about writting a fast algoritm, just curious about the performance of a recursive call algorithm.

A friend of me, advertised me that the similar Java version code, ran fast, so I tried:

// Java fibonnaci class

class  fibo {

public static long calc(long x) {
if( x < 2 ) return 1;
return calc(x-1) + calc(x-2);
}

public static void main(String s[]) {
for(int i=0; i<=40; i++) {
System.out.println(i + " : " + calc(i));
}
}
}
// EOF Java fibonnaci class

----------------------------
The results (40 terms calc):
1) Perl: 16 minutes
2) Java: 16 seconds (!)

I'm sure that Java does some kind of optimization at the Virtual Machine.
I hope that Parrot team will be able to make a very fast virtual machine...
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Full
Abbreviated
Hidden
• Memoize(Score:1)

Computing the Fibonacci sequence is the canonical example for MJD's Memoize [cpan.org], which is a core module as of 5.8.
• Re:(Score:1)

I'm not looking for a cache model like memoize. I only want to focus on the time taken by each program (Java, Perl) with a similar original code. I think Java does some kind of memoize at low level, doesn't it?
• Re:(Score:1)

No. It just has fundamentally different execution model.

• Re:(Score:1)

Please, explain what you want to say
• Re:(Score:1)

Java will look for heavily used sections of code, aggressively optimize them, and rewrite in machine code. That is the reason for the performance difference.

• O(2^n)(Score:1)

It's also the classic example (it's in SICP) of how a bad algorithm choice can get really slow really fast.