कंप्यूटिंग (ए * बी) मॉड सी सी = 2^एन + -1

Question

32 बिट पूर्णांक गणित में, मूल और गणित के मूल गणित संचालन की गणना सामान्य रूप से 2^32 की गणना की जाती है, जिसका अर्थ है कि आपके परिणाम निम्नतम आदेश होंगे जोड़ने या गुणा करने के बिट्स।

यदि आप परिणाम को एक अलग मॉड्यूलस के साथ गणना करना चाहते हैं, तो आप निश्चित रूप से विभिन्न भाषाओं में किसी भी बड़ी कक्षाओं का उपयोग कर सकते हैं। और मानों के लिए ए, बी, सी < 2^32 आप 64 बिट लंबी स्याही में इंटरमीडिएट मानों की गणना कर सकते हैं और सही उत्तर

पर कम करने के लिए% ऑपरेटरों में निर्मित का उपयोग कर सकते हैं लेकिन मुझे बताया गया है कि विशेष चाल हैं एक * बी मोड सी की कुशलतापूर्वक कंप्यूटिंग के लिए जब सी फॉर्म (2^एन) -1 या (2^एन) +1 है, जो 64 बिट गणित या बिगइन्ट लाइब्रेरी का उपयोग नहीं करता है और काफी कुशल है एक मनमाना मॉड्यूलस मूल्यांकन, और यदि आप इंटरमीडिएट गुणा समेत थे तो आम तौर पर 32 बिट int को ओवरफ्लो करने वाले मामलों की उचित गणना करें।

दुर्भाग्य से, यह सुनकर कि इस तरह के विशेष मामलों में तेजी से मूल्यांकन विधि है, मुझे वास्तव में विधि का विवरण नहीं मिला है। "क्या वह नथ में नहीं है?" "क्या वह विकिपीडिया पर कहीं नहीं है?" क्या मैंने सुना है mumblings हैं।

यह यादृच्छिक संख्या जेनरेटर में एक आम तकनीक है जो * बी मॉड 2147483647 के गुणा कर रही है, क्योंकि 2147483647 2^31 -1 के बराबर एक प्रमुख संख्या है।

तो मैं विशेषज्ञों से पूछूंगा। यह चालाक विशेष मामला मल्टीप्ली-इन-मोड विधि क्या है जिसके बारे में मुझे कोई चर्चा नहीं मिल रही है?

Answer 1

मुझे लगता है कि चाल निम्नलिखित (मैं आधार 10 में यह करने के लिए जा रहा हूँ, क्योंकि यह आसान है, लेकिन सिद्धांत रूप धारण करना चाहिए)

मान लीजिए आप a*b mod 10000-1 गुणा कर रहे हैं, और

a = 1234 = 12 * 100 + 34 
b = 5432 = 54 * 100 + 32 

है

अब a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 = 648 * 10000 
34 * 54 * 100 = 1836 * 100 
12 * 32 * 100 = 384 * 100 
34 * 32   = 1088 

x * 10000 ≡ x (mod 10000-1) के बाद से [1], टी वह पहले और आखिरी शब्द 648 + 1088 बन गए। दूसरे और तीसरे नियम हैं जहां 'चाल' आती है।ध्यान दें कि:

1836 = 18 * 100 + 36 
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1). 

यह अनिवार्य रूप से एक परिपत्र शिफ्ट है। 648 + 3618 + 8403 + 1088 के परिणाम दे रहे हैं और यह भी ध्यान दें कि सभी मामलों में, गुणा संख्या < 10000 (< 100 और बी < 100 के बाद से), इसलिए यह गणना योग्य है यदि आप केवल एक साथ कई 2 अंकों की संख्या कर सकते हैं , और उन्हें जोड़ें।

बाइनरी में, यह समान रूप से काम करने जा रहा है।

ए और बी के साथ शुरू करें, दोनों 32 बिट हैं। मान लीजिए कि आप उन्हें मॉड 2^31 - 1 गुणा करना चाहते हैं, लेकिन आपके पास केवल 16 बिट गुणक (32 बिट्स देना) है।

a = 0x12345678 
b = 0xfedbca98 
accumulator = 0 
for (x = 0; x < 32; x += 16) 
    for (y = 0; y < 32; y += 16) 
     // do the multiplication, 16-bit * 16-bit = 32-bit 
     temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF) 

     // add the bits to the accumulator, shifting over the right amount 
     total_bits_shifted = x + y 
     for (bits = 0; bits < total_bits_shifted + 32; bits += 31) 
      accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF 

     // do modulus if it overflows 
     if (accumulator > 0x7FFFFFFFF) 
      accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF); 

यह देर हो चुकी है, इसलिए इस बात का संचायक हिस्सा शायद काम नहीं करेगा: एल्गोरिथ्म कुछ इस तरह होगा। मुझे लगता है कि सिद्धांत में यह सही है हालांकि। कोई इसे सही बनाने के लिए इसे संपादित करने के लिए स्वतंत्र महसूस करता है।

अनलॉक, यह बहुत तेज़ है, साथ ही, पीआरएनजी का उपयोग, मैं अनुमान लगा रहा हूं।

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

एक त्वरित खोज ने इसे चालू किया: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf। दुर्भाग्यवश, सरलीकृत फॉर्मूला में लिखने के लिए पर्याप्त समझदारी करने के लिए मेरे लिए बहुत देर हो चुकी है, लेकिन शायद यह उस पेपर में कहीं है।

Answer 3

मान लीजिए कि आप * बी को p*2^N+q के रूप में गणना कर सकते हैं। इसके लिए 64-बिट कंप्यूटेशंस की आवश्यकता हो सकती है, या आप 16-बिट भागों में ए और बी को विभाजित कर सकते हैं और 32-बिट्स पर गणना कर सकते हैं।

a*b mod 2^N-1 = p+q mod 2^N-12^N mod 2^N-1 = 1 के बाद से।

और a*b mod 2^N+1 = -p+q mod 2^N+12^N mod 2^N+1 = -1 के बाद से।

दोनों मामलों में, 2^N-1 या 2^N+1 द्वारा कोई विभाजन नहीं है।

Answer 4

प्रत्येक चरण में मॉड्यूलर कमी करने की बजाय, आप मॉड्यूलर गुणा गणना की लागत को कम करने के लिए Montgomery reduction (अन्य descriptions) का उपयोग कर सकते हैं। यह अभी भी एन के गुणों का उपयोग नहीं करता है, प्लस/शून्य से दो की शक्ति है।

Answer 5

पहचान आप देख रहे हैं x mod N = (x mod 2^q)- c*floor(x/2^q) है, (लेकिन आम तौर पर ± 1) यह देखते हुए कि N = 2^q + c और ग किसी भी पूर्णांक है। में "विशेष रूप से MODULI" "प्रधानमंत्री नंबर:: एक कम्प्यूटेशनल दृष्टिकोण" रिचर्ड Crandall और कार्ल पोमेरान्स द्वारा

आप खंड 9.2.3 से पढ़ सकते हैं। सिद्धांत के अलावा, इसमें उपरोक्त संबंध लागू करने वाले एल्गोरिदम के लिए छद्म कोड शामिल है।

Answer 6

मैं यह बहुत ही विषय पर एक rather extensive page पाया है, न सिर्फ एल्गोरिथ्म लेकिन फिर भी विशिष्ट इतिहास समस्या और समाधान और तरीकों लोगों समाधान का इस्तेमाल किया है की पर चर्चा।