स्ट्रिंग

Question

से फ़्लोटिंग पॉइंट नंबर मैन्युअल रूप से कैसे पार्स करें, बेशक अधिकांश भाषाओं में इसके लिए लाइब्रेरी फ़ंक्शन हैं, लेकिन मान लीजिए कि मैं इसे स्वयं करना चाहता हूं।

मान लीजिए कि नाव एक सी या जावा प्रोग्राम, उदाहरण के लिए "4.2e1" ('एफ' या 'प' प्रत्यय को छोड़ कर), ".42e2" या केवल "42" की तरह दिया जाता है। आम तौर पर, हमारे पास दशमलव बिंदु से पहले "पूर्णांक भाग" होता है, दशमलव बिंदु के बाद "आंशिक भाग" और "एक्सपोनेंट" होता है। सभी तीन पूर्णांक हैं।

व्यक्तिगत अंक ढूंढना और संसाधित करना आसान है, लेकिन आप उन्हें सटीक खोए बिना float या double के मूल्य में कैसे लिखते हैं?

मैं 10^n, जहां n आंशिक भाग में अंकों की संख्या है साथ पूर्णांक भाग गुणा, और फिर पूर्णांक भाग में आंशिक भाग को जोड़ने और घटाने के n की सोच रहा हूँ एक्सपोनेंट से। यह प्रभावी रूप से 4.2e142e0 में बदल जाता है, उदाहरण के लिए। तो मैं 1012 एक्सपोनेंट की गणना करने के लिए pow फ़ंक्शन का उपयोग कर सकता हूं और परिणाम को नए पूर्णांक भाग के साथ गुणा कर सकता हूं। सवाल यह है कि, क्या यह विधि पूरे परिशुद्धता की गारंटी देता है?

इस पर कोई विचार?

Answer 1

मैं सीधे अपने बाइनरी प्रतिनिधित्व का उपयोग कर फ्लोटिंग पॉइंट नंबर इकट्ठा करूंगा।

दूसरे के बाद नंबर एक वर्ण में पढ़ें और पहले सभी अंक खोजें। पूर्णांक अंकगणित में ऐसा करें। दशमलव बिंदु और एक्सपोनेंट का भी ट्रैक रखें। यह बाद में महत्वपूर्ण होगा।

अब आप अपने फ़्लोटिंग पॉइंट नंबर को इकट्ठा कर सकते हैं। पहली बात यह है कि पहले सेट एक-बिट (उच्चतम से निम्नतम) के लिए अंकों के पूर्णांक प्रतिनिधित्व को स्कैन करना है।

पहले एक-बिट के तुरंत बाद बिट्स आपकी मंटिसा हैं।

एक्सपोनेंट प्राप्त करना मुश्किल नहीं है। आप पहली एक-बिट स्थिति, दशमलव बिंदु की स्थिति और वैज्ञानिक नोटेशन से वैकल्पिक एक्सपोनेंट जानते हैं। उन्हें संयोजित करें और फ्लोटिंग पॉइंट एक्सपोनेंट पूर्वाग्रह जोड़ें (मुझे लगता है कि यह 127 है, लेकिन कृपया कुछ संदर्भ देखें)।

यह घाटा 0 से 255 की सीमा में कहीं होना चाहिए। यदि यह बड़ा या छोटा है तो आपके पास सकारात्मक या नकारात्मक अनंत संख्या (विशेष मामला) है।

एक्सपोनेंट को अपनी फ्लोट के 24 से 30 बिट्स में स्टोर करें।

सबसे महत्वपूर्ण बात बस संकेत है। एक नकारात्मक मतलब है, शून्य मतलब सकारात्मक है।

वास्तव में यह वर्णन करना कठिन है, फ्लोटिंग पॉइंट नंबर को विघटित करने का प्रयास करें और एक्सपोनेंट और मंटिसा को देखें और आप देखेंगे कि वास्तव में यह कितना आसान है।

बीटीडब्ल्यू - फ्लोटिंग पॉइंट में अंकगणित करना स्वयं एक बुरा विचार है क्योंकि आप हमेशा अपने मंटिसा को 23 महत्वपूर्ण बिट्स में फेंकने के लिए मजबूर करेंगे। आपको इस तरह का सटीक प्रतिनिधित्व नहीं मिलेगा।

Answer 2

