Perl and Fib() - recursion is really bad?
User:
afbach
Date: 4/4/2012 11:28 am
Date: 4/4/2012 11:28 am
Views: 557
Rating: 0
Rating: 0
Reading an article on YAN language, Julia and they discuss Fibonacci
implementations in Julia
fib(n) = n < 2 ? n : fib(n - 1) + fib(n - 2)
and R
fib <- function(n)
{
ifelse(n < 2, n, fib(n - 1) + fib(n - 2))
}
"The Julia code takes around 8 milliseconds to complete, whereas the R
code takes around 4000 milliseconds."
though after some optimizations (ifelse appears to be a problem):
fib3 <- function(n) {
if (n < 2) return(n)
fib(n – 1) + fib(n – 2)
}
end up w/ R just 10 to 250 times slower than J. One commenter offers:
"I’m running the new R code against the Julia code for fib(250) and
seeing that R is running 7 threads and using 125mb of memory where
julia is using 3 threads and 68mb of memory on an old (2007 core duo)
iMac.
I’ll hold off on doing fib(250) in Perl; otherwise I wouldn’t get an
answer for a week."
Using a similar version (from:
http://www.scriptol.com/programming/fibonacci.php#perl
) I see:
time perl -e 'sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] -
2)}; print fibo(25), "\n"'
75025
real 0m0.118s
user 0m0.112s
sys 0m0.000s
though at fibo(100) I gave up after 2 minutes, though the iterative (op cit):
$ time perl -e 'sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
print fibo(250), "\n"'
7.89632582613173e+51
real 0m0.004s
user 0m0.000s
sys 0m0.004s
4ms regardless of number.
a
--
a
Andy Bach,
afbach@gmail.com
608 658-1890 cell
608 261-5738 wk
implementations in Julia
fib(n) = n < 2 ? n : fib(n - 1) + fib(n - 2)
and R
fib <- function(n)
{
ifelse(n < 2, n, fib(n - 1) + fib(n - 2))
}
"The Julia code takes around 8 milliseconds to complete, whereas the R
code takes around 4000 milliseconds."
though after some optimizations (ifelse appears to be a problem):
fib3 <- function(n) {
if (n < 2) return(n)
fib(n – 1) + fib(n – 2)
}
end up w/ R just 10 to 250 times slower than J. One commenter offers:
"I’m running the new R code against the Julia code for fib(250) and
seeing that R is running 7 threads and using 125mb of memory where
julia is using 3 threads and 68mb of memory on an old (2007 core duo)
iMac.
I’ll hold off on doing fib(250) in Perl; otherwise I wouldn’t get an
answer for a week."
Using a similar version (from:
http://www.scriptol.com/programming/fibonacci.php#perl
) I see:
time perl -e 'sub fibo;
sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] -
2)}; print fibo(25), "\n"'
75025
real 0m0.118s
user 0m0.112s
sys 0m0.000s
though at fibo(100) I gave up after 2 minutes, though the iterative (op cit):
$ time perl -e 'sub fibo
{
my ($n, $a, $b) = (shift, 0, 1);
($a, $b) = ($b, $a + $b) while $n-- > 0;
$a;
}
print fibo(250), "\n"'
7.89632582613173e+51
real 0m0.004s
user 0m0.000s
sys 0m0.004s
4ms regardless of number.
a
--
a
Andy Bach,
afbach@gmail.com
608 658-1890 cell
608 261-5738 wk
Re: Perl and Fib() - recursion is really bad?
User:
tmurray
Date: 4/4/2012 11:54 am
Date: 4/4/2012 11:54 am
Views: 0
Rating: 0
Rating: 0
If you do the recursion using "goto fib" (or somesuch, not really sure
about the syntax), it'll be tail recursive. Note that "goto BLOCK" is
different from the Considered Harmful form.
On 4/4/2012 11:28 AM, afbach@gmail.com wrote:
> afbach wrote:
>
> Reading an article on YAN language, Julia and they discuss Fibonacci
> implementations in Julia
> fib(n) = n < 2 ? n : fib(n - 1) + fib(n - 2)
>
> and R
> fib <- function(n)
> {
> ifelse(n < 2, n, fib(n - 1) + fib(n - 2))
> }
>
> "The Julia code takes around 8 milliseconds to complete, whereas the R
> code takes around 4000 milliseconds."
>
> though after some optimizations (ifelse appears to be a problem):
> fib3 <- function(n) {
> if (n < 2) return(n)
> fib(n – 1) + fib(n – 2)
> }
>
> end up w/ R just 10 to 250 times slower than J. One commenter offers:
> "I’m running the new R code against the Julia code for fib(250) and
> seeing that R is running 7 threads and using 125mb of memory where
> julia is using 3 threads and 68mb of memory on an old (2007 core duo)
> iMac.
>
> I’ll hold off on doing fib(250) in Perl; otherwise I wouldn’t get an
> answer for a week."
>
> Using a similar version (from:
> http://www.scriptol.com/programming/fibonacci.php#perl
>
> ) I see:
> time perl -e 'sub fibo;
> sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] -
> 2)}; print fibo(25), "\n"'
> 75025
>
> real 0m0.118s
> user 0m0.112s
> sys 0m0.000s
>
> though at fibo(100) I gave up after 2 minutes, though the iterative (op
> cit):
> $ time perl -e 'sub fibo
> {
> my ($n, $a, $b) = (shift, 0, 1);
> ($a, $b) = ($b, $a + $b) while $n-- > 0;
> $a;
> }
> print fibo(250), "\n"'
> 7.89632582613173e+51
>
> real 0m0.004s
> user 0m0.000s
> sys 0m0.004s
>
> 4ms regardless of number.
>
> a
>
>
>
>
>
>
> --
>
> a
>
> Andy Bach,
> afbach@gmail.com
> 608 658-1890 cell
> 608 261-5738 wk
>
> View Online
>
>
>
>
> Madison Area Perl Mongers - MadMongers
> http://www.madmongers.org
about the syntax), it'll be tail recursive. Note that "goto BLOCK" is
different from the Considered Harmful form.
On 4/4/2012 11:28 AM, afbach@gmail.com wrote:
> afbach wrote:
>
> Reading an article on YAN language, Julia and they discuss Fibonacci
> implementations in Julia
> fib(n) = n < 2 ? n : fib(n - 1) + fib(n - 2)
>
> and R
> fib <- function(n)
> {
> ifelse(n < 2, n, fib(n - 1) + fib(n - 2))
> }
>
> "The Julia code takes around 8 milliseconds to complete, whereas the R
> code takes around 4000 milliseconds."
>
> though after some optimizations (ifelse appears to be a problem):
> fib3 <- function(n) {
> if (n < 2) return(n)
> fib(n – 1) + fib(n – 2)
> }
>
> end up w/ R just 10 to 250 times slower than J. One commenter offers:
> "I’m running the new R code against the Julia code for fib(250) and
> seeing that R is running 7 threads and using 125mb of memory where
> julia is using 3 threads and 68mb of memory on an old (2007 core duo)
> iMac.
>
> I’ll hold off on doing fib(250) in Perl; otherwise I wouldn’t get an
> answer for a week."
>
> Using a similar version (from:
> http://www.scriptol.com/programming/fibonacci.php#perl
>
> ) I see:
> time perl -e 'sub fibo;
> sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] -
> 2)}; print fibo(25), "\n"'
> 75025
>
> real 0m0.118s
> user 0m0.112s
> sys 0m0.000s
>
> though at fibo(100) I gave up after 2 minutes, though the iterative (op
> cit):
> $ time perl -e 'sub fibo
> {
> my ($n, $a, $b) = (shift, 0, 1);
> ($a, $b) = ($b, $a + $b) while $n-- > 0;
> $a;
> }
> print fibo(250), "\n"'
> 7.89632582613173e+51
>
> real 0m0.004s
> user 0m0.000s
> sys 0m0.004s
>
> 4ms regardless of number.
>
> a
>
>
>
>
>
>
> --
>
> a
>
> Andy Bach,
> afbach@gmail.com
> 608 658-1890 cell
> 608 261-5738 wk
>
> View Online
>
>
>
>
> Madison Area Perl Mongers - MadMongers
> http://www.madmongers.org
Re: Perl and Fib() - recursion is really bad?
User:
afbach
Date: 4/4/2012 12:03 pm
Date: 4/4/2012 12:03 pm
Views: 115
Rating: 0
Rating: 0
On Wed, Apr 4, 2012 at 11:28 AM, wrote:
> though at fibo(100) I gave up after 2 minutes
Interesting was python's recursive was faster than Perl at 25
$ time python /tmp/fib.py 25
75025
real 0m0.082s
user 0m0.076s
sys 0m0.004s
but I gave up after 24 minutes on 50.
--
a
Andy Bach,
afbach@gmail.com
608 658-1890 cell
608 261-5738 wk
> though at fibo(100) I gave up after 2 minutes
Interesting was python's recursive was faster than Perl at 25
$ time python /tmp/fib.py 25
75025
real 0m0.082s
user 0m0.076s
sys 0m0.004s
but I gave up after 24 minutes on 50.
--
a
Andy Bach,
afbach@gmail.com
608 658-1890 cell
608 261-5738 wk
Re: Perl and Fib() - recursion is really bad?
User:
david-delikat
Date: 4/4/2012 6:08 pm
Date: 4/4/2012 6:08 pm
Views: 0
Rating: 0
Rating: 0
that for large starting parameters you calculate most of the
intermediate values 100's of times.
for each fib(n) there are two calls to fib required in order
to find the value. that happens all the way down to fib(2)
and fib(1)so for fib(10) the first call results in 2 calls, then 4,
8,16,32,…
if you want a reasonable fib function use some sort of
cache. then you will essentially get the same response as
the iterative version.
sub fib {
my $n = shift;
state @f;
return $n id $n < 2;
return $f[$n] ||= fib($n-1) + fib($n-2);
}
-dav { almost a math geek }
On Apr 4, 2012, at 12:03 PM, <afbach@gmail.com> wrote:
afbach wrote:
On Wed, Apr 4, 2012 at 11:28 AM, wrote:
> though at fibo(100) I gave up after 2 minutes
Interesting was python's recursive was faster than Perl at 25
$ time python /tmp/fib.py 25
75025
real 0m0.082s
user 0m0.076s
sys 0m0.004s
but I gave up after 24 minutes on 50.
--
a
Andy Bach,
afbach@gmail.com
608 658-1890 cell
608 261-5738 wk
Madison Area Perl Mongers - MadMongers
http://www.madmongers.org
Re: Perl and Fib() - recursion is really bad?
User:
tmurray
Date: 4/4/2012 6:55 pm
Date: 4/4/2012 6:55 pm
Views: 0
Rating: 0
Rating: 0
There are also logarithmic and constant time algorithms:
http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
That's not really the point, though. A recursive fib() is a
simple-stupid function to teach recursion and run some cross-language
benchmarks. Fibonacci numbers have few practical uses outside of that.
On 4/4/2012 6:08 PM, david-delikat@usa.net wrote:
> david-delikat wrote:
>
>
> the problem with calculating fibonacci with pure recursion is
> that for large starting parameters you calculate most of the
> intermediate values 100's of times.
>
> for each fib(n) there are two calls to fib required in order
> to find the value. that happens all the way down to fib(2)
> and fib(1)so for fib(10) the first call results in 2 calls, then 4,
> 8,16,32,…
>
> if you want a reasonable fib function use some sort of
> cache. then you will essentially get the same response as
> the iterative version.
>
> sub fib {
> my $n = shift;
> state @f;
> return $n id $n < 2;
> return $f[$n] ||= fib($n-1) + fib($n-2);
> }
>
> -dav { almost a math geek }
>
> On Apr 4, 2012, at 12:03 PM, > wrote:
>
>> afbach wrote:
>>
>> On Wed, Apr 4, 2012 at 11:28 AM, wrote:
>> > though at fibo(100) I gave up after 2 minutes
>>
>> Interesting was python's recursive was faster than Perl at 25
>> $ time python /tmp/fib.py 25
>> 75025
>>
>> real 0m0.082s
>> user 0m0.076s
>> sys 0m0.004s
>>
>> but I gave up after 24 minutes on 50.
>>
>> --
>>
>> a
>>
>> Andy Bach,
>> afbach@gmail.com
>> 608 658-1890 cell
>> 608 261-5738 wk
>>
>> View Online
>>
>>
>>
>>
>> Madison Area Perl Mongers - MadMongers
>> http://www.madmongers.org
>
> View Online
>
>
>
>
> Madison Area Perl Mongers - MadMongers
> http://www.madmongers.org
http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
That's not really the point, though. A recursive fib() is a
simple-stupid function to teach recursion and run some cross-language
benchmarks. Fibonacci numbers have few practical uses outside of that.
On 4/4/2012 6:08 PM, david-delikat@usa.net wrote:
> david-delikat wrote:
>
>
> the problem with calculating fibonacci with pure recursion is
> that for large starting parameters you calculate most of the
> intermediate values 100's of times.
>
> for each fib(n) there are two calls to fib required in order
> to find the value. that happens all the way down to fib(2)
> and fib(1)so for fib(10) the first call results in 2 calls, then 4,
> 8,16,32,…
>
> if you want a reasonable fib function use some sort of
> cache. then you will essentially get the same response as
> the iterative version.
>
> sub fib {
> my $n = shift;
> state @f;
> return $n id $n < 2;
> return $f[$n] ||= fib($n-1) + fib($n-2);
> }
>
> -dav { almost a math geek }
>
> On Apr 4, 2012, at 12:03 PM, > wrote:
>
>> afbach wrote:
>>
>> On Wed, Apr 4, 2012 at 11:28 AM, wrote:
>> > though at fibo(100) I gave up after 2 minutes
>>
>> Interesting was python's recursive was faster than Perl at 25
>> $ time python /tmp/fib.py 25
>> 75025
>>
>> real 0m0.082s
>> user 0m0.076s
>> sys 0m0.004s
>>
>> but I gave up after 24 minutes on 50.
>>
>> --
>>
>> a
>>
>> Andy Bach,
>> afbach@gmail.com
>> 608 658-1890 cell
>> 608 261-5738 wk
>>
>> View Online
>>
>>
>>
>>
>> Madison Area Perl Mongers - MadMongers
>> http://www.madmongers.org
>
> View Online
>
>
>
>
> Madison Area Perl Mongers - MadMongers
> http://www.madmongers.org
