गिना जा रहा है शक्तियों (जैसे 2^11) जल्दी से

Question

संभव डुप्लिकेट:
The most efficient way to implement an integer based power function pow(int, int)

मैं कैसे की गणना कर सकते बेहतर क्रम के साथ शक्तियों?

उदा। 2^13।

मैंने कहीं देखकर यह निम्नलिखित गणना के साथ क्या करना है कि कुछ याद रखें:

2^13 = 2^8 * 2^4 * 2^1

लेकिन मैं नहीं देख सकते हैं कि की गणना समीकरण के दाहिने तरफ के प्रत्येक घटक और फिर उन्हें गुणा करने से मेरी मदद मिलेगी।

कोई भी विचार?

संपादित करें: मेरा मतलब किसी भी आधार के साथ था। नीचे उल्लिखित एल्गोरिदम, विशेष रूप से "स्क्वायरिंग द्वारा एक्सपोनेंटेशन", रनटाइम/जटिलता में सुधार कैसे करते हैं?

Answer 1

इस के लिए एक सामान्यीकृत एल्गोरिथ्म है, लेकिन भाषाओं है कि थोड़ा-स्थानांतरण में, वहाँ की गणना करने के 2. की शक्तियों तुम बस 1 << exp में डाल (अपने बिट पारी ऑपरेटर मानते हुए एक बहुत तेजी से रास्ता है << है, क्योंकि यह सबसे में है ऑपरेशन का समर्थन करने वाली भाषाएं)।

मुझे लगता है कि आप सामान्यीकृत एल्गोरिदम की तलाश में हैं और उदाहरण के रूप में एक दुर्भाग्यपूर्ण आधार चुना है। मैं पाइथन में यह एल्गोरिदम दूंगा।

def intpow(base, exp): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base 
    elif (exp & 1) != 0: 
     return base * intpow(base * base, exp // 2) 
    else: 
     return intpow(base * base, exp // 2) 

यह मूलतः का कारण बनता है एक्स्पोनेंट्स log2 exp समय में गणना की जा करने में सक्षम हो। यह एक विभाजन है और एल्गोरिदम जीत। :-) जैसा कि किसी और ने कहा exponentiation by squaring।

आप इस में अपने उदाहरण प्लग, तो आप देख सकते हैं कि यह कैसे काम करता है और समीकरण आप देने के लिए संबंधित है:

दो की

intpow(2, 13) 
2 * intpow(4, 6) 
2 * intpow(16, 3) 
2 * 16 * intpow(256, 1) 
2 * 16 * 256 == 2^1 * 2^4 * 2^8 

Answer 2

शक्तियों आसान होते हैं। बाइनरी 2^13 में 13 शून्य के बाद एक है।

आप बिट स्थानांतरण का उपयोग करेंगे, जो कई भाषाओं में एक निर्मित ऑपरेटर है।

Answer 3

आप exponentiation by squaring का उपयोग कर सकते हैं। इसे "वर्ग-और-गुणा" के रूप में भी जाना जाता है और आधार के लिए काम करता है! = 2, भी।

Answer 4

आप तो दो की शक्तियों को अपने आप को सीमित नहीं हैं,:

कश्मीर^2n = (k^n)^2

Answer 5

उपयोग बिटवाइज़ स्थानांतरण। पूर्व। 1 < < 11 रिटर्न 2^11।

Answer 6

मुझे पता है कि सबसे तेज़ मुफ्त एल्गोरिदम Phillip S. Pang, Ph.D है और स्रोत कोड here पाया जा सकता है। यह तालिका-संचालित अपघटन का उपयोग करता है, जिसके द्वारा एक्सप() फ़ंक्शन बनाना संभव है, जो कि 2-10 गुना तेज है, फिर पेंटियम (आर) प्रोसेसर का मूल एक्सप() है।