अजगर

Question

मैं (क) एक रेखीय दृष्टिकोण का उपयोग वें फिबोनैकी संख्या की गणना कर रहा हूँ में सूत्रों का उपयोग वें फिबोनैकी संख्या की गणना, और (ख) this अभिव्यक्ति

अजगर कोड:

'Different implementations for computing the n-th fibonacci number' 

def lfib(n): 
    'Find the n-th fibonacci number iteratively' 
    a, b = 0, 1 
    for i in range(n): 
     a, b = b, a + b 
    return a 

def efib(n): 
    'Compute the n-th fibonacci number using the formulae' 
    from math import sqrt, floor 
    x = (1 + sqrt(5))/2 
    return long(floor((x**n)/sqrt(5) + 0.5)) 


if __name__ == '__main__': 
    for i in range(60,80): 
    if lfib(i) != efib(i): 
     print i, "lfib:", lfib(i) 
     print " efib:", efib(i) 

एन> 71 के लिए मैं देखता हूं कि दो कार्य अलग-अलग मान लौटाते हैं।

क्या यह efib() में शामिल फ्लोटिंग पॉइंट अंकगणित के कारण है? यदि हां, तो क्या matrix form का उपयोग कर संख्या की गणना करने के लिए सलाह दी जाती है?

Answer 1

आप वास्तव में गोल त्रुटियों को देख रहे हैं।

मैट्रिक्स फॉर्म अधिक सटीक और बहुत तेज़ एल्गोरिदम है। Literateprograms.org एक अच्छा कार्यान्वयन को सूचीबद्ध करता है, लेकिन यह भी निम्नलिखित कलन विधि लुकास संख्या के आधार पर सूचीबद्ध करता है:

def powLF(n): 
    if n == 1:  return (1, 1) 
    L, F = powLF(n//2) 
    L, F = (L**2 + 5*F**2) >> 1, L*F 
    if n & 1: 
     return ((L + 5*F)>>1, (L + F) >>1) 
    else: 
     return (L, F) 

def fib(n): 
    if n & 1: 
     return powLF(n)[1] 
    else: 
     L, F = powLF(n // 2) 
     return L * F 

मैट्रिक्स दृष्टिकोण का एक अच्छा विश्लेषण के लिए Lecture 3 of the MIT Open Courseware course on algorithms पर एक नजर डालें।

उपर्युक्त एल्गोरिदम और मैट्रिक्स दृष्टिकोण दोनों में Θ (एलजी एन) जटिलता है, जैसा कि आपने उपयोग की जाने वाली मूर्खतापूर्ण स्क्वायरिव स्क्वायरिंग विधि की तरह है, फिर भी गोल करने वाली समस्याओं के बिना। लुकास संख्या दृष्टिकोण यह तेजी से एल्गोरिथ्म (जितनी जल्दी बारे में दो बार मैट्रिक्स दृष्टिकोण) बनाने, सबसे कम लगातार लागत है:

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000) 
0.40711593627929688 
>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000) 
0.20211100578308105 

Answer 2

चल बिन्दु efib में शामिल अंकगणित को यह कारण है()?

हाँ, यह है। efib के भीतर आप

>>> log(x**72)/log(2) 
49.98541778140445 

x86-64 हार्डवेयर पर

और Python floats have about 53 bits of precision है, तो आप किनारों के पास चला रहे हैं।

Answer 3

मैं एक बहुत ही सरल विशुद्ध रूप से अजगर कोड है ...

def fibonum(n): # Give the nth fibonacci number 
    x=[0,1] 
    for i in range(2,n): 
     x.append(x[i-2]+x[i-1]) 
    print(x[n-1])