Что такое первый двойной, который отклоняется от его соответствующего длинного треугольника?

Question

Я хочу знать первый двойной от 0d вверх, который отклоняется длинной «той же ценности» некоторой дельтой, скажем, 1e-8. Но я здесь не сработал. Я пытаюсь сделать это на C, хотя я обычно использую управляемые языки, на всякий случай. Пожалуйста помоги.

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

Я предполагаю, что проблема в том, что ди бросает я в два раз и, следовательно, d == я и тогда разница всегда равна 0. Как еще я могу обнаружить это правильно - я бы предпочел прикольный C кастинг по сравнению строк, которые будут навсегда.

ANSWER: как мы и ожидали. 2^53 + 1 = 9007199254740993 - первая точка разницы в соответствии со стандартными инструментами C/UNIX/POSIX. Большое спасибо pax за его программу. И я думаю, что математика снова побеждает.

Answer 1

Учет двойных чисел в IEE754 составляет 52 бита, что означает, что они могут точно хранить цифры до (по крайней мере) 2 .

Если ваши длинны 32-разрядные, они будут иметь только (положительный) диапазон от 0 до 2 , поэтому нет 32-битного длинного изображения, которое невозможно представить точно как двойное. Для 64-битной длины это будет (примерно) 2 , поэтому я бы начал там, а не в нуле.

Вы можете использовать следующую программу, чтобы определить, где возникают сбои. В более ранней версии я полагался на то, что последняя цифра в числе, которая непрерывно удваивается, следует последовательности {2,4,8,6}. Тем не менее, я решил в конечном итоге использовать известный доверенный инструмент (bc) для проверки всего числа, а не только последней цифры.

Имейте в виду, что это может быть затронуты действиями sprintf(), а не реальную точность удваивается (я не думаю, что так лично, так как у него не было никаких проблем с определенными номерами до 2).

Это программа:

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

Это продолжает идти до:

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

, который о том, где я ожидал, что он не в состоянии.

Как и в сторону, я первоначально использовались чисел вида 2 ^п но у меня до:

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] 

с размером двойным будучи 8 байт (проверено с sizeof). Оказалось, что эти числа имеют двоичную форму "1000...", которая может быть представлена ​​длиннее с удвоениями. Вот когда я переключился на использование 2 ⁿ -1, чтобы получить лучший бит: все бит.

Answer 2

С другой стороны, я думал, что двойники могут точно представлять все целые числа (в пределах своих границ).

Если это не так, то вы захотите сделать i и d с чем-то более точным, чем любой из них. Возможно, длинный двойной будет работать.

Answer 3

Первый длинный, чтобы быть «неправильным», когда приведение к двойнику не будет отключено на 1е-8, оно будет выключено на 1. Пока двойной может соответствовать длине в его значении, он будет представлять его точно.

Я забыл, сколько битов удваивает для точности и смещения, но это скажет вам максимальный размер, который он мог бы представлять. Первый длинный неправильный должен иметь двоичную форму 10000 ..., поэтому вы можете найти ее намного быстрее, начиная с 1 и сдвига влево.

Википедия говорит о 52 битах в значении, не считая неявного старта 1. Это должно означать, что первый длинный, который должен быть отличен для другого значения, равен 2^53.

Answer 4

Хотя я не решаюсь упомянуть Fortran 95 и преемников в этой дискуссии, я упомянул, что Fortran со стандартного 1990 года предложила внутреннюю функцию SPACING, которая сообщает вам, какая разница между представляемыми REALs относительно данного REAL. Вы можете выполнить двоичный поиск на этом, останавливаясь, когда SPACING (X)> DELTA. Для компиляторов, которые используют ту же модель с плавающей точкой, что и интересующая вас (вероятно, это стандарт IEEE754), вы должны получить те же результаты.