كيفية تحليل رقم النقطة العائمة يدويًا من سلسلة

Question

بالطبع تحتوي معظم اللغات على وظائف مكتبية لهذا الغرض، لكن لنفترض أنني أريد القيام بذلك بنفسي.

لنفترض أن التعويم مُعطى كما هو الحال في برنامج C أو Java (باستثناء اللاحقة 'f' أو 'd')، على سبيل المثال "4.2e1", ".42e2" أو ببساطة "42".بشكل عام، لدينا "الجزء الصحيح" قبل العلامة العشرية، و"الجزء الكسري" بعد العلامة العشرية، و"الأس".الثلاثة أعداد صحيحة.

من السهل العثور على الأرقام الفردية ومعالجتها، ولكن كيف يمكنك تركيبها في قيمة من النوع float أو double دون أن تفقد الدقة؟

أفكر في ضرب الجزء الصحيح بـ 10^ن, ، أين ن هو عدد الأرقام في الجزء الكسري، ثم إضافة الجزء الكسري إلى الجزء الصحيح والطرح ن من الأس.هذا يتحول بشكل فعال 4.2e1 داخل 42e0, ، على سبيل المثال.ثم يمكنني استخدام pow وظيفة لحساب 10 ^الأس وضرب النتيجة مع الجزء الصحيح الجديد.والسؤال هو: هل تضمن هذه الطريقة أقصى قدر من الدقة طوال الوقت؟

اي افكار في هذا؟

Answer 1

سأقوم بتجميع رقم النقطة العائمة مباشرة باستخدام تمثيله الثنائي.

اقرأ الحرف الأول تلو الآخر وابحث أولاً عن جميع الأرقام.افعل ذلك في حساب الأعداد الصحيحة.تتبع أيضًا العلامة العشرية والأس.هذا سيكون مهمًا لاحقًا.

الآن يمكنك تجميع رقم النقطة العائمة الخاص بك.أول شيء يجب فعله هو مسح التمثيل الصحيح للأرقام للمجموعة الأولى ذات بت واحد (من الأعلى إلى الأدنى).

البتات التي تلي البت الأول مباشرة هي الجزء العشري الخاص بك.

الحصول على الأس ليس بالأمر الصعب أيضًا.أنت تعرف موضع البت الأول وموضع العلامة العشرية والأس الاختياري من التدوين العلمي.اجمعها وأضف انحياز الأس الفاصلة العائمة (أعتقد أنها 127، لكن تحقق من بعض المراجع من فضلك).

يجب أن يكون هذا الأس في مكان ما في حدود 0 إلى 255.إذا كان أكبر أو أصغر لديك عدد لا نهائي موجب أو سالب (حالة خاصة).

قم بتخزين الأس كما هو في البتات من 24 إلى 30 من تعويمك.

الشيء الأكثر أهمية هو ببساطة العلامة.واحد يعني سلبي، صفر يعني إيجابي.

من الصعب وصفه أكثر مما هو عليه بالفعل، حاول تحليل رقم الفاصلة العائمة وألق نظرة على الأس والجزء العشري وسترى مدى سهولة الأمر حقًا.

راجع للشغل - يعد إجراء العمليات الحسابية في النقطة العائمة في حد ذاتها فكرة سيئة لأنك ستجبر دائمًا على اقتطاع الجزء العشري الخاص بك إلى 23 بتًا مهمًا.لن تحصل على تمثيل دقيق بهذه الطريقة.

Answer 2

جميع الإجابات الأخرى فاتتها كيف صعب هو القيام بذلك بشكل صحيح.يمكنك اتباع النهج الأول في هذا الأمر وهو دقيق إلى حد ما، ولكن حتى تأخذ في الاعتبار أوضاع التقريب IEEE (وآخرون)، فلن يكون لديك أبدًا يمين إجابة.لقد كتبت تطبيقات ساذجة من قبل مع قدر كبير من الخطأ.

إذا لم تكن خائفًا من الرياضيات، أنصحك بشدة بقراءة المقال التالي بقلم ديفيد جولدبرج، ما يجب أن يعرفه كل عالم كمبيوتر عن حساب النقطة العائمة.سوف تحصل على فهم أفضل لما يجري تحت الغطاء، ولماذا تم وضع الأجزاء على هذا النحو.

أفضل نصيحتي هي أن أبدأ بتنفيذ العمل، ثم انتقل من هناك.سوف تجد سريعًا أنك تفتقد الأشياء، ولكن القليل من النظرات إليها com.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 3

الخوارزمية "القياسية" لتحويل رقم عشري إلى أفضل تقريب للفاصلة العائمة هي خوارزمية William Clinger كيفية قراءة أرقام الفاصلة العائمة بدقة, ، للتحميل من هنا.لاحظ أن القيام بذلك بشكل صحيح يتطلب أعدادًا صحيحة متعددة الدقة، على الأقل نسبة معينة من الوقت، من أجل التعامل مع الحالات الزاوية.

