Perché “dtoa.c” contengono una grande quantità di codice?

Sarò il primo ad ammettere che la mia conoscenza di programmazione a basso livello è un po ‘ sparse. Capisco molti dei concetti di base, ma io non uso di loro su base regolare.
Detto questo io ero assolutamente stupito della quantità di codice necessario per dtoa.c.

Per gli ultimi due mesi ho lavorato su un ECMAScript implementazione in C# e ho rallentare per riempire i buchi nel mio motore. Ieri sera ho iniziato a lavorare su Numero.prototipo.toString che è descritto nella sezione 15.7.4.2 del ECMAScript specifica (pdf). Nella sezione 9.8.1, NOTA 3 offre un link per dtoa.c ma ero alla ricerca di una sfida così ho aspettato di vederlo. Quanto segue è ciò che mi è venuto con.

private IDynamic ToString(Engine engine, Args args)
{
    var thisBinding = engine.Context.ThisBinding;
    if (!(thisBinding is NumberObject) && !(thisBinding is NumberPrimitive))
    {
        throw RuntimeError.TypeError("The current 'this' must be a number or a number object.");
    }

    var num = thisBinding.ToNumberPrimitive();

    if (double.IsNaN(num))
    {
        return new StringPrimitive("NaN");
    }
    else if (double.IsPositiveInfinity(num))
    {
        return new StringPrimitive("Infinity");
    }
    else if (double.IsNegativeInfinity(num))
    {
        return new StringPrimitive("-Infinity");
    }

    var radix = !args[0].IsUndefined ? args[0].ToNumberPrimitive().Value : 10D;

    if (radix < 2D || radix > 36D)
    {
        throw RuntimeError.RangeError("The parameter [radix] must be between 2 and 36.");
    }
    else if (radix == 10D)
    {
        return num.ToStringPrimitive();
    }

    var sb = new StringBuilder();
    var isNegative = false;

    if (num < 0D)
    {
        isNegative = true;
        num = -num;
    }

    var integralPart = Math.Truncate(num);
    var decimalPart = (double)((decimal)num.Value - (decimal)integralPart);
    var radixChars = RadixMap.GetArray((int)radix);

    if (integralPart == 0D)
    {
        sb.Append('0');
    }
    else
    {
        var integralTemp = integralPart;
        while (integralTemp > 0)
        {
            sb.Append(radixChars[(int)(integralTemp % radix)]);
            integralTemp = Math.Truncate(integralTemp / radix);
        }
    }

    var count = sb.Length - 1;
    for (int i = 0; i < count; i++)
    {
        var k = count - i;
        var swap = sb[i];
        sb[i] = sb[k];
        sb[k] = swap;
    }

    if (isNegative)
    {
        sb.Insert(0, '-');
    }

    if (decimalPart == 0D)
    {
        return new StringPrimitive(sb.ToString());
    }

    var runningValue = 0D;
    var decimalIndex = 1D;
    var decimalTemp = decimalPart;

    sb.Append('.');
    while (decimalIndex < 100 && decimalPart - runningValue > 1.0e-50)
    {
        var result = decimalTemp * radix;
        var integralResult = Math.Truncate(result);
        runningValue += integralResult / Math.Pow(radix, decimalIndex++);
        decimalTemp = result - integralResult;
        sb.Append(radixChars[(int)integralResult]);
    }

    return new StringPrimitive(sb.ToString());
}

Qualcuno con più esperienza in programmazione a basso livello spiegare perché dtoa.c ha circa 40 volte tanto di codice? Io non riesco proprio a immaginare il C# è molto più produttivo.

  • Perché non si può immaginare? Che tipo di differenziale è esattamente il motivo per linguaggi come C# sono così popolari.
  • Credo che non è difficile da immaginare. Avrei dovuto capire quanto lavoro va a fare in codice nativo e cross-platform.
  • Avete provato questo codice con ingresso negativo?
  • Beh, che io sia dannato, c’era un bug con i numeri negativi. Bella cattura.
  • Fa questo lavoro con piccoli numeri come 1e-20?
  • Ora, grazie mille. Ragazzi, devo dire.
  • Ho anche il sospetto che (1.3333333333333333).toString(3) non dare 1.1 con l’implementazione…
  • Che è quello che sto cercando. Grazie mille.

InformationsquelleAutor ChaosPandion | 2010-07-03



