सी प्रोग्रामिंग में फिक्स्ड प्वाइंट अंकगणित

Question

मैं एक ऐसा एप्लिकेशन बनाने की कोशिश कर रहा हूं जो स्टॉक की कीमतों को उच्च परिशुद्धता के साथ स्टोर करता है। वर्तमान में मैं ऐसा करने के लिए एक डबल का उपयोग कर रहा हूँ। स्मृति पर सहेजने के लिए क्या मैं किसी अन्य डेटा प्रकार का उपयोग कर सकता हूं? मुझे पता है कि इसमें निश्चित बिंदु अंकगणितीय के साथ कुछ करना है, लेकिन मैं इसे समझ नहीं सकता।

Answer 1

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

सी में ऐसा करने का सामान्य और सबसे प्रभावी तरीका बिट्स स्थानांतरण ऑपरेटरों (< < और >>) का उपयोग करके है।बिल्ट को स्थानांतरित करना एएलयू के लिए एक बहुत ही सरल और तेज़ ऑपरेशन है और ऐसा करने के लिए संपत्ति को गुणा करने के लिए (< <) और प्रत्येक शिफ्ट पर पूर्णांक मान को विभाजित करना (इसके अलावा) कई बदलावों को ठीक उसी के लिए किया जा सकता है एक ही कीमत की कीमत)। बेशक, दोष यह है कि गुणक 2 की शक्ति होना चाहिए (जो आमतौर पर स्वयं की समस्या नहीं है क्योंकि हम वास्तव में उस सटीक गुणक मूल्य की परवाह नहीं करते हैं)।

अब मान लें कि हम अपने मूल्यों को संग्रहीत करने के लिए 32 बिट्स पूर्णांक का उपयोग करना चाहते हैं। हमें 2 गुणक की शक्ति चुननी होगी। आइए केक को दो में विभाजित करें, इसलिए 65536 कहें (यह सबसे आम मामला है, लेकिन आप वास्तव में परिशुद्धता में अपनी आवश्यकताओं के आधार पर 2 की किसी भी शक्ति का उपयोग कर सकते हैं)। यह 2 है और 16 का मतलब है कि हम आंशिक भाग के लिए 16 कम से कम महत्वपूर्ण बिट्स (एलएसबी) का उपयोग करेंगे। बाकी (32 - 16 = 16) सबसे महत्वपूर्ण बिट्स (एमएसबी), पूर्णांक भाग के लिए है।

 integer (MSB) fraction (LSB) 
      v     v 
    0000000000000000.0000000000000000 

के कोड में डाल दो:

#define SHIFT_AMOUNT 16 // 2^16 = 65536 
#define SHIFT_MASK ((1 << SHIFT_AMOUNT) - 1) // 65535 (all LSB set, all MSB clear) 

int price = 500 << SHIFT_AMOUNT; 

यह मान आप की दुकान में डाल दिया जाना चाहिए (संरचना, डेटाबेस, जो कुछ भी) है। ध्यान दें कि int जरूरी नहीं है कि सी में 32 बिट्स हों, भले ही यह ज्यादातर आजकल मामला है। इसके अलावा आगे की घोषणा के बिना, यह डिफ़ॉल्ट रूप से हस्ताक्षरित है। आप सुनिश्चित करने के लिए घोषणा में हस्ताक्षर किए जोड़ सकते हैं। इससे बेहतर, आप uint32_t या uint_least32_t (stdint.h में घोषित) का उपयोग कर सकते हैं यदि आपका कोड अत्यधिक पूर्णांक बिट आकार पर निर्भर करता है (आप इसके बारे में कुछ हैक पेश कर सकते हैं)। संदेह में, अपने निश्चित-बिंदु प्रकार के लिए टाइपिफ़ का उपयोग करें और आप सुरक्षित हैं।

जब आप इस मूल्य पर कैलकुस करना चाहते हैं, तो आप 4 मूल ऑपरेटरों का उपयोग कर सकते हैं: +, -, * और /। आपको यह ध्यान रखना होगा कि जब मूल्य (+ और -) जोड़ना और घटाना, तो उस मान को भी स्थानांतरित किया जाना चाहिए। मान लीजिए कि हम अपने 500 मूल्य के लिए 10 जोड़ना चाहते हैं:

price += 10 << SHIFT_AMOUNT; 

लेकिन गुणा और भाग (* और /) के लिए, गुणक/भाजक नहीं स्थानांतरित कर दिया जाना चाहिए।

price *= 3; 

अब चीजों को और अधिक रोचक बना 4 द्वारा मूल्य विभाजित करके तो हम एक गैर शून्य आंशिक भाग के लिए बना:

price /= 4; // now our price is ((500 + 10) * 3)/4 = 382.5 

सब के बारे में है कि मान लीजिए कि हम 3 से गुणा करना चाहते हैं नियम। आप किसी भी समय वास्तविक कीमत की जानकारी हासिल करना चाहते हैं, तो आप सही-शिफ्ट करना होगा:

printf("price integer is %d\n", price >> SHIFT_AMOUNT); 

आप आंशिक भाग की जरूरत है, आप इसे बाहर मुखौटा चाहिए:

printf ("price fraction is %d\n", price & SHIFT_MASK); 

बेशक

, यह मान वह नहीं है जिसे हम दशमलव अंश कहते हैं, वास्तव में यह सीमा [0 - 65535] में एक पूर्णांक है। लेकिन यह दशमलव अंश सीमा [0 - 0.9 999 ...] के साथ बिल्कुल मैप करता है। दूसरे शब्दों में, मानचित्रण इस तरह दिखता है: 0 => 0, 32768 => 0.5, 65535 => 0.9999 ...

दशमलव भिन्न के रूप में यह देखने के लिए एक आसान तरीका है सी का सहारा लेना इस बिंदु पर निर्मित नाव गणित है:

printf("price fraction in decimal is %f\n", ((double)(price & SHIFT_MASK)/(1 << SHIFT_AMOUNT))); 

लेकिन आप एफपीयू समर्थन (हार्डवेयर या सॉफ्टवेयर) नहीं है, तो , तो आपको पूर्ण कीमत के लिए इस तरह अपने नए कौशल का उपयोग कर सकते हैं:

printf("price is roughly %d.%lld\n", price >> SHIFT_AMOUNT, (long long)(price & SHIFT_MASK) * 100000/(1 << SHIFT_AMOUNT)); 

अभिव्यक्ति में 0 की संख्या मोटे तौर पर आप चाहते हैं अंकों की संख्या दशमलव बिंदु के बाद है। अपने अंश परिशुद्धता को देखते हुए 0 की संख्या को अधिक महत्व न दें (यहां कोई असली जाल नहीं है, यह काफी स्पष्ट है)। आकार के रूप में लंबे समय तक उपयोग न करें (लंबा) आकार (int) के बराबर हो सकता है। लंबे समय तक का उपयोग करें यदि int 32 बिट्स लंबे लंबे को न्यूनतम 64 बिट्स (या int64_t, int_least64_t और ऐसे, stdint.h में घोषित किया गया है) का उपयोग किया जाता है। दूसरे शब्दों में, अपने निश्चित-बिंदु प्रकार के आकार से दो बार एक प्रकार का उपयोग करें, यह काफी उचित है। अंत में, यदि आपके पास> = 64 बिट प्रकारों तक पहुंच नहीं है, तो शायद कम से कम आपके आउटपुट के लिए उन्हें अनुकरण करने का समय हो सकता है।

ये निश्चित-बिंदु अंकगणित के पीछे मूलभूत विचार हैं।

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

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

अब वास्तविक चेतावनियों के लिए: यह तकनीक निश्चित रूप से उन क्षेत्रों में उपयुक्त नहीं है जहां परिशुद्धता सर्वोच्च प्राथमिकता (वित्तीय, विज्ञान, सैन्य ...) है। सामान्य फ़्लोटिंग पॉइंट (फ्लोट/डबल) अक्सर पर्याप्त सटीक नहीं होते हैं, भले ही उनके पास निश्चित-बिंदु समग्र से बेहतर गुण हों। फिक्स्ड-पॉइंट में वही परिशुद्धता है जो मूल्य (यह कुछ मामलों में एक लाभ हो सकता है), जहां सटीक फ्लोट सटीक मूल्य परिमाण के विपरीत आनुपातिक होता है (यानी कम परिमाण, जितना अधिक परिशुद्धता आपको मिलती है ... अच्छा, यह उससे अधिक जटिल है लेकिन आप बिंदु प्राप्त करते हैं)। इसके अलावा फ्लोट्स समकक्ष (बिट्स की संख्या में) पूर्णांक (निश्चित बिंदु या नहीं) की तुलना में अधिक मूल्य के साथ सटीकता के नुकसान की लागत के लिए बहुत अधिक परिमाण है (आप परिमाण के बिंदु तक भी पहुंच सकते हैं जहां 1 या यहां तक ​​कि जोड़ना अधिक मूल्यों का कोई असर नहीं होगा, ऐसा कुछ जो पूर्णांक के साथ नहीं हो सकता है)।