تم العثور على خوارزميات للسير في الاتجاه الآخر، وطباعة أفضل رقم عشري من رقم عائم، في برجر وديبفيج طباعة أرقام الفاصلة العائمة بسرعة ودقة, ، قابل للتنزيل هنا.وهذا يتطلب أيضًا حسابًا صحيحًا متعدد الدقة

انظر أيضًا ديفيد إم جاي تقريب التحويلات الثنائية العشرية والتحويلات العشرية الثنائية بشكل صحيح للخوارزميات تسير في كلا الاتجاهين.

Answer 4

يمكنك تجاهل العلامة العشرية عند التحليل (باستثناء موقعها).لنفترض أن الإدخال كان:156.7834e10...يمكن تحليل ذلك بسهولة إلى العدد الصحيح 1567834 متبوعًا بـ e10، والذي يمكنك تعديله بعد ذلك إلى e6، نظرًا لأن العلامة العشرية كانت عبارة عن 4 أرقام من نهاية الجزء "الرقمي" من العدد العائم.

الدقة هي قضية.ستحتاج إلى التحقق من مواصفات IEEE للغة التي تستخدمها.إذا كان عدد البتات في الجزء العشري (أو الكسر) أكبر من عدد البتات في نوع Integer الخاص بك، فمن المحتمل أن تفقد الدقة عندما يكتب شخص ما رقمًا مثل:

5123.123123e0 - يتم التحويل إلى 5123123123 في طريقتنا، وهو ما لا يتناسب مع عدد صحيح، ولكن البتات الخاصة بالرقم 5.123123123 قد تتلاءم مع الجزء العشري من المواصفات العائمة.

بالطبع، يمكنك استخدام طريقة تأخذ كل رقم قبل العلامة العشرية، وتضرب الإجمالي الحالي (في عدد عشري) في 10، ثم تضيف الرقم الجديد.بالنسبة للأرقام بعد العلامة العشرية، اضرب الرقم بقوة متزايدة قدرها 10 قبل إضافته إلى الإجمالي الحالي.يبدو أن هذه الطريقة تطرح سؤالاً عن سبب قيامك بذلك على الإطلاق، لأنها تتطلب استخدام النقطة العائمة البدائية دون استخدام مكتبات التحليل المتوفرة بسهولة.

حظا سعيدا على أي حال!

Answer 5

نعم, ، يمكنك تحليل البناء إلى عمليات الفاصلة العائمة طالما هذه العمليات هي بالضبط, ، ويمكنك تحمل أ نهائي واحد غير دقيق عملية.

لسوء الحظ، عمليات النقطة العائمة قريباً تصبح غير دقيقة، عندما تتجاوز دقة الجزء العشري، يتم تقريب النتائج.بمجرد ظهور "خطأ" التقريب، سيتم تراكمه في عمليات أخرى...
لذلك، بشكل عام، لا, ، لا يمكنك استخدام مثل هذه الخوارزمية الساذجة لتحويل الكسور العشرية التعسفية، فقد يؤدي ذلك إلى رقم مقرب بشكل غير صحيح، يتم إيقافه بواسطة عدة ulp من الرقم الصحيح، كما أخبرك الآخرون بالفعل.

ولكن دعونا نرى إلى أي مدى يمكننا أن نذهب:

إذا قمت بإعادة بناء العوامة بعناية مثل هذا:

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

هناك خطر لتجاوز الدقة عند تجميع عدد صحيح Mantissa إذا كان يحتوي على العديد من الأرقام، وعند رفع 10 إلى قوة الأس المتحيز...

لحسن الحظ، إذا كانت العمليتان الأوليتان دقيقتين، فيمكنك إجراء عملية نهائية غير دقيقة * أو /، وذلك بفضل خصائص IEEE، وسيتم تقريب النتيجة بشكل صحيح.

دعونا نطبق هذا على العوامات ذات الدقة الفردية والتي تبلغ دقتها 24 بت.

10^8 > 2^24 > 10^7

مع ملاحظة أن مضاعف 2 لن يؤدي إلا إلى زيادة الأس وترك الجزء العشري دون تغيير، علينا فقط التعامل مع قوى 5 للأس 10:

5^11 > 2^24 > 5^10

على الرغم من ذلك، يمكنك تحمل 7 أرقام من الدقة في العدد الصحيح Mantissa والأس المتحيز بين -10 و10.

بدقة مضاعفة، 53 بت،

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

لذلك يمكنك تحمل 15 رقمًا عشريًا وأسًا متحيزًا بين -22 و22.

الأمر متروك لك لمعرفة ما إذا كانت أرقامك ستقع دائمًا في النطاق الصحيح...(إذا كنت صعبًا حقًا، فيمكنك الترتيب لموازنة الجزء العشري والأس عن طريق إدخال/إزالة الأصفار الزائدة).

خلاف ذلك، سيكون عليك استخدام بعض الدقة الموسعة.
إذا كانت لغتك توفر أعدادًا صحيحة دقيقة عشوائيًا، فسيكون من الصعب بعض الشيء فهمها بشكل صحيح، ولكن ليس بهذه الصعوبة، لقد فعلت ذلك في Smalltalk وقمت بالتدوين حول هذا الموضوع على http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html و http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

