Come analizzare manualmente un numero in virgola mobile da una stringa

Question

Naturalmente la maggior parte dei linguaggi ha funzioni di libreria per questo, ma supponiamo che io voglia farlo da solo.

Supponiamo che il float sia dato come in un programma C o Java (ad eccezione del suffisso 'f' o 'd'), ad esempio "4.2e1", ".42e2"o semplicemente"42".In generale, abbiamo la "parte intera" prima della virgola decimale, la "parte frazionaria" dopo la virgola decimale e l'"esponente".Tutti e tre sono numeri interi.

È facile trovare ed elaborare le singole cifre, ma come comporle in un valore di tipo float O double senza perdere precisione?

Sto pensando di moltiplicare la parte intera per 10^N, Dove N è il numero di cifre nella parte frazionaria, quindi somma la parte frazionaria alla parte intera e sottrae N dall'esponente.Questo effettivamente gira 4.2e1 in 42e0, Per esempio.Allora potrei usare il pow funzione per calcolare 10^esponente e moltiplicare il risultato per la nuova parte intera.La domanda è: questo metodo garantisce la massima precisione in ogni fase?

Qualche idea su questo?

Answer 1

Vorrei assemblare direttamente il numero in virgola mobile utilizzando la sua rappresentazione binaria.

Leggi il numero un carattere dopo l'altro e trova prima tutte le cifre.Fallo con l'aritmetica dei numeri interi.Tieni traccia anche del punto decimale e dell'esponente.Questo sarà importante più tardi.

Ora puoi assemblare il tuo numero in virgola mobile.La prima cosa da fare è scansionare la rappresentazione intera delle cifre per il primo bit impostato (dal più alto al più basso).

I bit immediatamente successivi al primo bit sono la tua mantissa.

Anche ottenere l'esponente non è difficile.Conosci la prima posizione di un bit, la posizione del punto decimale e l'esponente opzionale dalla notazione scientifica.Combinali e aggiungi il bias dell'esponente in virgola mobile (penso che sia 127, ma controlla qualche riferimento per favore).

Questo esponente dovrebbe essere compreso tra 0 e 255.Se è più grande o più piccolo hai un numero infinito positivo o negativo (caso speciale).

Memorizza l'esponente così com'è nei bit da 24 a 30 del tuo float.

La parte più significativa è semplicemente il segno.Uno significa negativo, zero significa positivo.

È più difficile da descrivere di quanto non sia in realtà, prova a scomporre un numero in virgola mobile e dai un'occhiata all'esponente e alla mantissa e vedrai quanto è facile.

A proposito, eseguire l'aritmetica in virgola mobile è di per sé una cattiva idea perché costringerai sempre la tua mantissa a essere troncata a 23 bit significativi.Non otterrai una rappresentazione esatta in questo modo.

Answer 2

Tutte le altre risposte hanno mancato come difficile è farlo correttamente.Puoi eseguire un approccio di primo taglio a questo che è accurato in una certa misura, ma finché non prendi in considerazione le modalità di arrotondamento IEEE (et al), non avrai mai la possibilità Giusto risposta.Ho già scritto implementazioni ingenue con una quantità di errori piuttosto grande.

Se non hai paura della matematica, ti consiglio vivamente di leggere il seguente articolo di David Goldberg, Ciò che ogni informatico dovrebbe sapere sull'aritmetica in virgola mobile.Comprenderai meglio cosa sta succedendo sotto il cofano e perché i pezzi sono disposti come tali.

Il mio miglior consiglio è di iniziare con un'implementazione atoi funzionante e proseguire da lì.Scoprirai rapidamente che ti mancano delle cose, ma alcuni sguardi strtode sarai sulla strada giusta (che è una strada lunga, molto lunga).Alla fine loderai inserisci la divinità qui che esistono librerie 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);
}

Answer 3

L'algoritmo "standard" per convertire un numero decimale nella migliore approssimazione in virgola mobile è quello di William Clinger Come leggere con precisione i numeri in virgola mobile, scaricabile da Qui.Si noti che per eseguire questa operazione correttamente sono necessari numeri interi a precisione multipla, almeno una certa percentuale di volte, per gestire casi limite.

