«

"jacob navia" <> wrote in message
news:forvf7$6jn$...
> 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

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")

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")

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

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;
}

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")

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")