बड़ी संख्याओं का डिवीजन

मुझे कुछ डिवीजन एल्गोरिदम की आवश्यकता है जो बड़े पूर्णांक (128-बिट) को संभाल सकता है। मैंने पहले से ही पूछा है कि बिट स्थानांतरण ऑपरेटरों के माध्यम से इसे कैसे किया जाए। हालांकि, मेरे वर्तमान कार्यान्वयन के लिए एक बेहतर दृष्टिकोणबड़ी संख्याओं का डिवीजन

असल में, मैं प्रारूप

B < 2^64 साथ A * 2^64 + B में दो long long unsigned int के रूप में संख्या की दुकान के लिए पूछ रहा है।

यह संख्या 24 द्वारा विभाजित है और मैं इसे 24 द्वारा विभाजित करना चाहता हूं।

मेरे वर्तमान दृष्टिकोण इस गाड़ी है, यह की तरह

A * 2^64 + B  A    B 
-------------- = ---- * 2^64 + ---- 
     24   24   24 

      A    A mod 24     B   B mod 24 
= floor(----) * 2^64 + ---------- * 2^64 + floor(----) + ---------- 
      24    24.0      24   24.0

को बदलने के लिए हालांकि है।

(ध्यान दें कि मंजिल A/24 और modA % 24 है। सामान्य डिवीजनों long double में जमा हो जाती, पूर्णांकों long long unsigned int में संग्रहीत हैं।

24 के बाद से बाइनरी में 11000 के बराबर है, दूसरा योज्य नहीं करना चाहिए चौथे सारांश की सीमा में कुछ बदल दें क्योंकि इसे 64 बिट्स को बाईं ओर स्थानांतरित किया गया है।

तो, यदि A * 2^64 + B 24 तक विभाजित है, और बी नहीं है, तो यह आसानी से दिखाता है कि यह कुछ गैर-अभिन्न अंग लौटाता है संख्या

मेरे कार्यान्वयन में त्रुटि क्या है?

स्रोत

2009-11-27 Etan

बिट स्थानांतरण दृष्टिकोण के साथ समस्या क्या थी? –

ऐसा लगता है कि जब आप पहले से ही int64 के – Etan

128-बिट संख्याओं को चार 32-बिट के रूप में उपयोग करने का सबसे आसान तरीका यह है कि संख्या:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

और फिर 24 से लंबे विभाजन कार्य करें:

E = A/24 (with remainder Q) 
F = Q_B/24 (with remainder R) 
G = R_C/24 (with remainder S) 
H = S_D/24 (with remainder T)

कहाँ X_Y मतलब है X*2^32 + Y। फिर उत्तर E_F_G_H शेष T के साथ है। किसी भी समय आपको केवल 64-बिट संख्याओं के विभाजन की आवश्यकता होती है, इसलिए यह केवल पूर्णांक संचालन के साथ करने योग्य होना चाहिए।

स्रोत

2009-11-27 13:12:09 interjay

यह आपके एल्गोरिदम को बिल्कुल काम करने से नहीं रोकता है, लेकिन एफ, जी और एच प्रत्येक 2^32 से बड़े हो सकते हैं। मुझे इस तथ्य के साथ मेल खाना मुश्किल था कि 'E_F_G_H' नोटेशन concatenation की तरह दिखता है, लेकिन एक बार यह समझा जाता है, यह एक बहुत अच्छा एल्गोरिदम है। –

दरअसल, एफ, जी, और एच 2^32 से छोटे होंगे, क्योंकि क्यू, आर, और एस 24 से कम हैं। इसलिए E_F_G_H नोटेशन * है * concatenation। – interjay

सही! मैं अपने पेंसिल-एंड-पेपर डिवीजन को भूल गया ... मुझे याद आया कि एक अप्रिय अनुमान था लेकिन वह तब होता है जब विभाजक के पास बहुत अधिक अंक होते हैं। जब तक विभाजक स्वयं सीमा के भीतर गिरने के लिए पर्याप्त छोटा होता है जिसके लिए आदिम विभाजन काम करता है (जैसा मामला यहां है), पेंसिल-एंड-पेपर डिवीजन एल्गोरिदम लागू करते समय अनुमान लगाने की कोई आवश्यकता नहीं है। गलतफहमी के लिए खेद है। –

आपको अपने "सामान्य डिवीजन" के लिए long double का उपयोग नहीं करना चाहिए, बल्कि वहां पूर्णांक भी हैं। long double में सही उत्तर पाने के लिए पर्याप्त महत्वपूर्ण आंकड़े नहीं हैं (और फिर भी पूरा बिंदु पूर्णांक संचालन के साथ ऐसा करना है, सही?)।

स्रोत

2009-11-27 12:31:39

को विभाजित करने में सक्षम हैं, तो यह कुल मिलाकर लगता है कि यह 128 बिट int को 24 तक विभाजित करना है जिसके परिणामस्वरूप महाकाव्य इस समय विफल हो सकता है। लंबे डबल में 64 बिट मंटिसा है, इसलिए इससे कोई समस्या नहीं होनी चाहिए। या यह करता है? – Etan

एतान को ईर मूल प्रश्न से जुड़ा होना चाहिए था। ऐसा लगता है कि उद्देश्य पूर्णांक के साथ ऐसा नहीं करना है बल्कि इसे करने के लिए है। इसके अलावा, 'लम्बी डबल' 64-बिट डबल के रूप में छोटा हो सकता है, लेकिन यह भी बड़ा हो सकता है (10-बाइट विस्तारित डबल कहें, लेकिन वास्तव में कुछ भी ... वास्तव में ... आईईईई 754 ज्यादातर आकारों के संबंध में पैरामीट्रिक है)। इसलिए यह संभवतः आवश्यक परिशुद्धता हो सकता है (मैं यह नहीं कह रहा हूं कि 128-बिट पूर्णांक अंकगणितीय के रूप में आसान कुछ के लिए फ़्लोटिंग-पॉइंट कंप्यूटेशंस का उपयोग करना एक अच्छा विचार है)। –

लंबे समय तक इसे विभाजित कैसे करें? – Etan

24 24 बाइनरी में 11000 के बराबर है, दूसरे सारांश को चौथे सारांश की सीमा में कुछ नहीं बदला जाना चाहिए क्योंकि इसे 64 बिट्स बाईं ओर स्थानांतरित किया गया है।

आपका फॉर्मूला वास्तविक संख्या में लिखा गया है। (एक मॉड 24)/24 में मनमानी संख्याओं की संख्या हो सकती है (1/24 उदाहरण के लिए 0.041666666 ...) है और इसलिए आपके अपघटन में चौथे कार्यकाल में हस्तक्षेप कर सकता है, यहां तक कि एक बार 2^64 से गुणा हो सकता है।

संपत्ति जो वाई * 2^64 कम वजन बाइनरी अंकों में हस्तक्षेप नहीं करती है, केवल एक ही काम करता है जब वाई पूर्णांक होता है।

स्रोत

2009-11-27 12:32:32

यह दशमलव में हस्तक्षेप करता है क्योंकि आप उन्हें बिल्कुल नीचे नहीं लिख सकते हैं। बाइनरी में, यह एक बाध्य कार्यान्वयन है क्योंकि 1/24 अंकों की समाप्ति राशि में लिखा जा सकता है। – Etan

@ ईटन वास्तव में? बाइनरी में 1/24 का प्रतिनिधित्व करने के लिए कितने अंक लगते हैं? (यदि यह एक प्रश्न बहुत मुश्किल है, तो 1/3 बिल्कुल प्रतिनिधित्व करने के लिए बाइनरी अंकों की संख्या से शुरू करें) –

1/24 = बाइनरी 0.00001010101010101 ... अनुक्रम हमेशा के लिए चला जाता है। – dave4420

मत करो।

इस सामान को करने के लिए लाइब्रेरी को पकड़ें - अजीब त्रुटियों को डीबग करने पर आप अविश्वसनीय रूप से आभारी होंगे।

स्निपेट्स।संगठन के पास कुछ समय पहले इसकी साइट पर सी/सी ++ बिगइन्ट लाइब्रेरी थी, Google ने निम्न को भी चालू कर दिया: http://mattmccutchen.net/bigint/

स्रोत

2009-11-27 12:49:04

मुझे इसे मैन्युअल रूप से करना है क्योंकि यह एसीएम आईसीपीसी समस्या के लिए है। – Etan

क्या यह संभवतः व्यस्त गुणा के साथ हल किया जा सकता है? नोट करने के लिए पहली बात यह है कि 24 == 8 * 3 तो

a/24 == (a >> 3)/3

का परिणाम हैं x = (a >> 3) तो विभाजन का परिणाम 8 * (x/3) है। अब यह x/3 का मान ढूंढना बाकी है।

मॉड्यूलर अंकगणित राज्यों में कहा गया है कि n जैसे n * 3 == 1 (mod 2^128) मौजूद हैं। इस देता है:

x/3 = (x * n)/(n * 3) = x * n

यह लगातार n खोजने के लिए बनी हुई है। wikipedia पर इसे कैसे करें इस पर एक स्पष्टीकरण है। आपको 128 बिट संख्याओं में गुणा करने के लिए कार्यक्षमता को भी लागू करना होगा।

उम्मीद है कि इससे मदद मिलती है।

/ए.बी.

स्रोत

2009-11-27 13:45:46

उत्तर

संबंधित मुद्दे