java.math.BigInteger पाउ (एक्सपोनेंट) प्रश्न

Question

मैंने पाउ (एक्सपोनेंट) विधि पर कुछ परीक्षण किए। दुर्भाग्यवश, मेरे गणित कौशल निम्नलिखित समस्या को संभालने के लिए पर्याप्त मजबूत नहीं हैं।

BigInteger.valueOf(2).pow(var); 

परिणाम:: |

• वर

  मैं इस कोड का उपयोग कर रहा एमएस

• 2000000 में समय |
• 2500000 |
• 3000000 | 2237 9
• 3500000 | 32147
• 4000000 |
• 4500000 |
• 5000000 | 49 9 22

देखें? 2,500,000 एक्सपोनेंट की गणना लगभग 2,000,000 जितनी तेजी से की जाती है। 4,500,000 की गणना 4,000,000 से अधिक तेजी से की जाती है।

वह क्यों है?

आप कुछ मदद देने के लिए, यहाँ BigInteger.pow (प्रतिपादक) के मूल कार्यान्वयन है:

public BigInteger pow(int exponent) { 
    if (exponent < 0) 
     throw new ArithmeticException("Negative exponent"); 
    if (signum==0) 
     return (exponent==0 ? ONE : this); 

    // Perform exponentiation using repeated squaring trick 
     int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 
    int[] baseToPow2 = this.mag; 
     int[] result = {1}; 

    while (exponent != 0) { 
     if ((exponent & 1)==1) { 
     result = multiplyToLen(result, result.length, 
             baseToPow2, baseToPow2.length, null); 
     result = trustedStripLeadingZeroInts(result); 
     } 
     if ((exponent >>>= 1) != 0) { 
       baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 
     baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 
     } 
    } 
    return new BigInteger(result, newSign); 
    } 

Answer 1

एल्गोरिदम बार-बार स्क्वायरिंग (squareToLen) और गुणा (multiplyToLen) का उपयोग करता है।इन परिचालनों को चलाने के लिए समय शामिल संख्याओं के आकार पर निर्भर करता है। गणना के अंत के पास बड़ी संख्या में गुणा शुरू होने वालों की तुलना में अधिक महंगा है।

गुणा केवल तभी किया जाता है जब यह स्थिति सत्य हो: ((exponent & 1)==1)। स्क्वायर ऑपरेशंस की संख्या संख्या में बिट्स की संख्या (प्रमुख शून्य को छोड़कर) पर निर्भर करती है, लेकिन गुणा को केवल 1 बिट पर सेट करने के लिए जरूरी है। बाइनरी को देखकर आवश्यक संचालन देखना आसान है संख्या का प्रतिनिधित्व:

 
2000000: 0000111101000010010000000 
2500000: 0001001100010010110100000 
3000000: 0001011011100011011000000 
3500000: 0001101010110011111100000 
4000000: 0001111010000100100000000 
4500000: 0010001001010101000100000 
5000000: 0010011000100101101000000 

ध्यान दें कि 2.5M और 4.5M कि में भाग्यशाली वे कम उच्च बिट्स उन्हें आसपास संख्या से निर्धारित किया है कर रहे हैं। अगली बार ऐसा होता है 8.5M पर है:

 
8000000: 0011110100001001000000000 
8500000: 0100000011011001100100000 
9000000: 0100010010101010001000000 

स्वीट स्पॉट की 2.

 
1048575: 0001111111111111111111111 // 16408 ms 
1048576: 0010000000000000000000000 // 6209 ms 

Answer 2

बस एक अनुमान:

प्रतिपादक थोड़ा करके बिट नियंत्रित किया जाता है, और कम से कम अगर महत्वपूर्ण बिट 1 अतिरिक्त काम किया जाता है।

तो एल प्रतिपादक में बिट्स की संख्या और बिट्स जो कर रहे हैं 1 और t1 समय अतिरिक्त समय प्रसंस्करण आम हिस्सा और t2 कार्रवाई करने के लिए जब LSbit 1

है की एक संख्या है तो रन टाइम होगा

एल t1 + A t2

या समय द्विआधारी प्रतिनिधित्व में 1 की संख्या पर निर्भर है।

अब मेरा सिद्धांत सत्यापित करने के लिए एक छोटे से प्रोग्राम लिखने ...

Answer 3

मुझे यकीन है कि कितनी बार आप अपने समय दौड़े हैं नहीं कर रहा हूँ। जैसा कि कुछ टिप्पणीकारों ने इंगित किया है, आपको अच्छे नतीजों के लिए कई बार कई बार संचालन करने की आवश्यकता है (और वे अभी भी गलत हो सकते हैं)।

मान लीजिए कि आपने चीजों को अच्छी तरह से समय दिया है, याद रखें कि गणित में बहुत सारे शॉर्टकट हैं जिन्हें लिया जा सकता है। 5^6 की गणना करने के लिए आपको ऑपरेशन 5 * 5 * 5 * 5 * 5 * 5 करने की ज़रूरत नहीं है।

इसे और अधिक तेज़ी से करने का एक तरीका यहां है। http://en.wikipedia.org/wiki/Exponentiation_by_squaring