Comment analyser manuellement un nombre à virgule flottante à partir d'une chaîne

Bien sûr, la plupart des langues ont des fonctions de la bibliothèque, mais supposons que je veux faire moi-même.

Supposons que le flotteur est donné comme en C ou Java programme (sauf pour le 'f' ou 'd' suffixe), par exemple "4.2e1", ".42e2" ou tout simplement "42". En général, nous avons la "partie entière" avant le point décimal, la "fraction" après la virgule, et le "exposant". Tous les trois sont des nombres entiers.

Il est facile de trouver et de traiter les chiffres individuels, mais comment composez-vous en une valeur de type float ou double sans perdre de précision?

Je suis en train de penser de la multiplication de la partie entière avec 10^n, où n est le nombre de chiffres dans la partie décimale, puis en ajoutant la partie fractionnaire de la partie entière et la soustraction n de l'exposant. Cela devient 4.2e1 en 42e0, par exemple. Ensuite, j'ai pu utiliser le pow fonction pour calculer 10^exposant et multiplier le résultat avec la nouvelle partie entière. La question est, est ce que cette méthode garantit un maximum de précision tout au long de?

Des idées sur ce point?

InformationsquelleAutor Thomas | 2008-09-17
  1. 11

    Je voudrais directement assembler le nombre à virgule flottante à l'aide de sa représentation binaire.

    Lire dans le numéro un caractère après l'autre, et d'abord trouver tous les chiffres. Faire de l'arithmétique des nombres entiers. Aussi garder une trace de la virgule et l'exposant. Celui-ci sera important plus tard.

    Maintenant, vous pouvez assembler votre nombre à virgule flottante. La première chose à faire est d'analyser la représentation entière de l'chiffres pour le premier set un peu (la plus haute à la plus basse).

    Les bits immédiatement à la suite de la première bits sont vos mantisse.

    L'obtention de l'exposant n'est pas dur non plus. Vous savez que le premier bit de position, la position du point décimal et l'exposant facultatif de la notation scientifique. Combinez-les et ajoutez-les à virgule flottante biais de l'exposant (je pense que c'est 127, mais de vérifier certains de référence s'il vous plaît).

    Cet exposant doit être quelque part dans la gamme de 0 à 255. Si c'est plus grand ou plus petit que vous ont un effet positif ou négatif nombre infini (cas spécial).

    Magasin de l'exposant comme dans les bits de 24 à 30 de votre flotteur.

    Le bit le plus significatif est tout simplement le signe. L'un des moyens négatif, zéro signifie positive.

    Il est plus difficile à décrire qu'il est vraiment, essayez de décomposer un nombre en virgule flottante et de prendre un coup d'oeil à l'exposant et la mantisse, et vous verrez comment facile il est vraiment.

    Btw - faire de l'arithmétique en virgule flottante lui-même est une mauvaise idée parce que vous aurez toujours la force de votre mantisse être tronqué à 23 bits de poids faible. Vous n'obtiendrez pas une représentation exacte de cette façon.

    • Vous êtes ignorant les modes d'arrondi, et al. Jetez un oeil à strtod pour avoir une idée de ce qui est nécessaire.
    • Oui, je sais. Il en est de même de plus j'ai laissé de côté, comme la gestion de denormals et de zéros. Mais il me semblait que l'affiche originale voulais le faire à des fins d'apprentissage, pas pour la production.
    • En partie vrai. Je veux lire un flotteur à partir d'une chaîne, mais il y a d'autres choses suivantes à l'intérieur de la chaîne. Java ne peut pas gérer. Mais depuis le problème s'avère être un exercice extrêmement difficile, je vais analyser le flotteur, le mettre dans une chaîne de caractères et de le jeter à Flotteur.parseFloat() 😉
    • si vous êtes à l'aide de Java, vous trouverez les bitmagic est un--excuser mon mauvais jeu de mots--peu difficile à faire aussi facilement que C. Start off à l'aide de flotteurs pour faire de votre flotteur et puis en vrac zones avec le bit à bit des mathématiques comme Nils suggéré (comme la mantisse). Vous en apprendrez beaucoup sur les mathématiques.
    • Cette description oublie la norme IEEE-754 exposant est un exposant binaire, donc la mantisse doit être multiplié out: 1e2 => 1010b => 1.01e11b. Bien sûr, vous ne pouvez pas faire ce naïvement, que prendrais une résolution de 1024 bits, vous devez le faire par la longue multiplication. Décent float analyse des implémentations de le faire avec une base de 5 bignum.
    • "Décent float analyse des implémentations de le faire avec une base de 5 bignum". Pourquoi? Dites que vous avez fait tout à deux fois la précision requise et ensuite arrondi à double précision, ne seriez-vous pas toujours obtenir la meilleure approximation?
    • pas de double précision n'est pas suffisant si vous cumulez plusieurs erreurs d'arrondi peuvent transformer 1011.1000 en 1011.0111 et ensuite le tour de 1011. au lieu d'attacher la plus proche, même 1100. Vous avez besoin de suffisamment de précision pour la tenue exacte des résultats intermédiaires jusqu'à la finale de la division ou la multiplication, à moins que vous pouvez vous assurer que votre résultat final est assez loin de la cravate...

    InformationsquelleAutor Nils Pipenbrinck
  2. 22

    Toutes les autres réponses ont manqué comment dur est de le faire correctement. Vous pouvez faire une première méthode de réduction à ce qui est exact dans une certaine mesure, mais jusqu'à ce que vous prenez en compte les modes d'arrondi IEEE (et al), vous n'aurez jamais la droit réponse. J'ai écrit naïf implémentations avant avec une assez grande quantité d'erreur.

    Si vous n'avez pas peur des maths, je recommande fortement la lecture de l'article de David Goldberg, Ce Que Tout Informaticien Devez Savoir À Propos De L'Arithmétique À Virgule Flottante. Vous obtiendrez une meilleure compréhension de ce qui se passe sous le capot, et pourquoi les bits sont définis en tant que tels.

    Mon meilleur conseil est de commencer avec un travail atoi mise en œuvre, et de sortir de là. Vous allez trouver rapidement il vous manque des choses, mais un peu regarde strtod's source et vous serez sur la bonne voie (qui est un long, long chemin). Finalement, vous aurez la louange insérer divinité ici qu'il y a des bibliothèques standard.

    /* use this to start your atof implementation */

