Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Implementation of recursion in different languages: what happens inthe background ?

Reply
Thread Tools

Implementation of recursion in different languages: what happens inthe background ?

 
 
Bartc
Guest
Posts: n/a
 
      02-12-2008

"jacob navia" <(E-Mail Removed)> wrote in message
news:forvf7$6jn$(E-Mail Removed)...
> Sébastien de Mapias wrote:
>> Hello,
>> Hopefully I'm asking my question on the proper forum, but it's some
>> kind of low-level computer language issue and I guess here, many
>> people are likely to give me fine enlightenments (and I suppose -?-
>> that the interpreters I talk about below are coded in C)... I've found
>> on the page
>> http://antoniocangiano.com/2007/11/2...s-python-away/
>> a discussion about the performance differences between several
>> languages (Ruby, Perl, Python...) to execute the same operation,
>> using recursive function calls.
>>
>> Could someone explain me how such differences can be explained ?
>> Where does it come from ?
>>
>> Thanks a lot...
>> Regards,
>> Seb

>
> Python 2.5.1: 31.507s
> Ruby 1.9.0: 11.934s
>
> I just added "C"
>
> not even 1 second...
>
>
> #include <stdio.h>
> int fib(int n)
> {
> if (n < 2)
> return n;
> else
> return fib(n-1)+fib(n-2);
> }
>
> int main(void)
> {
> for(int i = 1; i<36;i++) {
> printf("fib(%d)=%d\n",i,fib(i));
> }
> }


That's not quite the same code as Ruby/Python, it should be more like:

#include <stdio.h>
int fib(int n)
{
if (n==0 || n==1) /* test this way */
return n;
else
return fib(n-1)+fib(n-2);
}

int main(void)
{
for(int i = 0; i<36;i++) { /* start from 0 */
printf("fib(%d)=%d\n",i,fib(i));
}
}

Your changes gave you an advantage of some 10%

For the record, my own timings were: Ruby(1.8.6) 90 secs, Python(2.5.1) 30
secs, C(lccwin) 0.52 seconds.

(And one of my own compiled C-like languages, 0.5 seconds, one of my own
interpreted languages, 10 secs. If new Ruby is really that fast then I may
have a bit of work to do to stay ahead)

--
Bart


 
Reply With Quote
 
 
 
 
Army1987
Guest
Posts: n/a
 
      02-13-2008
jacob navia wrote:

> I think no C compiler will go (using exactly the same program as given
> of course) beyond fib(50) in a reasonable amount of time.

army1987@army1987-laptop:~$ cat fib.c
#include <stdio.h>
long long fib(long long n)
{
if (n < 2)
return n;
else
return fib(n-1)+fib(n-2);
}

int main(void)
{
for(long long i = 1; i<52;i++) {
printf("fib(%lld)=%lld\n",i,fib(i));
}
}
army1987@army1987-laptop:~$ gcc -std=c99 -O3 fib.c -o fib
army1987@army1987-laptop:~$ time ./fib
fib(1)=1
fib(2)=1
[...]
fib(50)=12586269025
fib(51)=20365011074

real 19m4.878s
user 18m50.311s
sys 0m3.824s