यदि आप उन समझदार क्षेत्रों में काम करते हैं, तो आप मनमाना परिशुद्धता के उद्देश्य से समर्पित पुस्तकालयों का उपयोग करना बेहतर कर सकते हैं (gmplib पर एक नज़र डालें), यह मुफ़्त है)। विज्ञान की गणना में, अनिवार्य रूप से, सटीकता प्राप्त करना आपके मूल्यों को संग्रहीत करने के लिए उपयोग की जाने वाली बिट्स की संख्या के बारे में है। आप उच्च परिशुद्धता चाहते हैं? बिट्स का प्रयोग करें। बस इतना ही।

Answer 2

मैं आपको ऐसा करने की सलाह नहीं दूंगा, अगर आपका एकमात्र उद्देश्य स्मृति को सहेजना है। कीमत की गणना में त्रुटि जमा की जा सकती है और आप इसे खत्म करने जा रहे हैं।

यदि आप वास्तव में समान सामान लागू करना चाहते हैं, तो क्या आप केवल कीमत का न्यूनतम अंतराल ले सकते हैं और फिर सीधे अपने नंबर में हेरफेर करने के लिए int और पूर्णांक ऑपरेशन का उपयोग कर सकते हैं? डिस्प्ले करते समय आपको केवल फ्लोटिंग पॉइंट नंबर में कनवर्ट करने की आवश्यकता होती है, जिससे आपका जीवन आसान हो जाता है।

Answer 3

मुझे आपके लिए दो विकल्प दिखाई देते हैं। यदि आप वित्तीय सेवा उद्योग में काम कर रहे हैं, तो शायद मानक हैं कि आपके कोड को सटीकता और सटीकता के लिए अनुपालन करना चाहिए, इसलिए स्मृति लागत के बावजूद आपको इसके साथ ही जाना होगा। मैं समझता हूं कि वह व्यवसाय आम तौर पर अच्छी तरह से वित्त पोषित होता है, इसलिए अधिक स्मृति के लिए भुगतान करना कोई समस्या नहीं होनी चाहिए। :)

यदि यह व्यक्तिगत उपयोग के लिए है, तो अधिकतम परिशुद्धता के लिए मैं अनुशंसा करता हूं कि आप पूर्णांक का उपयोग करें और भंडारण से पहले एक निश्चित कारक द्वारा सभी कीमतों को गुणा करें। उदाहरण के लिए, यदि आप पैनी के लिए चीजों को सटीक बनाना चाहते हैं (शायद पर्याप्त नहीं है), तो सभी कीमतों को 100 से गुणा करें ताकि आपकी इकाई प्रभावी रूप से डॉलर के बजाय सेंट हो और वहां से चले जाएं। यदि आप अधिक परिशुद्धता चाहते हैं, तो अधिक से गुणा करें। उदाहरण के लिए, एक सौ प्रतिशत के सटीक होने के लिए (एक मानक जो मैंने सुना है आम तौर पर लागू होता है), 10000 (100 * 100) तक कीमतों को गुणा करें।

अब 32-बिट पूर्णांक के साथ, 10000 से गुणा करके बड़ी संख्या में डॉलर के लिए छोटे कमरे छोड़ते हैं। 2 बिलियन की एक व्यावहारिक 32-बिट सीमा का मतलब है कि केवल $ 20000 जितनी अधिक कीमतें व्यक्त की जा सकती हैं: 2000000000/10000 = 20000. यदि आप 20000 से कुछ गुणा करते हैं तो यह बदतर हो जाता है, क्योंकि परिणाम रखने के लिए कोई जगह नहीं हो सकती है। इस कारण से, मैं 64-बिट पूर्णांक (long long) का उपयोग करने की अनुशंसा करता हूं। यहां तक ​​कि यदि आप 10000 तक सभी कीमतों को गुणा करते हैं, तो गुणाओं में भी बड़े मूल्य रखने के लिए अभी भी बहुत सारे हेडरूम हैं।

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

यदि यह सब जटिल लगता है, तो यह है। मुझे लगता है कि सबसे आसान विकल्प युगल का उपयोग करना है और यदि आपको इसकी आवश्यकता है तो अधिक रैम खरीदें। उनके पास सटीक 53 बिट्स हैं, जो लगभग 9 क्वाड्रिलियन हैं, या लगभग 16 दशमलव अंक हैं। हां, आप अरबों के साथ काम करते समय भी पैसा खो सकते हैं, लेकिन यदि आप इसके बारे में परवाह करते हैं, तो आप बिलकुल सही नहीं हो रहे हैं। :)