/* atoi - [email protected] */
/* 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);
}
    • Débordement appelle UB; vous ne pouvez pas détecter elle après le fait. Soit utiliser unsigned types ou de test avant de réaliser l'arithmétique, que peut-débordement.
    • Merci, je crois que mes modifications retirer le comportement indéfini.
    InformationsquelleAutor user7116
  3. 19

    Le "standard" de l'algorithme de conversion d'un nombre décimal à la meilleure virgule flottante rapprochement est William Clinger de Comment lire les nombres à virgule flottante de précision, téléchargeable à partir de ici. Notez que cette opération correctement nécessite de multiples précision des nombres entiers, au moins un certain pourcentage du temps, afin de gérer les cas de coin.

    Algorithmes pour l'autre, l'impression d'un meilleur nombre décimal à partir d'une variable nombre, sont trouvés dans le Burger et Dybvig de L'impression des Nombres à virgule Flottante Rapidement et avec Précision, téléchargeable ici. Cela nécessite aussi de multiples précision arithmétique entière

    Voir aussi David M Gay Arrondie Binaire-Décimal et le séparateur Décimal Binaire Conversions pour les algorithmes d'aller dans les deux sens.

    InformationsquelleAutor Peter S. Housel
  4. 2

    Vous pouvez ignorer la virgule lors de l'analyse (à l'exception de son emplacement). Dire que l'entrée était:
    156.7834e10... Cela pourrait facilement être analysée dans l'entier 1567834 suivie par e10, vous pouvez modifier en e6, depuis le décimal est 4 chiffres à partir de la fin du "chiffre" partie de la flotte.

    De précision est un problème. Vous aurez besoin de vérifier la spécification IEEE de la langue que vous utilisez. Si le nombre de bits de la Mantisse (ou Fraction) est plus grand que le nombre de bits dans votre type Entier, alors vous allez peut-être perdre en précision lorsque quelqu'un tape dans un nombre tel que:

    5123.123123e0 - convertit à 5123123123 dans notre méthode, qui ne correspond PAS à un nombre Entier, mais les bits de 5.123123123 peuvent tenir dans la mantisse du flotteur spec.

    Bien sûr, vous pouvez utiliser une méthode qui prend chaque chiffre avant la virgule, multiplie le total en cours (en float) par 10, puis ajoute les nouveaux chiffres. Pour les chiffres après la virgule, il faut multiplier le chiffre par une montée en puissance de 10 avant de l'ajouter au total actuel. Cette méthode semble poser la question de pourquoi vous faites ceci à tous, cependant, car il nécessite l'utilisation de la virgule flottante primitive sans l'aide de la facilement disponibles bibliothèques d'analyse.

    De toute façon, bonne chance!

    InformationsquelleAutor billjamesdev
  5. 2

    Oui, vous pouvez décomposer la construction dans les opérations à virgule flottante tant que ces opérations sont EXACTE, et vous pouvez vous permettre un unique et final inexact opération.

    Malheureusement, les opérations à virgule flottante bientôt devenir inexact, lorsque vous dépassez la précision de la mantisse, les résultats sont arrondis. Une fois un arrondissement "erreur" est mis en place, il sera cumulée à d'autres opérations...

    Donc, en général, PAS, vous ne pouvez pas utiliser ces naïfs algorithme de conversion arbitraire décimales, ce qui peut conduire à une mauvaise nombre arrondi, par plusieurs ulp de la bonne, comme d'autres l'ont déjà dit.

    MAIS NOUS ALLONS VOIR COMMENT NOUS POUVONS ALLER:

    Si vous soigneusement reconstruire le flotteur comme ceci:

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

    il y a un risque de dépasser la précision à la fois lorsque le cumul des integerMantissa s'il a beaucoup de chiffres, et lors de la récolte de 10 à la puissance de biasedExponent...

    Heureusement, si les deux premières opérations sont exactes, alors vous pouvez vous permettre un final inexact de fonctionnement * ou /, grâce à la norme IEEE propriétés, le résultat sera arrondi correctement.

    Nous allons l'appliquer à simple précision des flotteurs qui ont une précision de 24 bits.

    10^8 > 2^24 > 10^7

    Notant que les multiples de 2 ne fera qu'augmenter l'exposant et de laisser la mantisse inchangée, nous n'avons à traiter avec des puissances de 5 pour une puissance de 10:

    5^11 > 2^24 > 5^10

    Cependant, vous pouvez vous permettre 7 chiffres de précision dans le integerMantissa et un biasedExponent entre -10 et 10.

    En double précision, 53 bits, 

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

    De sorte que vous pouvez vous permettre de 15 chiffres après la virgule, et un exposant biaisé entre -22 et 22.

    C'est à vous de voir si vos numéros tombent toujours dans la plage correcte... (Si vous êtes vraiment difficile, vous pouvez vous arranger pour l'équilibre de la mantisse et de l'exposant par l'insertion/suppression des zéros à la fin).

    Sinon, vous devrez utiliser un peu de la précision étendue.

    Si votre langue fournit une précision arbitraire des entiers, alors il est un peu difficile à trouver le bon, mais pas si difficile, je l'ai fait en Smalltalk et blogué à ce sujet à http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html et http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

    Remarque que ce sont de simple et naïf implémentations. Heureusement, la libc est plus optimisée.

    InformationsquelleAutor aka.nice
  6. 1

    Ma première pensée est pour analyser la chaîne dans un int64 mantisse et un int exposant décimal en utilisant seulement les 18 premiers chiffres de la mantisse. Par exemple, 1.2345 e-5 devrait être analysé en 12345 et -9. Alors je multiplie la mantisse de 10 et de décrémentation l'exposant jusqu'à ce que la mantisse est de 18 chiffres (>56 bits de précision). Puis je regarde la virgule exposant dans une table pour trouver un facteur et exposant binaire qui peut être utilisé pour convertir le nombre de décimal n*10^m binaire p*2^q forme. Le facteur serait une autre int64 donc je multipliez la mantisse, tels que j'ai obtenu le top 64-bits de l'résultant nombre de 128 bits. Cette int64 mantisse peut être converti en float perdre la précision nécessaire et la 2^q l'exposant peut être appliqué à l'aide d'une multiplication sans perte de précision.

    Je m'attends à ce être très précis et très rapide, mais vous pouvez également gérer les numéros spéciaux NaN, -l'infini, -0.0 et de l'infini. Je n'ai pas pensé sur le les nombres dénormalisés ou les modes d'arrondi.

    • Oui, pas mal... Mais le p*2^q est toujours approximative de puissance négative de 10, à droite? En prenant la première de 18 digts est approximative (par exemple valeur exacte de 0,001 prend déjà 58 chiffres décimaux pas de comptabilité pour le premier zéro). Avec deux inexact opérations, je suppose que je peux toujours créer un nombre malchanceux qui se situent de l'autre côté de l'égalité, et donc être à tort arrondis. Rare mais pas inexistant. Même si vous limitez la longueur de 18 chiffres, final arrondi 128->53 bits est un autre inexact op, c'est trop...
    InformationsquelleAutor Jon Harrop
  7. 0

    Pour cela, vous devez comprendre la norme IEEE 754 pour la bonne représentation binaire. Après cela, vous pouvez utiliser Flotteur.intBitsToFloat ou Double.longBitsToDouble.

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

    InformationsquelleAutor Jorge Ferreira
  8. 0

    Si vous voulez que le résultat plus précis possible, vous devriez utiliser une plus haute précision interne de travail, et ensuite convertir le résultat de la précision souhaitée. Si vous n'avez pas l'esprit un peu ULPs d'erreur, alors vous pouvez simplement plusieurs reprises multiplier par 10, si nécessaire avec la précision souhaitée. Je voudrais éviter de la fonction pow (), car elle permettra de produire des résultats erronés pour les grands exposants.

    InformationsquelleAutor Adam Rosenfield
  9. 0

    Il n'est pas possible de convertir n'importe quelle chaîne de caractères représentant un nombre en double ou float, sans perdre de précision. Il y a beaucoup de nombres fractionnaires qui peut être représenté exactement en décimal (par exemple, "0.1") qui ne peut être approchée dans un système binaire de type float ou double. Ceci est similaire à la façon dont la fraction 1/3 ne peut pas être représenté exactement en décimal, vous ne pouvez écrire 0.333333...

    Si vous ne souhaitez pas utiliser une fonction de la bibliothèque directement pourquoi ne pas regarder le code source pour ceux des fonctions de la bibliothèque? Vous avez mentionné Java; la plupart Jdk navire avec le code source de la classe bibliothèques de sorte que vous pourrait regarder comment le java.lang.Double.parseDouble(String) méthode fonctionne. Bien sûr, quelque chose comme BigDecimal est mieux pour le contrôle de la précision et de modes d'arrondi, mais vous avez dit qu'il doit être un float ou double.

    InformationsquelleAutor sk.
  10. -1

    À l'aide d'une machine d'état. Il est assez facile à faire, et fonctionne même si le flux de données est interrompue (vous avez juste à garder l'état et le résultat partiel). Vous pouvez également utiliser un analyseur générateur (si vous êtes en train de faire quelque chose de plus complexe).

    • L'analyse n'est pas le problème, c'est la construction de l'résultant flotteur qui me donne de la difficulté.
    InformationsquelleAutor terminus
  11. -1

    Je suis d'accord avec terminus. Une machine d'état est le meilleur moyen pour accomplir cette tâche, car il existe de nombreuses façons stupide un analyseur peut être rompu. Je suis en train de travailler sur un maintenant, je pense que c'est complet et c'est, je pense, 13 états.

    Le problème n'est pas trivial.

    Je suis un ingénieur en matériel informatique intéressés à la conception de matériel de point flottant. J'en suis à ma deuxième mise en œuvre.

    J'ai trouvé aujourd'hui ce http://speleotrove.com/decimal/decarith.pdf

    qui, à la page 18 donne à certains intéressant de cas de test.

    Oui, j'ai lu Clinger de l'article, mais le fait d'être un simple d'esprit ingénieur hardware, je ne peux pas obtenir mon esprit à travers le code présenté. La référence à Steele algorithme de asnwered dans Knuth du texte a été utile pour moi. À la fois d'entrée et de sortie sont problématiques.

    Toutes ces références aux différents articles sont excellents.

    Je n'ai pas encore inscrivez-vous ici pour l'instant, mais quand je le fais, en supposant que la connexion n'est pas pris, il sera broh. (broh-point).

    Clyde

    InformationsquelleAutor