Gli algoritmi per andare nella direzione opposta, stampando il miglior numero decimale da un numero mobile, si trovano in Burger e Dybvig Stampa di numeri in virgola mobile in modo rapido e accurato, scaricabile Qui.Ciò richiede anche l'aritmetica dei numeri interi a precisione multipla

Vedi anche David M. Gay Conversioni binario-decimale e decimale-binario correttamente arrotondate per algoritmi che vanno in entrambe le direzioni.

Answer 4

Potresti ignorare il decimale durante l'analisi (ad eccezione della sua posizione).Supponiamo che l'input sia stato:156.7834e10...Questo potrebbe essere facilmente analizzato nel numero intero 1567834 seguito da e10, che poi modificheresti in e6, poiché il decimale era a 4 cifre dalla fine della parte "numerale" del float.

La precisione è un problema.Dovrai controllare le specifiche IEEE della lingua che stai utilizzando.Se il numero di bit nella Mantissa (o Frazione) è maggiore del numero di bit nel tipo Intero, potresti perdere la precisione quando qualcuno digita un numero come:

5123.123123e0 - converte in 5123123123 nel nostro metodo, che NON rientra in un numero intero, ma i bit per 5.123123123 potrebbero rientrare nella mantissa della specifica float.

Naturalmente, potresti usare un metodo che prende ogni cifra davanti al decimale, moltiplica il totale corrente (in float) per 10, quindi aggiunge la nuova cifra.Per le cifre dopo il decimale, moltiplica la cifra per una potenza crescente di 10 prima di aggiungere al totale corrente.Questo metodo sembra sollevare la questione del perché lo stai facendo, poiché richiede l'uso della primitiva in virgola mobile senza utilizzare le librerie di analisi prontamente disponibili.

Comunque, buona fortuna!

Answer 5

SÌ, puoi scomporre la costruzione in operazioni in virgola mobile fino a quando queste operazioni sono ESATTO, e puoi permetterti a unico finale impreciso operazione.

Sfortunatamente, operazioni in virgola mobile Presto diventano imprecisi, quando si supera la precisione della mantissa i risultati vengono arrotondati.Una volta introdotto un "errore" di arrotondamento, questo verrà cumulato in ulteriori operazioni...
Quindi, in genere, NO, non puoi utilizzare un algoritmo così ingenuo per convertire decimali arbitrari, questo potrebbe portare a un numero arrotondato in modo errato, sfalsato di diversi ulp da quello corretto, come altri ti hanno già detto.

MA VEDIAMO QUANTO LONTANO POSSIAMO ARRIVARE:

Se ricostruisci attentamente il float in questo modo:

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

c'è il rischio di superare la precisione sia quando si cumula l'interoMantissa se ha molte cifre, sia quando si eleva 10 alla potenza di biasedExponent...

Fortunatamente, se le prime due operazioni sono esatte, allora puoi permetterti un'operazione finale inesatta * o /, grazie alle proprietà IEEE, il risultato verrà arrotondato correttamente.

Applichiamolo ai float a precisione singola che hanno una precisione di 24 bit.

10^8 > 2^24 > 10^7

Notando che multipli di 2 aumenteranno solo l'esponente e lasceranno invariata la mantissa, dobbiamo occuparci solo delle potenze di 5 per l'esponenziazione di 10:

5^11 > 2^24 > 5^10

Tuttavia, puoi permetterti 7 cifre di precisione nell'interoMantissa e un esponente parziale compreso tra -10 e 10.

In doppia precisione, 53 bit,

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

Quindi puoi permetterti 15 cifre decimali e un esponente distorto compreso tra -22 e 22.

Sta a te vedere se i tuoi numeri rientreranno sempre nell'intervallo corretto...(Se sei davvero complicato, potresti bilanciare la mantissa e l'esponente inserendo/rimuovendo gli zeri finali).

Altrimenti, dovrai usare una precisione estesa.
Se la tua lingua fornisce numeri interi di precisione arbitraria, allora è un po' complicato farlo bene, ma non così difficile, l'ho fatto in Smalltalk e ne ho scritto sul blog su http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html E http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

