«

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

Hello,
To my mind, it depends more about the compiler than the language.
But, because im new here, and a young student, my intepretation might
be wrong.



On 12 fév, 12:13, "Sébastien de Mapias" <sglrig...@gmail.com> 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 pagehttp://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-pyth...
> 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

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));
}
}
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(=21
fib(9)=34
fib(10)=55
fib(11)=89
fib(12)=144
fib(13)=233
fib(14)=377
fib(15)=610
fib(16)=987
fib(17)=1597
fib(1=2584
fib(19)=4181
fib(20)=6765
fib(21)=10946
fib(22)=17711
fib(23)=28657
fib(24)=46368
fib(25)=75025
fib(26)=121393
fib(27)=196418
fib(2=317811
fib(29)=514229
fib(30)=832040
fib(31)=1346269
fib(32)=2178309
fib(33)=3524578
fib(34)=5702887
fib(35)=9227465


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

jacob navia wrote:

> Python 2.5.1: 31.507s
> Ruby 1.9.0: 11.934s
>
> I just added "C"
>
> not even 1 second...

Since one expects a factor of between 10 and 100 for interpretive
implementations, that's hardly surprising. How does your implementation
perform for fib(100)?

--
"Well begun is half done." - Proverb

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

Chris Dollin wrote:
> jacob navia wrote:
>
>> Python 2.5.1: 31.507s
>> Ruby 1.9.0: 11.934s
>>
>> I just added "C"
>>
>> not even 1 second...
>
> Since one expects a factor of between 10 and 100 for interpretive
> implementations, that's hardly surprising. How does your implementation
> perform for fib(100)?
>

Using long long instead of int and the 64 bit lcc-win compiler
instead of the 32 bit lcc-win32 I obtain:
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(=21
fib(9)=34
fib(10)=55
fib(11)=89
fib(12)=144
fib(13)=233
fib(14)=377
fib(15)=610
fib(16)=987
fib(17)=1597
fib(1=2584
fib(19)=4181
fib(20)=6765
fib(21)=10946
fib(22)=17711
fib(23)=28657
fib(24)=46368
fib(25)=75025
fib(26)=121393
fib(27)=196418
fib(2=317811
fib(29)=514229
fib(30)=832040
fib(31)=1346269
fib(32)=2178309
fib(33)=3524578
fib(34)=5702887
fib(35)=9227465
fib(36)=14930352
fib(37)=24157817
fib(3=39088169
fib(39)=63245986
fib(40)=102334155
fib(41)=165580141
fib(42)=267914296
fib(43)=433494437
fib(44)=701408733
fib(45)=1134903170
fib(46)=1836311903
fib(47)=2971215073

TimeThis : Command Line : tfib
TimeThis : Start Time : Tue Feb 12 13:14:25 2008
TimeThis : End Time : Tue Feb 12 13:16:51 2008
TimeThis : Elapsed Time : 00:02:25.941

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.

fib(100) would take more than the age of the Universe...


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

Could you please tell me how you 'timed' your
execution ? Thanks.

jacob navia wrote:

> Chris Dollin wrote:
>> jacob navia wrote:
>>
>>> Python 2.5.1: 31.507s
>>> Ruby 1.9.0: 11.934s
>>>
>>> I just added "C"
>>>
>>> not even 1 second...
>>
>> Since one expects a factor of between 10 and 100 for interpretive
>> implementations, that's hardly surprising. How does your implementation
>> perform for fib(100)?
>>
>
> Using long long instead of int and the 64 bit lcc-win compiler
> instead of the 32 bit lcc-win32 I obtain:

Sorry, Jacob, I was confusing `fib` and `fact` and thinking of the
size of the numbers rather than the time taken. The fix for the
recursion time is easy.

I'd say that you were comparing apples and oranges, except that's
easy.

--
"Ashes are burning the way." - Renaissance, /Ashes Are Burning/

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

On Feb 12, 11:13*am, "Sébastien de Mapias" <sglrig...@gmail.com>
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 pagehttp://antoniocangiano.com/2007/11/28/holy-shmoly-ruby-19-smokes-pyth...
> 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 ?

I doubt that there is a simple answer to your
question. One would have to dig deep in the
internals of the interpreters/compilers of the
languages under question to see how they
implement function calls, arithmetic, etc.
and how that might affect performance. So a
group or mailing list for the developers of
interpreters/compilers of the languages would
be a better place.

The only general comment I can make is that
some languages optimize tail recursive calls
by turning them into loops. Scheme for example
is required to do that by its standard. I
don't know what the situation is with Ruby and
Python and it's not relevant to the Fibonacci
benchmark since the recursive call there is
not tail recursive.

Crossposting and setting follow-ups for
comp.programming where I think this is more
on topic.

On Feb 12, 4:19*am, jacob navia <ja...@nospam.com> 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.
>
> fib(100) would take more than the age of the Universe...

fib(100) cannot be done using that program because the answer is the
69 bit integer 354224848179261915075.

In a high level language, you can memoize your function with some
trivial spelling change.

In Python, simple memoization can be done with a custom function
decorator, which turns into a trivial blurb that you add in front of
the function definition.

In CLISP, with my own memoization macro:

[1]> (define-memoized-function fib (n) (if (< n 2) n (+ (fib (1- n))
(fib (- n 2)))))
[2]> (compile 'fib)
FIB ;
NIL ;
NIL
[3]> (time (fib 100))
Real time: 1.0E-6 sec.
Run time: 0.0 sec.
Space: 9944 Bytes
354224848179261915075

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.

Kaz Kylheku wrote:
> On Feb 12, 4:19 am, jacob navia <ja...@nospam.com> 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.
>>
>> fib(100) would take more than the age of the Universe...
>
> fib(100) cannot be done using that program because the answer is the
> 69 bit integer 354224848179261915075.
>
> In a high level language, you can memoize your function with some
> trivial spelling change.
>
> In Python, simple memoization can be done with a custom function
> decorator, which turns into a trivial blurb that you add in front of
> the function definition.
>
> In CLISP, with my own memoization macro:
>
> [1]> (define-memoized-function fib (n) (if (< n 2) n (+ (fib (1- n))
> (fib (- n 2)))))
> [2]> (compile 'fib)
> FIB ;
> NIL ;
> NIL
> [3]> (time (fib 100))
> Real time: 1.0E-6 sec.
> Run time: 0.0 sec.
> Space: 9944 Bytes
> 354224848179261915075
>
> 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.
>
>

In ONLY 0.05 seconds you can do it in lcc-win:

fib( 0)= 0
fib( 1)= 1
fib( 2)= 1
fib( 3)= 2
fib( 4)= 3
fib( 5)= 5
fib( 6)= 8
fib( 7)= 13
fib( = 21
fib( 9)= 34
fib( 10)= 55
fib( 11)= 89
fib( 12)= 144
fib( 13)= 233
fib( 14)= 377
fib( 15)= 610
fib( 16)= 987
fib( 17)= 1597
fib( 1= 2584
fib( 19)= 4181
fib( 20)= 6765
fib( 21)= 10946
fib( 22)= 17711
fib( 23)= 28657
fib( 24)= 46368
fib( 25)= 75025
fib( 26)= 121393
fib( 27)= 196418
fib( 2= 317811
fib( 29)= 514229
fib( 30)= 832040
fib( 31)= 1346269
fib( 32)= 2178309
fib( 33)= 3524578
fib( 34)= 5702887
fib( 35)= 9227465
fib( 36)= 14930352
fib( 37)= 24157817
fib( 3= 39088169
fib( 39)= 63245986
fib( 40)= 102334155
fib( 41)= 165580141
fib( 42)= 267914296
fib( 43)= 433494437
fib( 44)= 701408733
fib( 45)= 1134903170
fib( 46)= 1836311903
fib( 47)= 2971215073
fib( 4= 4807526976
fib( 49)= 7778742049
fib( 50)= 12586269025
fib( 51)= 20365011074
fib( 52)= 32951280099
fib( 53)= 53316291173
fib( 54)= 86267571272
fib( 55)= 139583862445
fib( 56)= 225851433717
fib( 57)= 365435296162
fib( 5= 591286729879
fib( 59)= 956722026041
fib( 60)= 1548008755920
fib( 61)= 2504730781961
fib( 62)= 4052739537881
fib( 63)= 6557470319842
fib( 64)= 10610209857723
fib( 65)= 17167680177565
fib( 66)= 27777890035288
fib( 67)= 44945570212853
fib( 6= 72723460248141
fib( 69)= 117669030460994
fib( 70)= 190392490709135
fib( 71)= 308061521170129
fib( 72)= 498454011879264
fib( 73)= 806515533049393
fib( 74)= 1304969544928657
fib( 75)= 2111485077978050
fib( 76)= 3416454622906707
fib( 77)= 5527939700884757
fib( 7= 8944394323791464
fib( 79)= 14472334024676221
fib( 80)= 23416728348467685
fib( 81)= 37889062373143906
fib( 82)= 61305790721611591
fib( 83)= 99194853094755497
fib( 84)= 160500643816367088
fib( 85)= 259695496911122585
fib( 86)= 420196140727489673
fib( 87)= 679891637638612258
fib( 8= 1100087778366101931
fib( 89)= 1779979416004714189
fib( 90)= 2880067194370816120
fib( 91)= 4660046610375530309
fib( 92)= 7540113804746346429
fib( 93)= 12200160415121876738
fib( 94)= 19740274219868223167
fib( 95)= 31940434634990099905
fib( 96)= 51680708854858323072
fib( 97)= 83621143489848422977
fib( 9= 135301852344706746049
fib( 99)= 218922995834555169026
fib(100)= 354224848179261915075
TimeThis : Command Line : tfib-bigq
TimeThis : Start Time : Tue Feb 12 22:14:56 2008


TimeThis : Command Line : tfib-bigq
TimeThis : Start Time : Tue Feb 12 22:14:56 2008
TimeThis : End Time : Tue Feb 12 22:14:56 2008
TimeThis : Elapsed Time : 00:00:00.054

Note that we arrive to the same result for fib(100).
That is somehow reassuring

Program:

#include <math.h>
#include <stdio.h>
#include <qfloat.h>
int main(void)
{
qfloat GoldenRatio = (1+sqrt(5.0Q))/2.0q;

for (int i=0; i<=100;i++) {
qfloat phiN = pow(GoldenRatio,(qfloat)i);
qfloat s = pow((1-GoldenRatio),(qfloat)i);
qfloat fib = (phiN-s)/sqrt(5.0q);

printf("fib(%3d)=%29.25qg\n",i,fib);
}
}



--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32