मुझे एक निश्चित-बिंदु गणित पुस्तकालय

Question

के लिए 64-बिट विशिष्ट विभाजन एल्गोरिदम पर एक तेज़ 96-बिट की आवश्यकता है, मैं वर्तमान में 32.32 निश्चित-बिंदु गणित लाइब्रेरी लिख रहा हूं। मैं जोड़ना, घटाव और गुणात्मक कार्य सही ढंग से करने में सफल रहा, लेकिन मैं विभाजन में काफी अटक गया हूं।

उन लोगों के लिए थोड़ा अनुस्मारक जो याद नहीं कर सकते: 32.32 फिक्स्ड-पॉइंट नंबर एक संख्या है जिसमें 32 बिट पूर्णांक भाग और आंशिक भाग के 32 बिट होते हैं।

सबसे अच्छा एल्गोरिदम मैं 96-बिट पूर्णांक विभाजन की आवश्यकता के साथ आया, जो कि कुछ कंपाइलर्स आमतौर पर अंतर्निहित नहीं होते हैं।

वैसे भी, यहाँ यह जाता है:

G = 2^32 

notation: x is the 64-bit fixed-point number, x1 is its low nibble and x2 is its high 

G*(a/b) = ((a1 + a2*G)/(b1 + b2*G))*G  // Decompose this 

G*(a/b) = (a1*G)/(b1*G + b2) + (a2*G*G)/(b1*G + b2) 

आप देख सकते हैं, (a2*G*G) नियमित 64-बिट पूर्णांक से बड़े होने की गारंटी है। uint128_t की वास्तव में मेरे संकलक द्वारा समर्थित थे, तो मैं बस निम्नलिखित करना होगा:

((uint128_t)x << 32)/y) 

खैर वे नहीं हैं और मैं एक समाधान की जरूरत है। आपके सहयोग के लिए धन्यवाद।

Answer 1

बेहतर स्वयं का समायोजन जवाब:
जवाब के सी # -ism माफ कर दो, लेकिन निम्न सभी मामलों में काम करना चाहिए। संभवतः एक समाधान संभव है जो सही बदलावों को तेज़ी से उपयोग करने के लिए पाता है, लेकिन मुझे अभी भी इतना गहराई से सोचना होगा।

int upshift = 32; 
ulong mask = 0xFFFFFFFF00000000; 
ulong mod = x % y; 
while ((mod & mask) != 0) 
{ 
    // Current upshift of the remainder would overflow... so adjust 
    y >>= 1; 
    mask <<= 1; 
    upshift--; 

    mod = x % y; 
} 
ulong div = ((x/y) << upshift) + (mod << upshift)/y; 

सरल लेकिन असुरक्षित जवाब:: यह यथोचित हालांकि कुशल होना चाहिए
इस गणना x % y शेष के upshift में एक अतिप्रवाह पैदा कर सकता है अगर यह शेष किसी भी बिट्स उच्च 32 बिट में सेट है , एक गलत जवाब का कारण बनता है।

((x/y) << 32) + ((x % y) << 32)/y 

पहला भाग पूर्णांक विभाजन का उपयोग करता है और आपको उत्तर के उच्च बिट्स देता है (उन्हें वापस स्थानांतरित करें)।

दूसरा भाग उच्च-बिट विभाजन के बाकी हिस्सों से कम बिट्स की गणना करता है (बिट जिसे आगे विभाजित नहीं किया जा सकता), स्थानांतरित हो गया और फिर विभाजित किया गया।

Answer 2

आप कम बिट्स के साथ विभाजन करने वाले कई हिस्सों में एक बड़ा विभाजन विघटित कर सकते हैं। जैसा कि एक अन्य पोस्टर ने पहले से ही एल्गोरिदम का उल्लेख किया है, वह नाउथ से टीएओसीपी में पाया जा सकता है।

हालांकि, पुस्तक खरीदने की कोई ज़रूरत नहीं है!

हैकर्स खुशी वेबसाइट पर एक कोड है जो सी में एल्गोरिदम लागू करता है। यह 64 बिट अंकगणित डिवीजनों को केवल 32 बिट अंकगणित का उपयोग करके लिखा जाता है, इसलिए आप कोड को सीधे चिपका नहीं सकते हैं। 64 से 128 बिट तक पहुंचने के लिए आपको दो प्रकार के सभी प्रकार, मास्क और कॉन्स्टेंस को विस्तृत करना होगा। एक छोटा सा int बन जाता है, 0xffff 0xffffffffll ect बन जाता है।

इस आसान आसान परिवर्तन के बाद आप 128 बिट डिवीजन करने में सक्षम होना चाहिए।