Tieni presente che queste sono implementazioni semplici e ingenue.Fortunatamente, libc è più ottimizzato.

Answer 6

Il mio primo pensiero è analizzare la stringa in un file an int64 mantissa e un int esponente decimale utilizzando solo le prime 18 cifre della mantissa.Ad esempio, 1.2345e-5 verrebbe analizzato in 12345 e -9.Quindi continuerei a moltiplicare la mantissa per 10 e a decrementare l'esponente finché la mantissa non fosse lunga 18 cifre (> 56 bit di precisione).Quindi cercherei l'esponente decimale in una tabella per trovare un fattore e un esponente binario che possano essere utilizzati per convertire il numero dalla forma decimale n*10^m alla forma binaria p*2^q.Il fattore sarebbe un altro int64 quindi moltiplicherei la mantissa per essa in modo tale da ottenere i primi 64 bit del numero risultante a 128 bit.Questo int64 la mantissa può essere trasformata in float perdendo solo la precisione necessaria e l'esponente 2^q può essere applicato utilizzando la moltiplicazione senza perdita di precisione.

Mi aspetto che questo sia molto preciso e molto veloce, ma potresti anche voler gestire i numeri speciali NaN, -infinity, -0.0 e infinito.Non ho pensato ai numeri denormalizzati o alle modalità di arrotondamento.

Answer 7

Per questo è necessario comprendere lo standard IEEE 754 per una corretta rappresentazione binaria.Dopodiché puoi usare Float.intBitsToFloat O Double.longBitsToDouble.

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

Answer 8

Se si desidera il risultato più preciso possibile, è necessario utilizzare una precisione di lavoro interna più elevata e quindi convertire il risultato alla precisione desiderata.Se non ti dispiace qualche ULP di errore, puoi semplicemente moltiplicare ripetutamente per 10 secondo necessità con la precisione desiderata.Eviterei la funzione pow(), poiché produrrà risultati inesatti per esponenti di grandi dimensioni.

Answer 9

Non è possibile convertire una stringa arbitraria che rappresenta un numero in un double o in float senza perdere la precisione.Esistono molti numeri frazionari che possono essere rappresentati esattamente in decimale (ad es."0.1") che può essere approssimato solo in un float binario o double.Questo è simile a come la frazione 1/3 non può essere rappresentata esattamente in decimale, puoi solo scrivere 0,333333...

Se non vuoi utilizzare direttamente una funzione di libreria, perché non guardare il codice sorgente di quelle funzioni di libreria?Hai menzionato Java;la maggior parte dei JDK viene fornita con il codice sorgente per le librerie di classi in modo da poter verificare come funziona il metodo java.lang.Double.parseDouble(String).Ovviamente qualcosa come BigDecimal è migliore per controllare la precisione e le modalità di arrotondamento, ma hai detto che deve essere float o double.

Answer 10

Utilizzando una macchina statale.È abbastanza semplice da eseguire e funziona anche se il flusso di dati viene interrotto (devi solo mantenere lo stato e il risultato parziale).Puoi anche utilizzare un generatore di parser (se stai facendo qualcosa di più complesso).

Answer 11

Sono d'accordo con capolinea.Una macchina a stati è il modo migliore per svolgere questo compito poiché esistono molti modi stupidi in cui un parser può essere danneggiato.Sto lavorando su uno adesso, penso che sia completo e penso che abbia 13 stati.

Il problema non è banale.

Sono un ingegnere hardware interessato alla progettazione di hardware in virgola mobile.Sono alla seconda implementazione.

Ho trovato questo oggi http://speleotrove.com/decimal/decarith.pdf

che a pagina 18 fornisce alcuni casi di test interessanti.

Sì, ho letto l'articolo di Clinger, ma essendo un ingegnere hardware dalla mentalità semplice, non riesco a capire il codice presentato.Il riferimento all'algoritmo di Steele come risposto nel testo di Knuth mi è stato utile.Sia l’input che l’output sono problematici.

Tutti i riferimenti sopra citati ai vari articoli sono eccellenti.

Devo ancora iscrivermi qui, ma quando lo farò, supponendo che il login non sia stato effettuato, sarà broh.(broh-punto).

Clyde