(No, it's not reasonable...)
(BTW, what does it do when n < 0?)
--
Army1987 (Replace "NOSPAM" with "email")
 
Reply With Quote
 
 
 
 
Army1987
Guest
Posts: n/a
 
      02-14-2008
Kaz Kylheku wrote:

> You can do memoization and wider integers in C, but the program will
> be so ugly that the Fibonacci part of it won't even be recognizeable
> any longer, except for the name.

As for wider integers, maybe, but as for memoization, what's so ugly with:
#include <stdio.h>
#include <errno.h>
#include <limits.h>
#define MAX 47 /* assuming 32-bit long */

long int fib(int n)
{
static long int values[MAX] = { 0, 1 };
static int i = 1;
if (n < 0)
return (n % 2 ? -1 : 1) * fib(-n);
if (n >= MAX) {
errno = ERANGE;
return LONG_MAX;
}
while (i < n) {
i++;
values[i] = values[i - 1] + values[i - 2];
}
return values[n];
}

int main(void)
{
int i = 0;
while (1) {
long r = fib(i);
if (errno == ERANGE)
break;
printf("%2d %10ld\n", i, r);
i++;
}
return 0;
}

(And you can use a floating type instead of long int to have a wider
range, if you don't care about results becoming inexact for large n...)

--
Army1987 (Replace "NOSPAM" with "email")
 
Reply With Quote
 
jacob navia
Guest
Posts: n/a
 
      02-14-2008
Army1987 wrote:
> jacob navia wrote:
>
>> I think no C compiler will go (using exactly the same program as given
>> of course) beyond fib(50) in a reasonable amount of time.

> army1987@army1987-laptop:~$ cat fib.c


[snip]

> fib(51)=20365011074
>
> real 19m4.878s
> user 18m50.311s
> sys 0m3.824s
>
> (No, it's not reasonable...)
> (BTW, what does it do when n < 0?)


Off by one bug?



Try fib(55) when your computer has nothing else to do.

In any case, the non recursive function will do this
in MUCH less than a second.

When it is less than zero it returns its argument
unchanged...

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
 
Reply With Quote
 
Spoon
Guest
Posts: n/a
 
      02-14-2008
Army1987 wrote:

> (And you can use a floating type instead of long int to have a wider
> range, if you don't care about results becoming inexact for large n...)


I offer another fast (and not quite correct) implementation.

#include <stdint.h>
uint64_t fib(int n)
{
uint64_t temp, u = 0, v = 1;
while (--n) { temp = u + v; u = v; v = temp; }
return v;
}
 
Reply With Quote
 
Army1987
Guest
Posts: n/a
 
      02-14-2008
jacob navia wrote:

> Army1987 wrote:

[fibonacci function]
>> (BTW, what does it do when n < 0?)

>
> Off by one bug?

No. If you use a signed parameter for fib(), you ought to look up how
fibonacci(-n) is defined. Another possibility is to use an unsigned
parameter.
>
>
> Try fib(55) when your computer has nothing else to do.
>
> In any case, the non recursive function will do this in MUCH less than a
> second.

Indeed.

<OT>
army1987@army1987-laptop:~$ cat fib.py
#!/usr/bin/python
def fib(n):
a, b = 0, 1
for i in xrange(n):
a, b = b, a + b
return a

if __name__ == "__main__":
for i in xrange(101):
print i, fib(i)

army1987@army1987-laptop:~$ time ./fib.py
0 0
1 1
[...]
99 218922995834555169026
100 354224848179261915075

real 0m0.016s
user 0m0.016s
sys 0m0.000s
</OT>
I know there is an implementation which gives exact results without using
floating point with O(log n) time.
http://it.wikipedia.org/wiki/Success...A0_logaritmica
--
Army1987 (Replace "NOSPAM" with "email")
 
Reply With Quote
 
Army1987
Guest
Posts: n/a
 
      02-14-2008
Spoon wrote:

> Army1987 wrote:


> I offer another fast (and not quite correct) implementation.
>
> #include <stdint.h>
> uint64_t fib(int n)
> {
> uint64_t temp, u = 0, v = 1;
> while (--n) { temp = u + v; u = v; v = temp; }
> return v;
> }

It's not correct only when n <= 0.
(When fibonacci(n) is greater than the number of grains of wheat on that
chessboard, the result is not correct in Z, but it *is* correct in Z_{2^64}.)


--
Army1987 (Replace "NOSPAM" with "email")
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: What is the differences between tkinter in windows and Tkinter inthe other platform? Hidekazu IWAKI Python 0 12-15-2009 05:58 AM
How to write an XML schema that specifies an optional namespace inthe XML docs? Jethrie-JDuprez in the news XML 4 04-26-2009 08:35 PM
What happens when type conversion between signed and unsigned happens? NM C++ 6 09-20-2006 05:39 PM
MEDIA censorship and propaganda inthe US JA DVD Video 40 04-16-2005 12:45 AM
[OT] XP inthe palm of your hand Wayne McGlinn MCSE 2 12-16-2004 02:17 PM



Advertisments