कोड यहां है: http://www.hackersdelight.org/HDcode/divlu.c (लाइन-एंडिंग के कारण वेब ब्राउज़र में बुरी तरह लपेट सकता है। यदि ऐसा है तो कोड को सहेजें और इसे नोटपैड के साथ खोलें)।

चूंकि आपके सबसे बड़े मूल्यों को केवल 96 बिट की आवश्यकता है, 64 बिट डिवीजनों में से एक हमेशा शून्य लौटाएगा, ताकि आप कोड को थोड़ा सा सरल बना सकें।

ओह - और इससे पहले कि मैं इसे भूल जाऊं: कोड केवल हस्ताक्षरित मानों के साथ काम करता है। अहस्ताक्षरित डिवाइड आप इस (छद्म कोड शैली) की तरह कुछ कर सकते हैं करने के लिए हस्ताक्षर किए से बदलने के लिए:

fixpoint Divide (fixpoint a, fixpoint b) 
{ 
    // check if the integers are of different sign: 
    fixpoint sign_difference = a^b; 

    // do unsigned division: 
    fixpoint x = unsigned_divide (abs(a), abs(b)); 

    // if the signs have been different: negate the result. 
    if (sign_difference < 0) 
    { 
    x = -x; 
    } 

    return x; 
} 

वेबसाइट ही साथ ही बाहर की जाँच के लायक है: http://www.hackersdelight.org/

आशा है कि यह मदद करता है।

बीटीडब्ल्यू - अच्छा काम जिस पर आप काम कर रहे हैं .. क्या आप हमें निश्चित बिंदु पुस्तकालय की आवश्यकता के लिए बता रहे हैं?

---

बीटीडब्ल्यू - विभाजन के लिए सामान्य शिफ्ट और घटाना एल्गोरिदम भी काम करेगा।

यदि आप x86 को लक्षित करते हैं तो आप इसे एमएमएक्स या एसएसई इंट्रिनिक्स का उपयोग करके कार्यान्वित कर सकते हैं। एल्गोरिदम केवल आदिम परिचालनों पर निर्भर करता है, इसलिए यह काफी तेजी से प्रदर्शन कर सकता है।

Answer 3

मुझे निल्स का जवाब पसंद है, जो शायद सबसे अच्छा है। यह सिर्फ लंबे विभाजन की तरह हम सभी ग्रेड स्कूल में सीखा है, को छोड़कर अंक आधार 2^32 के बजाय आधार हैं 10

हालांकि, अगर आप भी विभाजन के लिए न्यूटन के सन्निकटन विधि उपयोग करने पर विचार हो सकता है:

x := x (N + N - N * D * x) 

जहां एन संख्यात्मक है और डी राक्षसी है।

यह केवल गुणा और जोड़ों का उपयोग करता है, जो आपके पास पहले से है, और यह परिशुद्धता के लगभग 1 यूएलपी तक बहुत तेजी से अभिसरण करता है। दूसरी तरफ, आप सभी मामलों में सटीक 0.5-यूएलपी जवाब को स्वीकार नहीं कर पाएंगे।

किसी भी मामले में, मुश्किल बिट ओवरफ्लो का पता लगाने और संभालने का पता लगा रहा है।

Answer 4

त्वरित-गंदा।

ए/बी डबल परिशुद्धता फ्लोटिंग पॉइंट के साथ विभाजित करें। यह आपको सी ~ = ए/बी देता है। यह फ्लोटिंग पॉइंट परिशुद्धता और मंटिसा के 53 बिट्स के कारण केवल अनुमानित है।

आपके निश्चित बिंदु प्रणाली में एक प्रतिनिधित्व योग्य संख्या में सी को बंद करें।

अब गणना करें (फिर से अपने निश्चित बिंदु के साथ) डी = ए-सी * बी। ए

दोहराएं, अब फ्लोटिंग पॉइंट के साथ डी/बी की गणना करनी चाहिए। फिर, एक पूर्णांक के जवाब दौर। जैसे ही आप जाते हैं, प्रत्येक विभाजन परिणाम को एक साथ जोड़ें। जब आप अपना शेष इतना छोटा हो तो आप रुक सकते हैं कि आपका फ़्लोटिंग पॉइंट राउंडिंग के बाद 0 लौटाता है।

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

हां, आप न्यूटन पुनरावृत्ति यहां कर सकते हैं, लेकिन बाइनरी खोज संभवतः आसान हो जाएगी क्योंकि आपको केवल साधारण गुणों की आवश्यकता है और आपके मौजूदा 32.32 सटीक टूलकिट का उपयोग करके जोड़ना आवश्यक है।

यह सबसे कुशल विधि नहीं है, लेकिन यह कोड के लिए सबसे आसान है।