एक राज्य मशीन का उपयोग करना। यह करना काफी आसान है, और डेटा स्ट्रीम बाधित होने पर भी काम करता है (आपको केवल राज्य और आंशिक परिणाम रखना होगा)। आप एक पार्सर जनरेटर का भी उपयोग कर सकते हैं (यदि आप कुछ और जटिल कर रहे हैं)।

Answer 3

इसके लिए आपको उचित बाइनरी प्रतिनिधित्व के लिए मानक आईईईई 754 को समझना होगा। इसके बाद आप फ़्लोट.intBitsToFloat या Double.longBitsToDouble का उपयोग कर सकते हैं।

http://en.wikipedia.org/wiki/IEEE_754

Answer 4

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

Answer 5

पार्सिंग करते समय आप दशमलव को अनदेखा कर सकते हैं (इसके स्थान को छोड़कर)। इनपुट कहें: 156.7834e10 ... इसे आसानी से पूर्णांक 1567834 में पार्स किया जा सकता है, इसके बाद ई 10, जिसे आप ई 6 में संशोधित करेंगे, क्योंकि दशमलव "अंकों" भाग के अंत से 4 अंक था नाव।

प्रेसिजन एक मुद्दा है। आपको जिस भाषा का उपयोग कर रहे हैं उसका आईईईई स्पेक जांचना होगा। यदि मंटिसा (या फ्रैक्शन) में बिट्स की संख्या आपके इंटीजर प्रकार में बिट्स की संख्या से बड़ी है, तो आप संभवतया सटीक खो देंगे जब कोई संख्या में टाइप करता है जैसे:

5123.123123e0 - 5123123123 में परिवर्तित हो जाता है हमारी विधि में, जो एक इंटीजर में फिट नहीं होता है, लेकिन 5.123123123 के लिए बिट्स फ्लोट स्पेस के मंटिसा में फिट हो सकते हैं।

बेशक, आप एक विधि का उपयोग कर सकते हैं जो दशमलव के सामने प्रत्येक अंक लेता है, वर्तमान कुल (फ्लोट में) 10 से गुणा करता है, फिर नया अंक जोड़ता है। दशमलव के बाद अंकों के लिए, वर्तमान कुल में जोड़ने से पहले 10 की बढ़ती शक्ति से अंकों को गुणा करें। यह विधि सवाल उठाने लगती है कि आप इसे क्यों कर रहे हैं, हालांकि, इसे आसानी से उपलब्ध पार्सिंग पुस्तकालयों का उपयोग किये बिना फ्लोटिंग पॉइंट आदिम के उपयोग की आवश्यकता होती है।

वैसे भी, शुभकामनाएं!

Answer 6

किसी भी मनमानी स्ट्रिंग को किसी संख्या का प्रतिनिधित्व करने के लिए एक डबल या फ्लोट में परिशुद्धता खोने के बिना परिवर्तित करना संभव नहीं है। कई आंशिक संख्याएं हैं जिन्हें दशमलव में सटीक रूप से प्रदर्शित किया जा सकता है (उदाहरण के लिए "0.1") जिसे केवल बाइनरी फ्लोट या डबल में अनुमानित किया जा सकता है। यह दशमलव के रूप में बिल्कुल 1/3 का प्रतिनिधित्व नहीं किया जा सकता है, आप केवल 0.333333 लिख सकते हैं ...

यदि आप लाइब्रेरी फ़ंक्शन का उपयोग नहीं करना चाहते हैं तो उन लोगों के लिए स्रोत कोड क्यों न देखें लाइब्रेरी फ़ंक्शन? आपने जावा का उल्लेख किया है; अधिकांश जेडीके कक्षा पुस्तकालयों के लिए स्रोत कोड के साथ शिप करते हैं ताकि आप देख सकें कि java.lang.Double.parseDouble (स्ट्रिंग) विधि कैसे काम करती है। निश्चित रूप से बिगडिसिल जैसे कुछ सटीक और गोल करने वाले मोड को नियंत्रित करने के लिए बेहतर है लेकिन आपने कहा कि इसे एक फ्लोट या डबल होना चाहिए।

Answer 7

:

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

यदि आप गणित से डरते नहीं हैं, तो मैं डेविड गोल्डबर्ग, What Every Computer Scientist Should Know About Floating-Point Arithmetic द्वारा निम्नलिखित लेख पढ़ने की अत्यधिक अनुशंसा करता हूं। हुड के नीचे क्या चल रहा है, इसके लिए आपको बेहतर समझ मिलेगी, और बिट्स इस तरह क्यों रखे गए हैं।

