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

https://stackoverflow.com/questions/85223

01-07-2019
|

Question

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

Supposons que le float soit donné comme dans un programme C ou Java (à l'exception du suffixe "f" ou "d"), par exemple " 4.2e1 ", " .42e2 " ou simplement " 42 ". En général, nous avons la " partie entière " avant la virgule décimale, la "fraction décimale" après la virgule décimale et "l'exposant". Les trois sont des entiers.

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

Je songe à multiplier la partie entière par 10 ^ n , où n est le nombre de chiffres de la partie décimale, puis à ajouter la partie décimale à la partie entière et soustrayant n de l'exposant. Cela transforme effectivement 4.2e1 en 42e0 , par exemple. Ensuite, je pourrais utiliser la fonction pow pour calculer 10 ^ exposant et multiplier le résultat par la nouvelle partie entière. La question est de savoir si cette méthode garantit une précision maximale tout au long?

Avez-vous des idées à ce sujet?

La solution

Je voudrais assembler directement le nombre à virgule flottante en utilisant sa représentation binaire.

Lis le caractère numéro un après l’autre et trouve d’abord tous les chiffres. Faites cela en arithmétique entière. Gardez également une trace du point décimal et de l’exposant. Celui-ci sera important plus tard.

Vous pouvez maintenant assembler votre nombre à virgule flottante. La première chose à faire est d’analyser la représentation entière des chiffres pour le premier ensemble d’un bit (de l’ordre le plus élevé au plus faible).

Les bits qui suivent immédiatement le premier bit sont votre mantisse.

Obtenir l’exposant n’est pas difficile non plus. Vous connaissez la position du premier bit, la position du point décimal et l'exposant facultatif de la notation scientifique. Combinez-les et ajoutez le biais de l'exposant en virgule flottante (je pense qu'il s'agit de 127, mais vérifiez s'il vous plaît une référence s'il vous plaît).

Cet exposant doit être compris entre 0 et 255. S'il est plus grand ou plus petit, vous avez un nombre infini positif ou négatif (cas spécial).

Stockez l'exposant dans les bits 24 à 30 de votre float.

Le bit le plus significatif est simplement le signe. Un signifie négatif, zéro signifie positif.

C’est plus difficile à décrire qu’il ne l’est réellement, essayez de décomposer un nombre à virgule flottante et jetez un coup d’œil à l’exposant et à la mantisse pour voir à quel point il est facile.

Btw - faire l’arithmétique en virgule flottante est une mauvaise idée car vous forcerez toujours votre mantisse à être tronquée à 23 bits significatifs. Vous n'obtiendrez pas une représentation exacte de cette façon.

Autres conseils

Toutes les autres réponses ont manqué la difficulté de le faire correctement. Vous pouvez utiliser une approche de première coupe précise, mais jusqu'à ce que vous preniez en compte les modes d'arrondi IEEE (et autres), vous n'aurez jamais la réponse right . J'ai déjà écrit des implémentations naïves avec une quantité d'erreur assez importante.

Si vous n’êtes pas effrayé par les mathématiques, je vous recommande vivement de lire l’article suivant de David Goldberg, Ce que tous les informaticiens devraient savoir sur l'arithmétique en virgule flottante . Vous aurez une meilleure compréhension de ce qui se passe sous le capot et de la raison pour laquelle les éléments sont présentés comme tels.

Mon meilleur conseil est de commencer par une mise en œuvre fonctionnelle de l’atoi et de partir de là. Vous constaterez rapidement qu'il vous manque des éléments, mais vous pouvez vous pencher sur strtod La source est et vous serez sur le bon chemin (qui est un très long chemin). Vous finirez par louer l'insertion de diety ici pour le fait qu'il existe des bibliothèques standard.

/* 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);
}

Le " standard " L’algorithme permettant de convertir un nombre décimal en approximation optimale à virgule flottante est le , téléchargeable depuis ici . Notez que cela nécessite correctement des entiers à précision multiple, au moins un certain pourcentage du temps, afin de gérer les cas de coin.

Les algorithmes permettant d’agir dans le sens inverse, imprimant le meilleur nombre décimal à partir d’un nombre flottant, se trouvent dans Burger et Dybvig Impression rapide et précise de nombres à virgule flottante , téléchargeable ici . Cela nécessite également une arithmétique entière à précision multiple

Voir aussi Binary-Decimal et Decimal correctement arrondis Conversions binaires pour les algorithmes allant dans les deux sens.

Vous pouvez ignorer la décimale lors de l'analyse (à l'exception de son emplacement). Dites que l'entrée était: 156,7834e10 ... Cela pourrait facilement être analysé dans le nombre entier 1567834 suivi de e10, que vous modifieriez ensuite en e6, car le nombre décimal était composé de 4 chiffres à partir de la fin du "numéral". partie du flotteur.

La précision est un problème. Vous devrez vérifier les spécifications IEEE de la langue que vous utilisez. Si le nombre de bits de la mantisse (ou de la fraction) est supérieur au nombre de bits de votre type entier, vous risquez de perdre de la précision lorsque quelqu'un tape un nombre tel que:

5123.123123e0 - convertit en 5123123123 dans notre méthode, qui ne rentre PAS dans un entier, mais les bits de 5.123123123 peuvent entrer dans la mantisse de la spécification float.

Bien sûr, vous pouvez utiliser une méthode qui prend chaque chiffre devant la décimale, multiplie le total actuel (dans un flottant) par 10, puis ajoute le nouveau chiffre. Pour les chiffres après la décimale, multipliez le chiffre par une puissance croissante de 10 avant d’ajouter au total actuel. Cette méthode semble toutefois poser la question de savoir pourquoi vous le faites, car elle nécessite l'utilisation de la primitive à virgule flottante sans utiliser les bibliothèques d'analyse aisément disponibles.

En tout cas, bonne chance!

Oui , vous pouvez décomposer la construction en opérations à virgule flottante tant que ces opérations sont EXACT , et vous pouvez vous permettre une opération finale unique inexacte .

Malheureusement, les opérations en virgule flottante bientôt deviennent inexactes. Lorsque vous dépassez la précision de la mantisse, les résultats sont arrondis. Une fois l’arrondi " erreur " est introduit, il sera cumulé dans les prochaines opérations ...
Ainsi, en règle générale, NON , vous ne pouvez pas utiliser cet algorithme naïf pour convertir des nombres décimaux arbitraires. Cela peut conduire à un nombre arrondi incorrectement, avec plusieurs ulp du correct, comme d'autres vous l'ont déjà dit. .

MAIS, LORSQUE NOUS POUVONS NOUS ALLER:

Si vous reconstruisez soigneusement le flottant comme ceci:

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

il y a un risque de dépassement de la précision lors de la cumul de la valeur de integerMantissa si elle comporte plusieurs chiffres et lors de la montée de 10 à la puissance de partialedExponent ...

Heureusement, si les deux premières opérations sont exactes, vous pouvez vous permettre une dernière opération inexacte * ou /, grâce aux propriétés IEEE, le résultat sera arrondi correctement.

Appliquons cela aux flotteurs à simple précision qui ont une précision de 24 bits.

10^8 > 2^24 > 10^7

En notant qu'un multiple de 2 ne fera qu'augmenter l'exposant et à laisser la mantisse inchangée, il suffit de traiter avec des puissances de 5 pour une exponentiation de 10:

5^11 > 2^24 > 5^10

Cependant, vous pouvez vous permettre une précision de 7 chiffres dans la valeur entièreMantissa et un biais biaisé compris entre -10 et 10.

En double précision, 53 bits,

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

Vous pouvez donc vous permettre 15 chiffres décimaux et un exposant biaisé compris entre -22 et 22.

C’est à vous de voir si vos nombres tomberont toujours dans la plage correcte ... (si vous êtes vraiment compliqué, vous pouvez organiser votre équilibre entre mantisse et exposant en insérant / supprimant des zéros à la fin).

Sinon, vous devrez utiliser une précision accrue.
Si votre langue fournit des entiers de précision arbitraire, il est un peu délicat de bien faire les choses, mais ce n'est pas si difficile. Je l'ai fait dans Smalltalk et j'ai blogué à ce sujet à l'adresse http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html et http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

Notez qu'il s'agit d'implémentations simples et naïves. Heureusement, la libc est plus optimisée.

Ma première pensée est d’analyser la chaîne dans une mantisse int64 et un exposant décimal int en utilisant uniquement les 18 premiers chiffres de la mantisse. Par exemple, 1.2345e-5 serait analysé dans 12345 et -9. Ensuite, je multipliais la mantisse par 10 et décrémentais l'exposant jusqu'à ce que la mantisse ait 18 chiffres (> 56 bits de précision). Ensuite, je chercherais l’exposant décimal dans un tableau pour trouver un facteur et un exposant binaire pouvant être utilisés pour convertir le nombre décimal n * 10 ^ m en forme binaire p * 2 ^ q. Le facteur serait un autre int64 , je multiplierais donc la mantisse de manière à obtenir les 64 premiers bits du nombre de 128 bits obtenu. Cette mantisse int64 peut être transformée en un flottant ne perdant que la précision nécessaire et l'exposant 2 ^ q peut être appliqué à l'aide de la multiplication sans perte de précision.

Je m'attendrais à ce que ce soit très précis et très rapide, mais vous pouvez également gérer les nombres spéciaux NaN, -infinity, -0,0 et l'infini. Je n'ai pas pensé aux nombres dénormalisés ni aux modes d'arrondi.

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

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

Si vous souhaitez obtenir le résultat le plus précis possible, vous devez utiliser une précision de travail interne supérieure, puis convertir le résultat à la précision souhaitée. Si quelques erreurs ULP ne vous dérangent pas, vous pouvez simplement multiplier par 10 de manière répétée, selon les besoins, avec la précision souhaitée. J'éviterais la fonction pow (), car elle produirait des résultats inexacts pour les exposants importants.

Il n’est pas possible de convertir une chaîne quelconque représentant un nombre en double ou en virgule flottante sans perdre en précision. Il existe de nombreux nombres fractionnaires qui peuvent être représentés exactement en décimal (par exemple, "0,1") et qui ne peuvent être approximés que dans un nombre binaire ou double. Ceci est similaire à la façon dont la fraction 1/3 ne peut pas être représentée exactement en décimal, vous ne pouvez écrire que 0.333333 ...

Si vous ne souhaitez pas utiliser directement une fonction de bibliothèque, pourquoi ne pas consulter le code source de ces fonctions de bibliothèque? Vous avez mentionné Java. la plupart des JDK sont livrés avec le code source des bibliothèques de classes afin que vous puissiez voir comment fonctionne la méthode java.lang.Double.parseDouble (String). Bien sûr, quelque chose comme BigDecimal est préférable pour contrôler les modes d'arrondi et de précision, mais vous avez dit que cela devait être un float ou un double.

Utilisation d’une machine à états. C'est assez facile à faire, et ça marche même si le flux de données est interrompu (il suffit de garder l'état et le résultat partiel). Vous pouvez également utiliser un générateur d’analyseur (si vous faites quelque chose de plus complexe).

Je suis d'accord avec le terminus. Une machine à états est le meilleur moyen d’accomplir cette tâche car il existe de nombreuses manières stupides de briser un analyseur. Je travaille sur un projet maintenant, je pense qu'il est complet et que je pense à 13 États.

Le problème n'est pas anodin.

Je suis un ingénieur en matériel intéressé à concevoir du matériel en virgule flottante. Je suis sur ma deuxième implémentation.

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

qui à la page 18 donne quelques cas de test intéressants.

Oui, j'ai lu l'article de Clinger, mais étant un ingénieur en matériel simple d'esprit, je n'arrive pas à comprendre le code présenté. La référence à l'algorithme de Steele, telle que fournie dans le texte de Knuth, m'a été utile. Les entrées et les sorties sont problématiques.

Toutes les références susmentionnées à divers articles sont excellentes.

Je n'ai pas encore signé ici, mais si je le fais, en supposant que l'identifiant ne soit pas pris, ce sera chéri. (point broh).

Clyde

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow