Нахождение дискретной разницы между близкими числами с плавающей запятой

Предположим, у меня есть два числа с плавающей запятой, x и y, и их значения очень близки.

На компьютере может быть представлено дискретное количество чисел с плавающей запятой, поэтому мы можем перечислить их в порядке возрастания: f_1, f_2, f_3, .... Я хочу найти расстояние между x и y в этом списке (т.е. находятся ли они на 1, 2, 3, ... или n дискретных шагах друг от друга?)

Возможно ли это сделать, используя только арифметические операции (+-*/) и не глядя на двоичное представление? Меня в первую очередь интересует, как это работает на x86.

Правильно ли следующее приближение, если предположить, что y > x и x и y находятся всего в нескольких шагах (скажем, <100) друг от друга? (Возможно нет ...)

(y-x) / x / eps

Здесь eps обозначает машинный эпсилон. (Машинный эпсилон - это разница между 1.0 и следующим наименьшим числом с плавающей запятой.)


floating-point x87 numerical
person Szabolcs    schedule 31.05.2011    source источник
comment
@ShreevatsaR, поэтому я тоже разделил на x (не только на eps). (y-x) / x / eps = (y-x) / (x*eps). Я все еще не уверен, что это правильно.   -  person Szabolcs    schedule 31.05.2011
comment
Ах, ладно, извини. Ваша формула может быть правильной; будем думать. :-) А пока вы можете прочитать Что должен знать каждый компьютерный ученый об арифметике с плавающей запятой < / а>.   -  person ShreevatsaR    schedule 31.05.2011

Ответы (2)


arrow_upward
3
arrow_downward

Поплавки лексикографически упорядочены, поэтому:

int steps(float a, float b){

  int ai = *(int*)&a;  // reinterpret as integer
  int bi = *(int*)&b;  // reinterpret as integer
  return bi - ai;
}

steps(5.0e-1, 5.0000054e-1);  // returns 9

Такой метод используется при сравнении чисел с плавающей запятой.

person Arlen    schedule 16.01.2012
comment
пока числа равны ›0. Некоторая логика все еще необходима для покрытия отрицательных значений и 0 (включая -0). - person Alexey Frunze; 16.01.2012
comment
+1, Интересное наблюдение о лексикографическом упорядочивании. Но что я действительно хотел бы знать, так это то, возможно ли это, используя только арифметические операции с плавающей запятой. Язык, который я использовал, когда спросил об этом, не поддерживает переинтерпретацию битовых шаблонов как другого типа. - person Szabolcs; 16.01.2012
comment
@Szabolcs, какой язык ты использовал? Я написал код на C ++, но он должен работать на C и D. - person Arlen; 16.01.2012
comment
На самом деле мой вопрос касался не того, как это сделать на этом языке, мне просто было любопытно, можно ли это сделать, используя только операции с плавающей запятой, не прибегая к некоторому исследованию битового представления числа с плавающей запятой. Я использовал Mathematica. Даже если это не прямой ответ на мой вопрос, ваш ответ был интересным, и я ценю его (особенно учитывая, сколько лет этому вопросу). - person Szabolcs; 16.01.2012

arrow_upward
1
arrow_downward

Вам не нужно напрямую исследовать двоичное представление, но я думаю, вы должны полагаться на него, чтобы получить точный ответ.

Начните с использования frexp (), чтобы разбить x на экспоненту exp и мантиссу. Я считаю, что следующее число с плавающей запятой больше x - x + eps * 2^(exp-1). («-1» - это потому, что frexp возвращает мантиссу в диапазоне [1/2, 1), а не [1, 2).)

Если x и y имеют одинаковый показатель степени, вы в основном закончили. В противном случае вам нужно посчитать, сколько шагов приходится на степень двойки, что составляет всего 1.0/eps. Другими словами, количество шагов между 2 ^ n и 2 ^ (n + 1) равно 1.0/eps.

Итак, для y> x посчитайте, сколько шагов осталось от x до следующей степени двойки; затем посчитайте, сколько шагов нужно сделать, чтобы получить наибольшую степень двойки, меньшую y; затем посчитайте, сколько еще шагов нужно сделать, чтобы добраться оттуда до y. Я думаю, все это довольно легко выразить в терминах eps.

person Nemo    schedule 31.05.2011