मैं बहुत बड़ी संख्या जैसे n = 10^15 के लिए गणना करना चाहता हूं।

किसी भी तरह, मैं ओवरफ्लो एरर के कारण नहीं कर सकता।

xd = lambda n : ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/((2 ** (n+1)) * sqrt(17)))

N=1000 के लिए भी, इसकी गणना नहीं की जाएगी।

हालाँकि, मुझे यह उल्लेख करना चाहिए कि मुझे इसका मॉड्यूलर चाहिए (१०००००००००७)

समाधान क्या होगा?

4
Mikey Freeman 13 पद 2020, 12:31

3 जवाब

सबसे बढ़िया उत्तर

maths.stackexchange पर जवाब को देखते हुए ऐसा लगता है कि फ़ॉर्मूला कहां से आया है गणना करने के लिए सबसे आसान चीज ए (एन) है।

इसलिए, इसकी गणना पुनरावृत्ति द्वारा बहुत सरलता से की जा सकती है, और इस बार, जैसा कि हम केवल गुणा और जोड़ का उपयोग करते हैं, हम मॉड्यूलो अंकगणित के नियमों का लाभ उठा सकते हैं और संख्याओं को छोटा रख सकते हैं:

def s(n, mod):
    a1 = 1
    a2 = 3
    for k in range(n-1):
        a1, a2 = a2, (3*a2 + 2* a1) % mod
    return (a1 + a2) % mod


mod = 1000000007

print(s(10, mod))
# 363314, as with the other formulas...

print(s(10**6, mod))
# 982192189

%timeit s(10**6, mod)
# 310 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit s(10**7, mod)
# 3.39 s ± 93.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

हमें अन्य फ़ार्मुलों के समान परिणाम मिलते हैं, (जो वास्तव में अच्छी बात है...) चूंकि गणना के दौरान उपयोग की जाने वाली संख्या समान आकार रखती है, मॉड्यूलो के अधिकतम 5 गुना, गणना समय लगभग ओ (एन) है - s(10**7) s(10**6) की तुलना में केवल 10 गुना अधिक समय लेता है।

3
Thierry Lathuille 13 पद 2020, 15:44

केवल पूर्णांकों के साथ इसकी गणना करने का एक कार्य तरीका द्विपद विस्तार का उपयोग करके अपनी अभिव्यक्ति विकसित करना है। इसे थोड़ा सा पुनर्व्यवस्थित करने के बाद, हमें इसकी गणना करने का एक आसान तरीका मिलता है, सम और विषम शक्ति की शर्तों के लिए लगभग समान सूत्र के साथ:

def form(n, mod):
    cnk = 1
    total = 0
    for k in range(n+1):
        term = cnk * 3**k * 17**((n-k)//2)
        if (n-k) % 2 == 1:
            term *= 5
        total += term
        cnk *= (n-k)
        cnk //= (k+1)

        
    return (total // (2**n)) #% mod

परिणामों की जांच के लिए हम इसकी तुलना आपके मूल फॉर्मूले से कर सकते हैं:

from math import sqrt

def orig(n):
    return ((((5+ sqrt(17)) * ((3 + sqrt(17)) ** n)) - ((5-sqrt(17))* ((3 - sqrt(17)) ** n)))/((2 ** (n+1)) * sqrt(17)))

for n in range(20):
    print(n, orig(n), form(n, mod))

आउटपुट:

0 1.0000000000000002 1
1 4.0 4
2 14.000000000000002 14
3 50.0 50
4 178.0 178
5 634.0000000000001 634
6 2258.0 2258
7 8042.0 8042
8 28642.000000000004 28642
9 102010.00000000001 102010
10 363314.0 363314
11 1293962.0000000002 1293962
12 4608514.0 4608514
13 16413466.000000004 16413466
14 58457426.00000001 58457426
15 208199210.00000003 208199210
16 741512482.0000001 741512482
17 2640935866.000001 2640935866
18 9405832562.0 9405832562
19 33499369418.000004 33499369418

यह n (एक पुरानी मशीन पर परीक्षण) के बड़े मूल्यों के लिए "बल्कि" तेज़ है:

#%timeit form(1000, mod)
# 9.34 ms ± 87.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

#%timeit form(10000, mod)
# 3.79 s ± 14.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

#%timeit form(20000, mod)
# 23.6 s ± 37.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

अंतिम परीक्षण के लिए, मॉड्यूल लेने से पहले, हमारे पास 11033 अंकों की संख्या है।

इस दृष्टिकोण के साथ मुख्य समस्या यह है कि, जैसा कि हमें अंत में 2**n से विभाजित करना होता है, हम प्रत्येक चरण पर मोडुलो नहीं ले सकते हैं और संख्याओं को छोटा रख सकते हैं।

मैट्रिक्स गुणन के साथ सुझाए गए दृष्टिकोण का उपयोग करना (जब मैंने इस उत्तर के साथ शुरुआत की, तो मैंने रिकर्सन फॉर्मूला का लिंक नहीं देखा था, बहुत बुरा!) आपको ऐसा करने की अनुमति देगा, हालांकि।

1
Thierry Lathuille 13 पद 2020, 15:04

चूंकि n का मान बहुत अधिक है, पूर्णांक अतिप्रवाह स्पष्ट है।

मॉड्यूलर अंकगणित के लिए निम्नलिखित नियमों का पालन करें:

  1. जोड़: (a+b)%m = (a%m + b%m)%m
  2. घटाव: (a-b)%m = (a%m + b%m + m)%m
  3. गुणा: (a*b)%m = (a%m * b%m)%m
  4. घातांक: लूप का उपयोग करें।

उदाहरण: a^n के लिए, a = (a%m * a%m)%m, n कई बार उपयोग करें।

n के बड़े मानों के लिए, मॉड्यूलो की गणना करने के लिए पायथन के pow(x, e, m) फ़ंक्शन का उपयोग करें जिसमें बहुत कम समय लगता है।

1
rossum 13 पद 2020, 14:33