मेरी जावा पावर विधि की क्षमता?

Question

तो मैं एक नौकरी के साक्षात्कार में चला गया और वे मुझसे पूछा एक सफेद बोर्ड पर एक त्वरित गणित शक्ति विधि लिखने के लिए और यह है कि क्या मैं डाल दिया है वहाँ

public static double pow(double base, double power) { 
    double result = 1.0; 
    for(double x = 0; x < power; x++) { 
     result = result * base; 
    } 

    return result; 
} 

यह काम किया है और वे इसे से संतुष्ट थे, लेकिन फिर मुझसे पूछने के लिए आगे बढ़े कि मैं इसे और अधिक कुशल कैसे बना सकता हूं और मुझे कोई प्रतिक्रिया नहीं मिली। तो मेरा सवाल यह है कि, क्या आप इससे अधिक कुशल हो सकते हैं या क्या मुझे थोड़ा पसीने के लिए सिर्फ एक प्रश्न था? मैं सोच रहा हूं कि कुछ प्रत्यक्ष बिट स्थानांतरण समाधान हो सकता है लेकिन मुझे बिल्कुल यकीन नहीं है, मुझे लगता है कि केवल 2 की शक्तियों के लिए लागू होगा? कोई विचार?

* संपादित खेद है कि मैं यह है कि विधि हस्ताक्षर मुझे दिया गया (इनपुट के रूप में डबल्स) और मुझे बताया गया था मैं किसी भी अंतर्निहित गणित पुस्तकालयों का उपयोग नहीं कर सकता है उल्लेख करना भूल गया।

Answer 1

http://en.wikipedia.org/wiki/Exponentiation_by_squaring इस ओ (एन) एल्गोरिदम के विपरीत, "मूल विधि" ओ (लॉग एन) है। (Guava में एक गैर-पुनरावर्ती कार्यान्वयन है।)

इसके अलावा, आपका पावर पैरामीटर लगभग निश्चित रूप से int होना चाहिए। (क्या तुम सच में गैर पूर्णांक शक्तियों को संख्या बढ़ाने के लिए एक एल्गोरिथ्म को लागू करने के चाहते हैं, आप एक बहुत अधिक गणित की जरूरत जा रहे हैं।)

Answer 2

को अपने ख़िलाफ़ जवाब गुणा और अन्य निर्धारित गुणकों अलग के साथ प्राप्त हो सकते हैं शक्तियां, जो आपको समाधान के करीब तेजी से ले जा सकती हैं। विकी लुई प्रदान करता है अच्छा है। यदि आप एक सामान्य व्याख्या चाहते हैं, तो विचार करें:

2^1 * 2^1 = 2^2 
2^2 * 2^2 = 2^4 
2^4 * 2^4 = 2^8 
... 

यह दो की शक्तियों के लिए बहुत अच्छा काम करता है। हालांकि मुझे दो की गैर शक्तियों के साथ खेलने के लिए मजेदार लगता है। तो अगर मैं 2^13 चाहता था तो मैं यह कैसे कर सकता हूं?

2^1 * 2^1 = 2^2 
2^1 * 2^2 = 2^3 
2^3 * 2^3 = 2^6 
2^6 * 2^6 = 2^12 
2^12 * 2^1 = 2^13 

उपर्युक्त उदाहरण यह दिखाने के लिए है कि आपको केवल वर्गों के साथ खेलना नहीं है। यदि आप विभिन्न शक्तियों के साथ कुछ के साथ खेलते हैं, तो आप पाएंगे कि आप कभी-कभी 2 की शक्तियों का उपयोग करने से बेहतर कर सकते हैं ... इसके साथ खेलने के लिए एक मजेदार गणित समस्या है।

Answer 3

बॉक्स के बाहर थोड़ा सोचकर, आमतौर पर स्मृति और गति के बीच एक व्यापारिक होता है। memoization की अवधारणा है।

आप एक स्थिर डबल [] [] कैश जोड़ सकते हैं जो किसी विशेष मूल्य के परिणाम को संग्रहीत करता है।

कुछ की तरह:

// look for the value in the cache, if it is there return it. 

for(double x = 0; x < power; x++) { 
    result = result * base; 
    // store result in the cache 
} 

यह काम करेगा, लेकिन स्मृति का एक बहुत का प्रयोग करेंगे।