मॉड्यूलो गुणा (सी में)

Question

विशेष रूप से: मेरे पास दो हस्ताक्षरित पूर्णांक (ए, बी) हैं और मैं गणना करना चाहता हूं (ए * बी)% UINT_MAX (UINT_MAX को अधिकतम हस्ताक्षरित int के रूप में परिभाषित किया गया है)। ऐसा करने का सबसे अच्छा तरीका क्या है?

पृष्ठभूमि: मुझे लिनक्स के लिए एक मॉड्यूल लिखने की आवश्यकता है जो एक ज्यामितीय अनुक्रम का अनुकरण करेगा, इससे पढ़ने से मुझे अगला तत्व (मॉड्यूलो UINT_MAX) मिलेगा, मुझे मिला एकमात्र समाधान वर्तमान तत्व को अपने आप में जोड़ना है, जोड़ते समय किया जाता है निम्नलिखित तर्क का प्रयोग:। (है कि मैं गणित अनुक्रम के लिए उपयोग)

for(int i=0; i<b; ++i){ 
    if(UINT_MAX - current_value > difference) { 
    current_value += difference; 
    } else { 
    current_value = difference - (UINT_MAX - current_value); 
    } 

जब current_value = पहले चरण में एक (और हर चरण में अद्यतन किया जाता है, और अंतर = एक (हमेशा) जाहिर है यह एक बुद्धिमान समाधान नहीं है। एक बुद्धिमान व्यक्ति यह कैसे प्राप्त करेगा?

धन्यवाद!

Answer 1

के रूप में उल्लेख किया गया है, यदि आप दो बार चौड़ाई उपलब्ध का एक प्रकार है, बस का उपयोग करें कि, यहाँ

(unsigned int)(((unsigned long long)a * b) % UINT_MAX) 

अगर int 32 बिट और long long 64 (या अधिक) है। यदि आपके पास कोई बड़ा प्रकार नहीं है, तो आप कारकों को आधे बिट-चौड़ाई पर विभाजित कर सकते हैं, भागों को गुणा और कम कर सकते हैं, अंत में इसे इकट्ठा कर सकते हैं। 32-बिट अहस्ताक्षरित यहाँ इलस्ट्रेटेड:

a_low = a & 0xFFFF; // low 16 bits of a 
a_high = a >> 16; // high 16 bits of a, shifted in low half 
b_low = b & 0xFFFF; 
b_high = b >> 16; 
/* 
* Now a = (a_high * 65536 + a_low), b = (b_high * 65536 + b_low) 
* Thus a*b = (a_high * b_high) * 65536 * 65536 
*   + (a_high * b_low + a_low * b_high) * 65536 
*   + a_low * b_low 
* 
* All products a_i * b_j are at most (65536 - 1) * (65536 - 1) = UINT_MAX - 2 * 65536 + 2 
* The high product reduces to 
* (a_high * b_high) * (UINT_MAX + 1) = (a_high * b_high) 
* The middle products are a bit trickier, but splitting again solves: 
* m1 = a_high * b_low; 
* m1_low = m1 & 0xFFFF; 
* m1_high = m1 >> 16; 
* Then m1 * 65536 = m1_high * (UINT_MAX + 1) + m1_low * 65536 = m1_high + m1_low * 65536 
* Similar for a_low * b_high 
* Finally, add the parts and take care of overflow 
*/ 
m1 = a_high * b_low; 
m2 = a_low * b_high; 
m1_low = m1 & 0xFFFF; 
m1_high = m1 >> 16; 
m2_low = m2 & 0xFFFF; 
m2_high = m2 >> 16; 
result = a_high * b_high; 
temp = result + ((m1_low << 16) | m1_high); 
if (temp < result) // overflow 
{ 
    result = temp+1; 
} 
else 
{ 
    result = temp; 
} 
if (result == UINT_MAX) 
{ 
    result = 0; 
} 
// I'm too lazy to type out the rest, you get the gist, I suppose. 

बेशक

, अगर तुम क्या जरूरत है वास्तव में, कमी सापेक्ष UINT_MAX + 1 है के रूप में @Toad मान लिया गया है, तो है कि बस क्या unsigned int के गुणन करता है।

Answer 2

संपादित करें: टिप्पणियों में बताया गया है ... यह उत्तर मॉड्यूलो MAX_INT + 1 पर लागू होता है, मैं इसे भविष्य के संदर्भ के लिए यहां खड़ा कर दूंगा।

ऐसा नहीं है कि तुलना में बहुत simpeler है:

सिर्फ दो अहस्ताक्षरित ints गुणा, परिणाम भी एक अहस्ताक्षरित int हो जाएगा। जो कुछ भी हस्ताक्षरित int में फिट नहीं हुआ वह मूल रूप से वहां नहीं है।

See example here

#include <stdio.h> 

void main() 
{ 
    unsigned int a,b; 
    a = 0x90000000; 
    b = 2; 

    unsigned int c = a*b; 

    printf("Answer is %X\r\n", c); 
} 

जवाब है:: तो कोई एक सापेक्ष आपरेशन करने की ज़रूरत 0x20000000 (इसलिए यह 0x120000000 किया जाना चाहिए था, लेकिन इस सवाल का जवाब काट दिया गया, सिर्फ तुम क्या सापेक्ष संचालन के साथ करना चाहता था)