फास्ट गुणा मॉड्यूलो 2^16 + 1

Question

आईडीईए सिफर गुणा मॉड्यूल 2^16 + 1 का उपयोग करता है। क्या सामान्य ऑपरेशन के बिना इस ऑपरेशन को करने के लिए कोई एल्गोरिदम है (केवल मॉड्यूल 2^16 (छंटनी))? आईडीईए के संदर्भ में, शून्य को 2^16 के रूप में व्याख्या किया गया है (इसका मतलब है कि शून्य हमारे गुणा का तर्क नहीं है और यह परिणाम नहीं हो सकता है, इसलिए हम एक बिट को बचा सकते हैं और 2^16 को बिट पैटर्न 0000000000000000 के रूप में स्टोर कर सकते हैं)। मैं सोच रहा हूं कि मानक मॉड्यूलो ऑपरेटर का उपयोग किए बिना इसे कुशलतापूर्वक कार्यान्वित कैसे करें (या यह बिल्कुल संभव है)।

Answer 1

आप इस तथ्य का उपयोग कर सकते हैं कि (एन -1)% एन == -1।

इस प्रकार

, (65536 * क)% 65,537 == -एक% 65537.
इसके अलावा, -एक% 65,537 == -एक + 1 (आधुनिक 65536), जब 0 65536

uint16_t fastmod65537(uint16_t a, uint16_t b) 
{ 
    uint32_t c; 
    uint16_t hi, lo; 
    if (a == 0) 
     return -b + 1; 
    if (b == 0) 
     return -a + 1; 

    c = (uint32_t)a * (uint32_t)b; 
    hi = c >> 16; 
    lo = c; 
    if (lo > hi) 
     return lo-hi; 
    return lo-hi+1; 
} 

के रूप में व्याख्या की है

समस्या सिर्फ यहाँ अगर hi == lo, परिणाम 0. होगा सौभाग्य से टेस्ट स्वीट की पुष्टि करता है, कि यह वास्तव में नहीं किया जा सकता है ...

int main() 
{ 
    uint64_t a, b; 
    for (a = 1; a <= 65536; a++) 
     for (b = 1; b <= 65536; b++) 
     { 
      uint64_t c = a*b; 
      uint32_t d = (c % 65537) & 65535; 
      uint32_t e = m(a & 65535, b & 65535); 
      if (d != e) 
       printf("a * b % 65537 != m(%d, %d) real=%d m()=%d\n", 
         (uint32_t)a, (uint32_t)b, d, e); 
     } 
    } 

आउटपुट: कोई भी

Answer 2

सबसे पहले, मामला जहां a या b शून्य है। उस मामले में, यह मान 2^16 होने के रूप में व्याख्या की है, इसलिए प्राथमिक सापेक्ष अंकगणित हमें बताता है कि:

result = -a - b + 1; 

, क्योंकि 2^16 वर्ष की गुणक उलटा (आईडिया के संदर्भ में) अभी भी 2 है^16, और इसकी सबसे कम 16 बिट्स सभी शून्य हैं।

सामान्य स्थिति बहुत आसान की तुलना में यह लगता है, अब है कि हम "0" विशेष मामले का ध्यान रखा (2^16 + 1 0x10001 है):

/* This operation can overflow: */ 
unsigned result = (product & 0xFFFF) - (product >> 16); 
/* ..so account for cases of overflow: */ 
result -= result >> 16; 

यह एक साथ लाना:

/* All types must be sufficiently wide unsigned, e.g. uint32_t: */ 
unsigned long long product = a * b; 
if (product == 0) { 
    return -a - b + 1; 
} else { 
    result = (product & 0xFFFF) - (product >> 16); 
    result -= result >> 16; 
    return result & 0xFFFF; 
}