मेरी सबसे अच्छी सलाह एक कामकाजी atoi कार्यान्वयन के साथ शुरू करना है, और वहां से बाहर निकलना है। आप तेजी से पाएंगे कि आप चीजें खो रहे हैं, लेकिन कुछ strtod के स्रोत पर दिखते हैं और आप सही रास्ते पर होंगे (जो एक लंबा, लंबा रास्ता है)। आखिरकार आप प्रशंसा करेंगे में ड्रिटी डालें कि मानक पुस्तकालय हैं।

/* use this to start your atof implementation */ 

/* atoi - christopher.watford@gmail.com */ 
/* PUBLIC DOMAIN */ 
long atoi(const char *value) { 
    unsigned long ival = 0, c, n = 1, i = 0, oval; 
    for(; c = value[i]; ++i) /* chomp leading spaces */ 
    if(!isspace(c)) break; 
    if(c == '-' || c == '+') { /* chomp sign */ 
    n = (c != '-' ? n : -1); 
    i++; 
    } 
    while(c = value[i++]) { /* parse number */ 
    if(!isdigit(c)) return 0; 
    ival = (ival * 10) + (c - '0'); /* mult/accum */ 
    if((n > 0 && ival > LONG_MAX) 
    || (n < 0 && ival > (LONG_MAX + 1UL))) { 
     /* report overflow/underflow */ 
     errno = ERANGE; 
     return (n > 0 ? LONG_MAX : LONG_MIN); 
    } 
    } 
    return (n>0 ? (long)ival : -(long)ival); 
} 

Answer 8

सबसे अच्छा फ्लोटिंग प्वाइंट सन्निकटन किसी दशमलव संख्या को परिवर्तित करने के लिए "मानक" एल्गोरिथ्म विलियम क्लिंगर के How to read floating point numbers accurately, here से डाउनलोड है। ध्यान दें कि कोने के मामलों को संभालने के लिए, इसे सही तरीके से करने के लिए समय के कम से कम एक निश्चित प्रतिशत की आवश्यकता होती है।

दूसरी तरफ जाने के लिए एल्गोरिदम, फ़्लोटिंग-नंबर से सर्वोत्तम दशमलव संख्या प्रिंट करना, बर्गर और डाइबविग के Printing Floating-Point Numbers Quickly and Accurately, डाउनलोड करने योग्य here में पाए जाते हैं। इसके लिए कई-परिशुद्धता पूर्णांक अंकगणित

भी एल्गोरिदम दोनों तरीकों से चलने के लिए डेविड एम गे के Correctly Rounded Binary-Decimal and Decimal-Binary Conversions देखें।

Answer 9

मैं टर्मिनस से सहमत हूं। एक राज्य मशीन इस कार्य को पूरा करने का सबसे अच्छा तरीका है क्योंकि पार्सर को तोड़ने के कई बेवकूफ तरीके हैं। मैं अब एक पर काम कर रहा हूं, मुझे लगता है कि यह पूरा हो गया है और मुझे लगता है कि 13 राज्य हैं।

समस्या छोटी नहीं है।

मैं एक हार्डवेयर इंजीनियर हूं जो फ्लोटिंग पॉइंट हार्डवेयर डिजाइन करने में रूचि रखता है। मैं अपने दूसरे कार्यान्वयन पर हूं।

मैं आज http://speleotrove.com/decimal/decarith.pdf

जो पेज 18 पर कुछ दिलचस्प परीक्षण मामलों देता पाया।

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

विभिन्न लेखों के उपर्युक्त संदर्भ सभी उत्कृष्ट हैं।

मुझे अभी तक अभी तक साइन अप करना है, लेकिन जब मैं करता हूं, तो यह मानते हुए कि लॉगिन नहीं लिया जाता है, यह ब्रोश होगा। (Broh-डॉट)।

क्लाइड

Answer 10

