Home Posts Topics Members FAQ
=?ISO-8859-1?Q?S=E9bastien_de_Mapias?=
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
Feb 12 '08
Subscribe Reply
14 
2046 
- <
- 1
- 2
Army1987
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@army19 87-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(%ll d)=%lld\n",i,fi b(i));
}
}
army1987@army19 87-laptop:~$ gcc -std=c99 -O3 fib.c -o fib
army1987@army19 87-laptop:~$ time ./fib
fib(1)=1
fib(2)=1
[...]
fib(50)=1258626 9025
fib(51)=2036501 1074
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")
Feb 14 '08 #11
jacob navia
Army1987 wrote:
jacob navia wrote:
>I think no C compiler will go (using exactly the same program as givenarmy1987@army19 87-laptop:~$ cat fib.c
of course) beyond fib(50) in a reasonable amount of time.
[snip]
fib(51)=2036501 1074real 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
Feb 14 '08 #12
Spoon
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;
}
Feb 14 '08 #13
Army1987
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@army19 87-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@army19 87-laptop:~$ time ./fib.py
0 0
1 1
[...]
99 218922995834555 169026
100 354224848179261 915075
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")
Feb 14 '08 #14
Army1987
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")
Feb 14 '08 #15
- <
- 1
- 2
This thread has been closed and replies have been disabled. Please start a new discussion.
Similar topics
| 5 3412 recursion in grammar? 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. And so it says ANTLR. Maybe I don't understand EBNF notation. For me it should look like this. or_expr::= xor_expr | xor_expr "|" xor_expr and in ANTLR grammar file like this: Python |
| 12 2748 Question: How do you feel about 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 in modern day applications. Should we readily use it when we can or only when absolutly forced to use it? C / C++ |
| 9 4634 Abstract Data Types - Separating Interface from Implementation 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 C / C++ |
| 43 4138 Recursion elimination 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; C / C++ |
| 18 3712 Iteration over recursion? 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 python is generally more time-efficient than recursion. Is that true? Here is my algorithm as it stands. Any suggestions appreciated! Python |
| 2 1342 Help with thread implementation 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) an appropriate event is triggered. The application/class using it subscribes to the events (to update UI or log to file or whatever) and the event args include a Cancel parameter that they can set to true to abort the search. I have a couple of... C# / C Sharp |
| 24 2528 recursion depth problem 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 recursion depth exceeded in cmp i'm not too sure what i am doing improperly. is there really a lot of recursion in this code? Python |
| 30 8284 Javascript recursion limit 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? Surprisingly, deep recursion actually isn't that slow for what I'm doing. Programming this task recursively is so much more straightforward to me, but currently I'm forced to use an ugly hack to avoid going over the 1000 level limit. Of course, it could... Javascript |
| 35 4706 is it tail recursion 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 ?? C / C++ |
| 7988 Changing the language in Windows 10 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 effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,... Windows Server |
| 8468
Maximizing Business Potential: The Nexus of Website Design and Digital Marketing by: jinu1996 |last post by: In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is... Online Marketing |
| 8325
Discussion: How does Zigbee compare with other wireless protocols in smart home applications? by: tracyyun |last post by: Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some... General |
| 6808
AI Job Threat for Devs by: agi2029 |last post by: Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development projectplanning, coding, testing, and deploymentwithout human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea... Career Advice |
| 1 6004
Access Europe - Using VBA to create a class based on a table - Wed 1 May by: isladogs |last post by: The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will... Microsoft Access / VBA |
| 3954 Trying to create a lan-to-lan vpn between two differents networks by: TSSRALBI |last post by: Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls... Networking - Hardware / Configuration |
| 4016 Windows Forms - .Net 8.0 by: adsilva |last post by: A Windows Forms form does not have the event Unload, like VB6. What one acts like? Visual Basic .NET |
| 1 2467 transfer the data from one system to another through ip address by: 6302768590 |last post by: Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system C# / C Sharp |
| 1323
Comprehensive Guide to Website Development in Toronto: Expert Insights from BSMN Consultancy by: bsmnconsultancy |last post by: In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive... General |
By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.
To disable or enable advertisem*nts and analytics tracking please visit the page.