5 Replies
  1. 40

    dtoa.c contiene due funzioni principali: dtoa(), che converte una doppia corda, e strtod(), che converte una stringa in un valore double. Esso contiene anche un sacco di funzioni di supporto, la maggior parte dei quali sono per la sua implementazione di arbitrario-aritmetica a precisione. dtoa.c pretesa di fama è ottenere queste conversioni, e che può essere fatto, in generale, con arbitraria precisione aritmetica. Essa ha anche un codice per arrotondare le conversioni correttamente in quattro diverse modalità di arrotondamento.

    Il codice tenta di introdurre l’equivalente di dtoa(), e dal momento che si utilizza in virgola mobile a fare il suo conversioni, non sempre ottenere loro di diritto. (Aggiornamento: leggete il mio articolo http://www.exploringbinary.com/quick-and-dirty-floating-point-to-decimal-conversion/ per i dettagli.)

    (Ho scritto molto su questo, sul mio blog, http://www.exploringbinary.com/ . Sei dei miei ultimi sette articoli sono stati circa strtod() conversioni da solo. Leggere attraverso di loro per vedere quanto sia complicato fare arrotondate, le conversioni.)

    • Molto interessante, ho qualche lettura da fare e mi sarà sicuramente bisogno di esplorare questo codice in maggiore dettaglio.
    • Davvero non è difficile credere che mi sarebbe mancato il “entrambi i modi di” conversione presente in questo file. Il codice è davvero difficile per me leggere.
    • Penso che è difficile per la maggior parte delle persone di leggere!
    • Come si spiega il fatto che il numero 1024.1 durante la conversione in base 2 produce lo stesso output in Firefox come si fa nella mia implementazione? Potrebbe essere molto specifici e risultati non corretti potranno essere trovata solo attraverso un’ampia serie di test?
    • Non ogni conversione sarà sbagliato. Provare un po ‘ di più, troverete quello che fa Firefox ottiene di destra e il vostro viene sbagliato. (BTW: come si verifica che sono la stessa cosa? Sei la stampa di tutte le cifre del doppio?)
    • I casi si ottiene sbagliato sarà abbastanza rari, sempre più rari, migliore è la tua implementazione. Se l’implementazione è veramente buono, si può dimostrare che non ottiene qualsiasi di loro torto. Se l’implementazione è una schifezza, potrebbe a malapena a funzionare a tutti. Per esempio, se siete semplicemente alla prova 1024.1, posso passare i test con return "1024.1";. 🙂
    • +1. Per non parlare che Gay dtoa (che è il più piccolo dei due pezzi di funzionalità in dtoa.c) consente inoltre all’utente di specificare il numero di cifre di uscita, e che il metodo di arrotondamento da utilizzare. Mettere senza mezzi termini, il codice C# in questione fa una piccola frazione di quello che dtoa.c, e non a torto, lentamente, e buggily (da provare con i numeri negativi, per esempio).
    • Volevo solo chiarire una cosa: hai detto “1024.1 durante la conversione in base 2”. Ho pensato che significava convertito in binario in virgola mobile, e poi stampato in formato decimale (dopo tutto, la stampa in formato decimale è ciò che rende il problema difficile, e perché dtoa.c esiste). Ma sulla seconda lettura del tuo commento, ho pensato che forse lei diceva che si erano impostazione della radice di 2, e la stampa in formato binario. Che lavoro (supponendo che non c’è nessun errore nel tuo codice, non ho eseguito), in quanto per ogni potenza di 2 base-è essenzialmente lo spostamento di bit. (Ma poi avrei dovuto chiedere — come hai Firefox per stampare in binario?)
    • Woah, take it easy. Io non pretendiamo che questa è la produzione di codice di qualità. Questo è un semplice side-project faccio per divertimento. Io sono solo un curioso coder cercando di capire come tutta questa roba funziona. Non mi interessa che il mio è più lento. Non credo che il mio codice è bacato come si stanno affermando come i numeri negativi funzionano bene. Come per il test ho semplicemente chiamato (1024.1).toString(2); o (144.15).toString(36);. Ovviamente niente di formale, ma il risultato corrisponda Firefox esattamente.
    • Cosa pensi che contribuisce di più per la quantità di codice, compatibilità cross-platform o l’estrema precisione che dtoa fornisce?
    • Hai provato semplicemente vecchio toString() (in base 10)? È interessante — a mia conoscenza, Javascript utilizza dtoa.c, ma dtoa.c consente di stampare solo le stringhe decimali. Mi chiedo che cosa è utilizzato per la stampa a non decimali basi? Come per la quantità di codice, direi che è “l’estrema precisione” requisito (ma Mark è più qualificato per rispondere, avendo lavorato con dtoa.c ampiamente.)
    • Mi chiedo se è perché egli strappa il mio codice di uno nuovo. 🙂
    • Sembra che non ho bisogno di eseguire il test per trovarlo. @sth trovato che (1.3333333333333333).toString(3) è un esempio in cui il mio codice non riesce.
    • Due cose: 1) dtoa.c gestisce solo in base 10, in modo che non siamo più in confronto il codice per dtoa.c (a meno che qualcuno in Javascript, che ha modificato in tal senso). 2) 1.3333333333333333 decimale è concettualmente più vicino a 1.1 base 3, ma non dimenticare che si sta andando attraverso il binario in virgola mobile e poi alla base 3; penso sia consentito di non essere 1.1 in questo caso, come lungo come quello che la stampa rappresenta il valore della variabile a virgola mobile fedelmente.
    • Sai una cosa? La mia uscita corrisponde l’uscita di IE. Non posso fare a meno di chiedersi che cosa esattamente questi due browser stanno facendo. È un po ‘ confortante che la mia uscita corrisponde a un ampiamente usato attuazione però.
    • Potrebbe dare alcuni esempi di adattamento in uscita, per le conversioni da decimale corde? Mi piacerebbe capire meglio di cosa esattamente si stanno confrontando. (Inoltre, sono in esecuzione test casuali, o semplicemente a mano, esempi? Io non credo che si possa dire che l’output è lo stesso a meno che non si esegue milioni di esempi).
    • Io non sono così stupido da pensare che il mio codice funziona al 100% correttamente senza un test formale.
    • Sai che nonostante la gente busting sul mio codice mi sento come ho imparato a 100 volte di più di quanto avrei dovuto, ho appena montato una DLL nativa e usato dtoa.c. Comunque apprezzo le vostre risposte e grazie per il link del blog.
    • È piuttosto strano che il tuo programma semplice doppio decimale conversioni partita IE e Firefox esattamente. Se è vero, allora non ci sarebbe alcun bisogno per dtoa.c. Sto solo suggerendo che forse c’è un errore nella metodologia di prova. Potresti almeno darmi un esempio di una doppia conversione decimale che corrisponde, solo così posso vedere quello che stai confrontando? (E sei il benvenuto per il collegamento al blog!)
    • Scusate per il tono del precedente commento. (2) È la ‘arrotondate, requisito che è responsabile per la maggior parte delle dimensioni di dtoa.c: essenzialmente si contiene un po’ arbitraria precisione intero libreria solo per essere sicuri che i risultati dei calcoli sono arrotondate. E ottenere tutti i casi di angolo esattamente a destra (per non parlare di fare un test più approfondito) è davvero molto difficile.
    • La base della tua domanda è fondamentalmente; “il Mio codice fa quello che dtoa fa, quindi perché dtoa così grande?” Che non è corretto, il tuo codice non fare quello che dtoa fa, in modo da non essere sorpreso quando la gente vi chiamerà su di esso.
    • Swangren – Modo di suonare come un pomposo coglione, ho fatto la domanda per essere istruiti a non pompare il mio ego.
    • Wow, troppo conversazione qui. Ragazzi, dovreste aver fatto in chat.

  2. 8

    Produzione di buona risultati per le conversioni tra decimale e binario in virgola mobile rappresentazioni è un problema piuttosto difficile.

    La principale fonte di difficoltà è che molti frazioni decimali, anche le più semplici, non possono essere accuratamente espresso binaria in virgola mobile, ad esempio, 0.5 può (ovviamente), ma 0.1 non può. E, in senso contrario (da binario a decimale), in genere non si vuole assolutamente il risultato esatto (per esempio, per la precisione di valore decimale del numero più vicino a 0.1, che possono essere rappresentati in un IEEE-754-compatibile double è in realtà
    0.1000000000000000055511151231257827021181583404541015625) così normalmente si desidera che alcuni di arrotondamento.

    Pertanto, la conversione comporta spesso approssimazione. Una buona routine di conversione di garanzia per produrre il più vicino possibile approssimazione nell’ambito di particolari (la dimensione di parola o il numero di cifre) vincoli. Questo è dove la maggior parte della complessità deriva dal.

    Dare un’occhiata al documento citato nel commento al top della dtoa.c attuazione, Clinger del Come Leggere i Numeri in virgola Mobile con Precisione, per un sapore del problema; e, forse, David M. Gay (autore),’s di carta, Arrotondate, Binario-Decimale e Decimale-Binario Conversioni.

    (Anche, più in generale: Quello Che Ogni Computer Scienziato Deve Conoscere L’Aritmetica In Virgola Mobile.)

    • Sono ben consapevole delle sfide che a virgola mobile rappresenta. La mia domanda ha a che fare con la differenza nella quantità di codice. Quando stavo testando il mio esempio contro il mio Firefox codice prodotto risultati identici. Firefox non utilizzare dtoa.c.
  3. 4

    Basati su una rapida occhiata, una buona dose di C versione che fare con diverse piattaforme e come sembra che questo file è pensato per essere genericamente utilizzabile attraverso i compilatori C & C++), bitnesses, virgola mobile implementazioni e piattaforme, con tonnellate di #define configurabilità.

    • Sono D’Accordo. Ho avuto anche una breve occhiata al codice, ho sentito male del lavoro rappresenta per tale semplice operazione. Con .NETTO vedo questi tempi fortunatamente dietro di noi per la programmazione dell’applicazione.
    • Non sarebbe solo essere più facile di avere un archivio di file c con ogni supporto di una piattaforma separata? La lettura a tutti coloro #ifdef blocchi mi ha dato un aneurisma cerebrale…
    • Sì, il problema non è l’lingue, è solo imbarazzante il design complessivo. Lo stesso effetto può essere ottenuto con una migliore modularità.
    • dipende se vuoi che il tuo specifico per la piattaforma di eseguire la configurazione in un file di intestazione C (impostazione definisce), o in un makefile (selezionando il diritto .c file di costruire). Inoltre, se ci sono abbastanza definisce per darvi un aneurisma, che potrebbe essere di 2^aneurisma distinti file c se tutte le possibilità sono state mostrate. In pratica, durante la scrittura di questo tipo di ultra-portatile roba che di solito vuole un piccolo numero di file di origine (in questo caso 1, ma a volte un paio di più) guidato da un gran numero di opzioni di configurazione, piuttosto che l’altro senso intorno.
    • … e la ragione si potrebbe desiderare di scrivere il codice per il supporto delle piattaforme basate sul loro comportamento e delle proprietà, piuttosto che scrivere esattamente un dtoa attuazione per ogni piattaforma, è così che si può porta a nuove piattaforme semplicemente scrivendo un file di intestazione con la giusta combinazione di definisce, piuttosto che ri-scrittura di tutti stdlib ogni volta. Ampiamente configurabile dall’attuazione come questo non è sempre il migliore, ma potrebbe non essere così male come sembra quando si considera l’alternativa.
    • Tu sai che io penso che semplicemente potrebbe essere stato lo shock iniziale di vedere così tanto di codice. Guardando più nel dettaglio, è vero che viene fornito insieme un po ‘ meglio. Ho trovato anche @Tyler commento dell’ @Lajnold la risposta di essere un po ‘ illuminante sull’argomento.
    • Cosa pensi che contribuisce di più per la quantità di codice, compatibilità cross-platform o l’estrema precisione che dtoa fornisce?
    • difficile per me giudicare, senza scavare in esso (stima approssimativa di circa 50/50). Un modo per separare il grano forma la pula sarebbe quello di guardare il pre-elaborati di output per una compilation che ha avuto il #definisce impostare il modo in cui si desidera supportare. Utilizzando MS strumenti che si possono fare con qualcosa di simile a: CL /E /C dtoa.c > dtoa.pre.c. Questo vi mostrerà ciò che il preprocessore è in realtà la presentazione del compilatore.

  4. 4

    Penso anche che il codice in dtoa.c potrebbe essere più efficiente (indipendente dalla lingua). Sembra, ad esempio, per fare un po ‘ di bit-giocherellare, che nelle mani di un esperto spesso significa velocità. Suppongo che semplicemente utilizza un meno intuitiva di algoritmo per motivi di velocità.

    • Un sacco di funzioni di libreria C (e la libreria C estensioni) sono scritti come questo. Ha senso, perché in genere non sono aggiornati, modificati, o comunque mantenuto molto frequentemente, ma sono chiamati in tutto il luogo da un vasto numero di programmi. Ha senso solo per fare il più velocemente possibile, anche a scapito di qualche manutenzione.
  5. 2

    Risposta breve: perché dtoa.c opere.

    Questa è esattamente la differenza tra bene-debug del prodotto e NIH prototipo.

    • Cosa significa NIH significa?
    • “Non inventato qui”, come in “custom ad-hok codice, come un’alternativa al popolare il 3 ° partito di codice”
    • Voglio dire, hai ragione, ma non spiega nulla perché c’è così tanto di codice. Chi lo sa, magari qualcun altro ha scritto una implementazione che correttamente convertito con la metà della maggior parte del codice e il doppio di quanto la funzionalità.

Lascia un commento