मेरी पहली सोचा एक int64 अपूर्णांश में स्ट्रिंग और एक int दशमलव प्रतिपादक केवल पहले 18 अपूर्णांश के अंकों का उपयोग कर पार्स करने के लिए है। उदाहरण के लिए, 1.2345e-5 को 12345 और -9 में पार्स किया जाएगा। तब मैं मंटिसा को 10 से गुणा कर रहा था और जब तक मंथिसा 18 अंकों लंबा नहीं था (> परिशुद्धता के 56 बिट्स) तक एक्सपोनेंट में कमी आई थी। फिर मैं एक कारक में दशमलव एक्सपोनेंट को एक कारक और बाइनरी एक्सपोनेंट खोजने के लिए देखता हूं जिसका उपयोग दशमलव एन * 10^मीटर से बाइनरी पी * 2^क्यू फॉर्म में कनवर्ट करने के लिए किया जा सकता है। कारक एक और int64 होगा, इसलिए मैं इसके द्वारा मंटिसा को गुणा कर दूंगा जैसे कि मैंने परिणामी 128-बिट संख्या के शीर्ष 64-बिट प्राप्त किए।यह int64 मंटिसा को केवल आवश्यक परिशुद्धता खोने वाली फ्लोट पर डाला जा सकता है और 2^क्यू एक्सपोनेंट को गुणा का उपयोग करके परिशुद्धता के नुकसान के साथ लागू किया जा सकता है।

मैं उम्मीद करता हूं कि यह बहुत सटीक और बहुत तेज हो, लेकिन आप विशेष संख्या NaN, -infinity, -0.0 और अनंतता को भी संभालना चाहते हैं। मैंने denormalized संख्या या गोल मोड के बारे में सोचा नहीं है।

Answer 11

हाँ, आप चल बिन्दु आपरेशनों रूप में लंबे समय के रूप में इन आपरेशनों सटीक हैं में निर्माण विघटित कर सकते हैं, और आप एक एकल अंतिम अयथार्थ आपरेशन खर्च कर सकते हैं।

दुर्भाग्य से, चल बिन्दु आपरेशनों जल्द ही अयथार्थ हो जाते हैं, जब आप अपूर्णांश की शुद्धता से अधिक है, परिणाम गोल कर रहे हैं। एक बार गोल करने के बाद "त्रुटि" पेश की जाती है, इसे आगे के संचालन में संचयी किया जाएगा ...
तो, आमतौर पर, नहीं, आप मनमानी दशमलव को बदलने के लिए ऐसे बेवकूफ एल्गोरिदम का उपयोग नहीं कर सकते हैं, इससे गलत तरीके से गोल संख्या हो सकती है , सही के कई उलझन से दूर, जैसे कि दूसरों ने आपको पहले ही बताया है।

लेकिन चलो देखते हैं कि हम कितनी दूर जा सकते हैं:

आप ध्यान से इस तरह नाव को फिर से संगठित हैं:

if(biasedExponent >= 0) 
    return integerMantissa * (10^biasedExponent); 
else 
    return integerMantissa/(10^(-biasedExponent)); 

वहाँ परिशुद्धता पार करने के लिए एक खतरा है दोनों जब integerMantissa cumulating अगर यह है कई अंक, और biasedExponent की शक्ति के लिए 10 उठाते समय ...

सौभाग्य से, यदि पहले दो ऑपरेशन सटीक हैं, तो आप आईईईई संपत्तियों के लिए अंतिम अचूक ऑपरेशन * या/ies, परिणाम सही ढंग से गोल किया जाएगा।

चलो इसे एकल परिशुद्धता फ्लोट पर लागू करें जिसमें 24 बिट्स की सटीकता है।

10^8 > 2^24 > 10^7 

यह देखते हुए कि 2 के कई केवल प्रतिपादक बढ़ाने के लिए और अपूर्णांश अपरिवर्तित छोड़ देंगे, हम केवल 10 का घातांक के लिए 5 की शक्तियों से निपटने के लिए:

5^11 > 2^24 > 5^10 

हालांकि, आप 7 खर्च कर सकते हैं integerMantissa में सटीकता और -10 और 10

डबल परिशुद्धता, 53 बिट्स में जो biasedExponent की अंक,

10^16 > 2^53 > 10^15 
5^23 > 2^53 > 5^22 

,210

तो तुम 15 दशमलव अंक खर्च कर सकते हैं, और -22 और 22

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

अन्यथा, आपको कुछ विस्तारित परिशुद्धता का उपयोग करना होगा।
अपनी भाषा मनमाना परिशुद्धता पूर्णांकों प्रदान करता है, तो यह थोड़ा मुश्किल यह सही पाने के लिए है, लेकिन ऐसा नहीं है कि मुश्किल है, मैं स्मालटाक में ऐसा किया और http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html में यह के बारे में ब्लॉग और http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

ध्यान दें कि इन सरल और अनुभवहीन कार्यान्वयन हैं । सौभाग्य से, libc अधिक अनुकूलित है।