गुणा दो उमड़ती पूर्णांकों एक तिहाई

Question

को देखते हुए तीन पूर्णांकों, a, b और ca,b <= c < INT_MAX मैं गणना करने के लिए करता है, तो मान जो गलत परिणाम देता है, बहुत बड़ी हैं (a * b) % c लेकिन a * b अतिप्रवाह कर सकते हैं की जरूरत के साथ सापेक्ष।

क्या बिथैक्स के माध्यम से इसे सीधे गणना करने का कोई तरीका है, यानी एक प्रकार का उपयोग किए बिना प्रश्नों के मूल्यों के लिए अतिप्रवाह नहीं होगा?

Answer 1

करात्सुबा के एल्गोरिदम वास्तव में यहां जरूरी नहीं है। यह सिर्फ एक बार अपने ऑपरेटरों को विभाजित करने के लिए पर्याप्त है।

मान लें कि सादगी के लिए, कि आपकी संख्या 64-बिट हस्ताक्षरित पूर्णांक हैं। चलो = 2^32। तब

a=a1+k*a2 
b=b1+k*b2 
(a1+k*a2)*(b1+k*b2) % c = 
    a1*b1 % c + k*a1*b2 % c + k*a2*b1 % c + k*k*a2*b2 % c 

अब a1*b1 % c तुरंत गणना की जा सकती है, बाकी बारी-बारी से x <<= 1 और x %= c 32 या 64 बार (के बाद से (यू * v)% c = ((यू% ग) * v)% प्रदर्शन से परिकलित किया जा सकता सी)। c >= 2^63 पर यह स्पष्ट रूप से अतिप्रवाह हो सकता है। हालांकि, अच्छी बात यह है कि संचालन की इस जोड़ी को सचमुच नहीं किया जाना चाहिए। या तो x < c/2 और फिर आप केवल एक बदलाव की जरूरत है (और कोई अतिप्रवाह है), या x >= c/2 और

2*x % c = 2*x - c = x - (c-x). 

(और कोई अतिप्रवाह फिर से है)।

Answer 2

कई प्रमुख कंपाइलर 128-बिट पूर्णांक प्रकार प्रदान करते हैं, जिसके साथ आप बिना किसी प्रवाह के इस गणना कर सकते हैं।