لاحظ أن هذه تطبيقات بسيطة وساذجة.لحسن الحظ، libc هو الأمثل.

Answer 6

فكرتي الأولى هي تحليل السلسلة إلى ملف int64 العشري و int الأس العشري باستخدام أول 18 رقمًا فقط من الجزء العشري.على سبيل المثال، سيتم تحليل 1.2345e-5 إلى 12345 و-9.ثم سأستمر في ضرب الجزء العشري بـ 10 وتقليل الأس حتى يصبح طول الجزء العشري 18 رقمًا (> 56 بت من الدقة).ثم سأبحث عن الأس العشري في الجدول للعثور على عامل وأُس ثنائي يمكن استخدامه لتحويل الرقم من النموذج العشري n*10^m إلى النموذج الثنائي p*2^q.سيكون العامل آخر int64 لذا سأضرب الجزء العشري به بحيث أحصل على أعلى 64 بت من الرقم 128 بت الناتج.هذا int64 يمكن صب الجزء العشري على عوامة مما يفقد الدقة اللازمة فقط ويمكن تطبيق الأس 2^q باستخدام الضرب دون فقدان الدقة.

أتوقع أن يكون هذا دقيقًا جدًا وسريعًا جدًا ولكنك قد ترغب أيضًا في التعامل مع الأرقام الخاصة NaN و-infinity و-0.0 وinfinity.لم أفكر في الأرقام غير الطبيعية أو أوضاع التقريب.

Answer 7

لذلك عليك أن تفهم معيار IEEE 754 من أجل التمثيل الثنائي المناسب.بعد ذلك يمكنك استخدام Float.intBitsToFloat أو Double.longBitsToDouble.

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

Answer 8

إذا كنت تريد الحصول على النتيجة الأكثر دقة قدر الإمكان، فيجب عليك استخدام دقة عمل داخلية أعلى، ثم تحويل النتيجة إلى الدقة المطلوبة.إذا كنت لا تمانع في حدوث بعض أخطاء ULP، فيمكنك فقط الضرب بشكل متكرر في 10 حسب الضرورة بالدقة المطلوبة.أود أن أتجنب الدالة pow()، لأنها ستنتج نتائج غير دقيقة للأسس الكبيرة.

Answer 9

ليس من الممكن تحويل أي سلسلة عشوائية تمثل رقمًا إلى رقم مزدوج أو عدد عشري دون فقدان الدقة.هناك العديد من الأعداد الكسرية التي يمكن تمثيلها بالضبط بالنظام العشري (على سبيل المثال:"0.1") التي لا يمكن تقريبها إلا في تعويم ثنائي أو مزدوج.وهذا مشابه لكيفية تمثيل الكسر 1/3 بالنظام العشري تمامًا، حيث يمكنك فقط كتابة 0.333333...

إذا كنت لا ترغب في استخدام وظيفة المكتبة مباشرة، فلماذا لا تنظر إلى الكود المصدري لوظائف المكتبة تلك؟لقد ذكرت جافا؛تأتي معظم JDKs مع الكود المصدري لمكتبات الفئات حتى تتمكن من البحث عن كيفية عمل طريقة java.lang.Double.parseDouble(String).بالطبع شيء مثل BigDecimal أفضل للتحكم في الدقة وأوضاع التقريب ولكنك قلت إنه يجب أن يكون عائمًا أو مزدوجًا.

Answer 10

باستخدام آلة الدولة.إنه أمر سهل إلى حد ما، ويعمل حتى في حالة انقطاع تدفق البيانات (عليك فقط الحفاظ على الحالة والنتيجة الجزئية).يمكنك أيضًا استخدام مولد المحلل اللغوي (إذا كنت تفعل شيئًا أكثر تعقيدًا).

Answer 11

وأنا أتفق مع المحطة.تعد آلة الحالة هي أفضل طريقة لإنجاز هذه المهمة نظرًا لوجود العديد من الطرق الغبية التي يمكن من خلالها كسر المحلل اللغوي.أنا أعمل على واحدة الآن، وأعتقد أنها كاملة، وأعتقد أنها تحتوي على 13 ولاية.

المشكلة ليست تافهة.

أنا مهندس أجهزة مهتم بتصميم أجهزة الفاصلة العائمة.أنا في التنفيذ الثاني.

لقد وجدت هذا اليوم http://speleotrove.com/decimal/decarith.pdf

والتي في الصفحة 18 تقدم بعض حالات الاختبار المثيرة للاهتمام.

نعم، لقد قرأت مقالة Clinger، لكن كوني مهندس أجهزة بسيط التفكير، لا أستطيع التفكير في الكود المقدم.كانت الإشارة إلى خوارزمية ستيل كما ورد في نص كنوث مفيدة بالنسبة لي.كل من المدخلات والمخرجات مشكلة.

جميع الإشارات المذكورة أعلاه لمختلف المقالات ممتازة.

لم أقم بالتسجيل هنا حتى الآن، ولكن عندما أفعل ذلك، بافتراض أن تسجيل الدخول لم يتم تسجيله، فسيكون ذلك أمرًا رائعًا.(أخي نقطة).

كلايد