क्या एमओडी ऑपरेशन गुणा से अधिक CPU गहन है?

Question

MODmultiplication से factor of 2 से थोड़ा अधिक महंगा क्यों है? सीपीयू डिवीजन ऑपरेशन कैसे करता है और एमओडी ऑपरेशन के परिणाम के परिणाम के बारे में अधिक विशिष्टता प्राप्त करें।

निम्नलिखित उदाहरण में प्रत्येक थ्रेड प्रत्येक सेकेंड के लिए चलाया जाता है। परीक्षण SPARC प्रोसेसर पर किया गया था।

// multiplication 
void someThread() { 

    int a = 10234; 
    while (true) { 
     opers++; 
     a = a * a; 
     a++; 
    } 

    // opers ~ 26 * 10^6 in a sec. 
} 

// MOD 
void someThread() { 

    int a = 10234; 
    while (true) { 
     opers++; 
     a = a % 10000007; 
     a++; 
    } 

    // opers ~ 12 * 10^6 in a sec. 
} 

Answer 1

एल्गोरिदम विभाजन के लिए (प्रोसेसर विभाजन और फाटक में लागू एल्गोरिदम द्वारा गुणा निष्पादित) गुणन के लिए की तुलना में अधिक महंगा है। वास्तव में, विभाजन के लिए कुछ एल्गोरिदम जिनमें अच्छी जटिलता है, गुणा को मूलभूत चरण के रूप में उपयोग कर रहे हैं।

भले ही आप स्कूल में सीखे गए बेवकूफ एल्गोरिदम का उपयोग करें। दोनों में एक ही एसिम्प्टोटिक जटिलता है, लेकिन विभाजन के लिए निरंतर अधिक है (आपको अंक पता लगाना है और यह छोटा नहीं है, इसलिए आप गड़बड़ कर सकते हैं और गड़बड़ी को ठीक कर सकते हैं)।

Answer 2

एमओडी एक प्रभाग ऑपरेशन नहीं है, गुणात्मक संचालन नहीं है। गुणा गुणा से अधिक महंगा है।

एमओडी आपरेशन यहाँ बारे में अधिक जानकारी: http://en.wikipedia.org/wiki/Modulo_operation

Answer 3

हाँ, आधुनिक गुणा से ज्यादा महंगा है, क्योंकि यह प्रभाग के माध्यम से कार्यान्वित किया जाता है है। (सीपीयू आम तौर पर विभाजन पर शेष और शेष दोनों लौटते हैं।) लेकिन आपके दोनों धागे गुणा का उपयोग करते हैं। कॉपी/पेस्ट त्रुटि?

Answer 4

Instruction latencies and throughput for AMD and Intel x86 processors

एक आपरेशन सिर्फ सीपीयू :) पर स्वाभाविक धीमी है