Jakie jest pierwsze podwójne, które różni się od odpowiadającej mu długości o delta?

Question

Chcę poznać pierwsze podwójne od 0 d wzwyż, które różni się o tę samą wartość od jakiejś delty, powiedzmy 1e-8. Niestety tu nie mam. Próbuję to zrobić w C, chociaż zazwyczaj używam języków zarządzanych. Proszę pomóż.

#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; 
     } 
    } 
}

Zgaduję, że chodzi o to, że di rzuca mi się podwoić, a zatem d == I i wtedy różnica jest zawsze 0. W jaki inny sposób można wykryć to prawidłowo - Wolałbym zabawa C rzucanie przez porównanie ciągów, które trwałyby wiecznie.

ODPOWIEDŹ: jest dokładnie taka, jak oczekiwaliśmy. 2^53 + 1 = 9007199254740993 jest pierwszą różnicą w stosunku do standardowych narzędzi C/UNIX/POSIX. Wielkie dzięki dla pax za jego program. I myślę, że matematyka znów wygrywa.

Answer 1

Podwaja w IEE754 mają precyzję 52 bitów, co oznacza, e mogą przechowywać numery dokładnie (co najmniej) 2 .

Jeśli twoje długie są 32-bitowe, będą miały tylko (dodatni) zakres od 0 do 2 , więc nie ma 32-bitowej długości, która nie może być dokładnie odwzorowana jako podwójna. Dla 64-bitowej długości będzie to (w przybliżeniu) 2 , więc zacznę od tego miejsca, nie w punkcie zerowym.

Możesz użyć poniższego programu, aby wykryć, gdzie zaczynają się awarie. Wcześniejsza wersja polegała na tym, że ostatnia cyfra liczby, która stale podwaja się zgodnie z sekwencją {2,4,8,6}. Jednak ostatecznie zdecydowałem się użyć znanego zaufanego narzędzia (bc) do sprawdzenia całkowitej liczby, a nie tylko ostatniej cyfry.

Należy pamiętać, że ten może być dotknięte działaniami sprintf() zamiast rzeczywistej dokładności deblu (I nie sądzę osobiście, ponieważ nie miał żadnych kłopotów z określonych numerów do 2).

To jest program:

#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++; 
    } 
} 

to leci do:

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

która jest o tym, gdzie spodziewałem się, że nie.

Tak na marginesie, ja pierwotnie używane numery od postaci 2 ⁿ ale że dostał mi się do:

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] 

o rozmiarze podwójnego wynosi 8 bajtów (sprawdzone z sizeof). Okazało się, że liczby te mają postać binarną "1000...", która może być reprezentowana przez daleka znacznie dłużej. Wtedy przełączyłem się na używanie 2 ⁿ -1, aby uzyskać lepszy wzór bitowy: wszystkie bity.

Answer 2

Off hand, myślałem, że debel może dokładnie reprezentować wszystkie liczby całkowite (w obrębie ich granic).

Jeśli tak nie jest, to będziecie chcieli rzucić zarówno I, jak i D na coś z większą precyzją niż którykolwiek z nich. Być może długi podwójny zadziała.

Answer 3

Pierwszy, który ma być "niesłuszny", gdy zostanie rzucony do podwójnego, nie zostanie wyłączony przez 1e-8, zostanie wyłączony o 1. Tak długo, jak podwójny może pasować do długiego w swoim znaczeniu, będzie go reprezentował dokładnie.

Zapomniałem dokładnie, ile bitów ma podwójność dla precyzji względem odsunięcia, ale to wskaże maksymalny rozmiar, jaki może reprezentować. Pierwszy błąd, który powinien być długi, powinien mieć postać binarną 10000 ..., więc możesz go znaleźć znacznie szybciej, zaczynając od 1 i przesunięcia w lewo.

Wikipedia podaje 52 bity w znaczeniu, nie licząc domyślnego początku 1. To powinno oznaczać, że pierwszym długim rzutem do innej wartości jest 2^53.

Answer 4

Mimo, że nie zgadzam się z Fortranem 95 i następcami tej dyskusji, wspomnę, że Fortran od 1990 roku oferował wewnętrzną funkcję PRZESTRZENI, która mówi ci, jaka jest różnica między reprezentowanymi PRAWDZIWYMI REALami. Możesz wykonać wyszukiwanie binarne, zatrzymując się, gdy SPACING (X)> DELTA. W przypadku kompilatorów, które używają tego samego modelu zmiennoprzecinkowego, niż ten, który jest zainteresowany (prawdopodobnie jest to standard IEEE754), należy uzyskać takie same wyniki.