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 14 2028
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.comwrote:
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(8)=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(18)=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(28)=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(8)=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(18)=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(28)=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(38)=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.comwrote:
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.
"jacob navia" <ja***@nospam.comwrote in message
news:fo**********@aioe.org...
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")
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") This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Peri |
last post by:
I'm trying to create Python parser/interpreter using ANTLR.
Reading grammar from language refference I found:
or_expr::= xor_expr | or_expr "|" xor_expr
For me it looks like infinite recursion....
|
by: da Vinci |
last post by:
Greetings.
I want to get everyone's opinion on the use of recursion.
We covered it in class tonight and I want a good solid answer from
people in the "know" on how well recursion is accepted...
|
by: Anon Email |
last post by:
Hi people,
I'm learning about header files in C++. The following is code from
Bartosz Milewski:
// Code
const int maxStack = 16;
class IStack
|
by: Lorenzo Villari |
last post by:
I've tried to transform this into a not recursive version but without
luck...
#include <stdio.h>
void countdown(int p)
{
int x;
|
by: MTD |
last post by:
Hello all,
I've been messing about for fun creating a trial division factorizing
function and I'm naturally interested in optimising it as much as
possible.
I've been told that iteration in...
|
by: Peter Thornqvist |
last post by:
Hi!
I have a directory and file search class that I would like to call in an
asynch manner. The class is implemented such that whenever a matching item
is found (directory, file, file content)...
|
by: proctor |
last post by:
hello,
i have a small function which mimics binary counting. it runs fine as
long as the input is not too long, but if i give it input longer than
8 characters it gives
RuntimeError: maximum...
|
by: Jeff Bigham |
last post by:
So, it appears that Javascript has a recursion limit of about 1000
levels on FF, maybe less/more on other browsers.
Should such deep recursion then generally be avoided in Javascript?...
|
by: Muzammil |
last post by:
int harmonic(int n) {
if (n=1) {
return 1;
}
else {
return harmonic(n-1)+1/n;
}
}
can any help me ??
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
| |