Qual è il primo doppio che devia dal suo corrispondente lungo da Delta?

Question

Vorrei sapere il primo doppio da verso l'alto 0d che devia dalla lunga dello "stesso valore" di un certo delta, dire 1e-8. Sto in mancanza qui però. Sto cercando di fare questo in C anche se io di solito uso lingue gestite, per ogni evenienza. Si prega di aiutare.

#include <stdio.h>
#include <limits.h>
#define DELTA 1e-8

int main() {
    double d = 0; // checked, the literal is fine
    long i;
    for (i = 0L; i < LONG_MAX; i++) {
         d=i; // gcc does the cast right, i checked
         if (d-i > DELTA || d-i < -DELTA) {
              printf("%f", d);
              break;
         }
    }
}

Sto indovinando che il problema è che di calchi i per raddoppiare e quindi d == I e poi la differenza è sempre 0. Altrimenti come posso rilevare questo correttamente - Preferirei divertimento C fusione sopra stringhe confronto , che avrebbe preso per sempre.

RISPOSTA : è esattamente come ci aspettavamo. 2 ^ 53 + 1 = 9007199254740993 è il primo punto di differenza secondo strumenti C / UNIX / POSIX standard. Grazie molto per pax per il suo programma. E credo che la matematica vince ancora.

Answer 1

raddoppia in IEE754 hanno una precisione di 52 bit che significa che possono memorizzare numeri precisione fino a (almeno) 2 ⁵¹ .

Se i Longs sono a 32-bit, avranno solo il campo (positivo) 0-2 ³¹ quindi non c'è a 32 bit a lungo che non può essere rappresentato esattamente come un doppio. Per un 64-bit lungo, sarà (approssimativamente) 2 ⁵² quindi mi piacerebbe partirò lì intorno, non a zero.

È possibile utilizzare il seguente programma per rilevare in cui i fallimenti cominciano a verificarsi. Una versione precedente che aveva fatto affidamento sul fatto che l'ultima cifra in un numero che raddoppia continuamente segue la sequenza {2,4,8,6}. Tuttavia, alla fine ho optato per utilizzare un noto (bc) strumento di fiducia per la verifica del numero intero, non solo l'ultima cifra.

Tenete a mente che questo possono essere influenzato dalle azioni di sprintf() piuttosto che il vero e accuratezza dei doppi (io non la penso così personalmente dal momento che non ha avuto problemi con alcuni numeri fino a 2 < sup> 143 ).

Questo è il programma:

#include <stdio.h>
#include <string.h>

int main() {
    FILE *fin;
    double d = 1.0; // 2^n-1 to avoid exact powers of 2.
    int i = 1;
    char ds[1000];
    char tst[1000];

    // Loop forever, rely on break to finish.
    while (1) {
        // Get C version of the double.
        sprintf (ds, "%.0f", d);

        // Get bc version of the double.
        sprintf (tst, "echo '2^%d - 1' | bc >tmpfile", i);
        system(tst);
        fin = fopen ("tmpfile", "r");
        fgets (tst, sizeof (tst), fin);
        fclose (fin);
        tst[strlen (tst) - 1] = '\0';

        // Check them.
        if (strcmp (ds, tst) != 0) {
            printf( "2^%d - 1 <-- bc failure\n", i);
            printf( "   got       [%s]\n", ds);
            printf( "   expected  [%s]\n", tst);
            break;
        }

        // Output for status then move to next.
        printf( "2^%d - 1 = %s\n", i, ds);
        d = (d + 1) * 2 - 1;  // Again, 2^n - 1.
        i++;
    }
}

Questa continua ad andare fino:

2^51 - 1 = 2251799813685247
2^52 - 1 = 4503599627370495
2^53 - 1 = 9007199254740991
2^54 - 1 <-- bc failure
   got       [18014398509481984]
   expected  [18014398509481983]

che è circa dove mi aspettavo di fallire.

Per inciso, ho inizialmente numeri della forma usato 2 ⁿ , ma che mi ha fatto fino a:

2^136 = 87112285931760246646623899502532662132736
2^137 = 174224571863520493293247799005065324265472
2^138 = 348449143727040986586495598010130648530944
2^139 = 696898287454081973172991196020261297061888
2^140 = 1393796574908163946345982392040522594123776
2^141 = 2787593149816327892691964784081045188247552
2^142 = 5575186299632655785383929568162090376495104
2^143 <-- bc failure
   got       [11150372599265311570767859136324180752990210]
   expected  [11150372599265311570767859136324180752990208]

con le dimensioni di una doppia essendo 8 byte (verificato con sizeof). Si è scoperto questi numeri erano del "1000..." forma binaria che può essere rappresentato molto più a lungo con doppie. Questo è quando sono passato ad usare 2 ⁿ -1 per ottenere una migliore po modello:. Tutti uno bit

Answer 2

Il primo lungo per essere 'sbagliato', quando gettato in un letto non sarà fuori da 1e-8, sarà fuori dal 1. Finché il doppio può andare bene la lunga nel suo significante, rappresenterà con precisione .

ho dimenticato esattamente quanti bit un doppio ha per la precisione vs compensato, ma che direbbe la dimensione massima potrebbe rappresentare. Il primo tempo di essere sbagliato dovrebbe avere la forma binaria 10000 ..., in modo da poter trovare molto più veloce da a partire da 1 e sinistra-shifting.

Wikipedia dice 52 bit del significante, senza contare l'avviamento implicito 1. Questo dovrebbe significare il primo lungo per essere gettato su un valore diverso è 2 ^ 53.

Answer 3

Anche se sono riluttanti a parlare di Fortran 95 e successori in questa discussione, io detto che Fortran poiché lo standard 1990 ha offerto una funzione intrinseca DISTANZA che ti dice quale sia la differenza tra REAL rappresentabili sono circa un dato reale. Si potrebbe fare una ricerca binaria su questo, fermandosi quando distanza (X)> DELTA. Per compilatori che utilizzano lo stesso modello in virgola mobile come quello che ti interessa (probabile che sia lo standard IEEE754), si dovrebbe ottenere gli stessi risultati.

Answer 4

Fuori mano, ho pensato che raddoppia potrebbero rappresentare tutti gli interi (all'interno dei loro limiti) esattamente.

Se questo non è il caso, allora si sta andando a voler lanciare sia i e d per qualcosa con più precisione rispetto a nessuno dei due. Forse un lungo doppio funzionerà.