क्या असाइन किए गए लंबे लंबे ए और बी के लिए अतिप्रवाह के बिना (ए * बी) मॉड एम करने का कोई तरीका है?

Question

मैं विंडोज पर जीएमपी स्थापित करने का दुःस्वप्न नहीं चाहता हूं।

मेरे पास दो संख्या ए और बी, unsigned long long एस है, जो अधिकतम 10^10 या उससे अधिक के क्रम पर है, लेकिन ((A%M)*(B%M))%M करते समय भी, मुझे पूर्णांक ओवरफ़्लो मिलता है।

क्या बड़ी संख्या के लिए (A*B)%M की गणना के लिए होमब्री फ़ंक्शन हैं?

Answer 1

यदि मॉड्यूलस MULLONG_MAX से अधिक छोटा है (जो मामला 10^10 के क्षेत्र में है), तो आप इसे दो भागों में कारकों में से एक को विभाजित करके तीन चरणों में कर सकते हैं। मुझे लगता है कि A < M और B < M, और M < 2^42।

// split A into to parts 
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1); 
unsigned long long temp = (a1 * B) % M; // doesn't overflow under the assumptions 
temp = (temp << 21) % M;     // this neither 
temp += (a2*B) % M;      // nor this 
return temp % M; 

बड़े मान के लिए, आप तीन भागों में विभाजित कर सकते हैं कारक है, लेकिन अगर मापांक ULLONG_MAX को वास्तव में पास हो जाता है यह बदसूरत हो जाता है।