एल्गोरिथ्म C/C++: गणना करने के लिए सबसे तेजी से रास्ता (2^n) एक और घ 32 या 64 बिट पूर्णांकों

Question

साथ% d

मैं एक एल्गोरिथ्म है कि मुझे n और घ 32 या 64 के साथ गणना करने के लिए (2^n)%d की अनुमति देने के लिए तलाश कर रहा हूँ बिट्स पूर्णांक।

समस्या यह है कि 2^n को मल्टीप्रिजन लाइब्रेरीज़ के साथ स्मृति में संग्रहीत करना असंभव है, लेकिन शायद 3212 64 बिट्स पूर्णांक का उपयोग करके (2^n)%d की गणना करने के लिए एक चाल मौजूद है।

बहुत बहुत धन्यवाद।

Answer 1

Modular Exponentiation algorithm पर एक नज़र डालें।

विचार 2^n की गणना नहीं करना है। इसके बजाए, आप पावर अप करते समय मॉड्यूलस d कई बार कम करते हैं। That keeps the number small.

Exponentiation by Squaring के साथ विधि को संयोजित करें, और आप केवल O(log(n)) चरणों में (2^n)%d की गणना कर सकते हैं।

यहां एक छोटा उदाहरण है: 2^130 % 123 = 40

2^1 % 123 = 2 
2^2 % 123 = 2^2  % 123 = 4 
2^4 % 123 = 4^2  % 123 = 16 
2^8 % 123 = 16^2  % 123 = 10 
2^16 % 123 = 10^2  % 123 = 100 
2^32 % 123 = 100^2 % 123 = 37 
2^65 % 123 = 37^2 * 2 % 123 = 32 
2^130 % 123 = 32^2  % 123 = 40