Как вернуть ближайший элемент из упорядоченного набора?

Question

У меня есть вектор, который содержит некоторые значения с плавающей запятой, разумно отделенные друг от друга и отсортированные по некоторой функции. Например,

double foo(double x) 
{ 
    return 199.1*x; 
} 
double x = 3000000.3157; 
double y = x + DBL_EPSILON; 

std::vector<double> s { y,y+10}; 
std::sort(s.begin(),s.end(),[](double x,double y) { return foo(x) < foo(y) ;}); 

Теперь кто-то есть ключ, который близок к тому, я имею в s, такой, как x. В эпоху lambda, все они имеют свои собственные мало функцию поиска, как

std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x, 
[] (double x,double y) { return foo(x) < foo(y);}))<<std::endl; 
    std::cout<<std::distance(s.begin(),std::lower_bound(s.begin(),s.end(),x, 
[] (double x,double y) { double f1 = foo(x); 
         double f2 = foo(y); 
         return f1 < f2;}))<<std::endl; 

и получает другую позицию (и соответствующие значения сильно отличаются).

Глядя на использование, оказалось, что они связаны с нахождения для ключа k

• Ближайший элемент из упорядоченного набора хорошо размещенных значений с плавающей точкой.
• Соотношение, r, который (в идеале должен быть [0,1]), прикрепленные к последовательным значениям x1 & x2 таким образом, что возвращаемое значение функции f(x1,x2,r) примерно равно k.

Оба они похожи на связанные и связанные с интерполяцией. Как их реализовать?

Примечание:

В короткий код ниже

double f1 = foo(x); 
double f2 = foo(y); 
bool l = foo(x) < foo(y); 
std::cout<<std::boolalpha<<(f1<f2)<< " "<<l<<" "<<(f1 == f2) << std::endl; 
std::cout << std::boolalpha << (foo(x) < foo(y)) << " "<< (foo(y) < foo(x)) 
      << " "<<(foo(x) == foo(y))<<std::endl; 
std::cout << std::boolalpha << std::isless(foo(x) , foo(y)) 
      << " "<< std::isless(foo(y) , foo(x)) <<std::endl; 

я получаю выход с GCC на машине X86, как

false true true 
true true false 
false false 

Хотя я думаю, что GCC делает более высокую точность (80bit) на лету, если я не заставляю его хранить результат, в результате чего получается другой результат для l & (f1<f2) (что вызвало проблему, указанную выше). Мне также будет интересно узнать, почему foo(x) < foo(y) и foo(y) < foo(x) оба говорят true!

Answer 1

Эти два заявления ничего не добиться, потому что DBL_EPSILON меньше 1ulp для этих чисел:

double x = 3000000.3157; 
double y = x + DBL_EPSILON; 

Чтобы быть уверенным, я напечатал шестнадцатеричное представление как x и y и получил следующее:

4146E3602868DB8C 
4146E3602868DB8C 

Когда я запускаю пример в нижней части вашего вопроса через пару разных версий G ++ (4.4.5 и 4.8.0) с оптимизацией как на (-O3), так и off (без флагов), я получаю следующий вывод :

false false true 
false false true 
0 0 

Я подозреваю, что поведение, которое вы видите, это именно по той причине, вы постулировать: Ваш компилятор проводит большую точность промежуточных результатов и кровоточит до этих сравнений.

Какую версию компилятора вы используете, а другой код в приложении регулирует любой из режимов округления? Какие флагов компиляции вы используете?

---

EDIT 1

Я был в состоянии воспроизвести свое поведение перекомпиляцией с оптимизацией от и в 32-битном режиме. В этом режиме, я вижу, что компилятор оставляет результат из foo в стек с плавающей точкой:

_Z3food: 
.LFB1053: 
    .cfi_startproc 
    pushl %ebp # 
    .cfi_def_cfa_offset 8 
    .cfi_offset 5, -8 
    movl %esp, %ebp #, 
    .cfi_def_cfa_register 5 
    subl $8, %esp #, 
    movl 8(%ebp), %eax # x, tmp61 
    movl %eax, -8(%ebp) # tmp61, x 
    movl 12(%ebp), %eax # x, tmp62 
    movl %eax, -4(%ebp) # tmp62, x 
    fldl -8(%ebp) # x 
    fldl .LC0 # 
    fmulp %st, %st(1) #, 
    leave 

Это говорит о том, что это причуда i386 ABI. Чтобы проверить эту теорию, я более внимательно посмотрел на i386 ABI. На page 38 of this PDF (. Ака «страницы 3-12» по внутренним номерам страниц), я считаю, что, скорее всего, дымящийся пистолет:

%st(0)возвращение с плавающей точкой значения появляются на верхней части плавающей стек регистров точек; нет никакой разницы в представлении значений одиночной или двойной точности в регистры с плавающей запятой . Если функция не возвращает значение с плавающей запятой, , то этот регистр должен быть пустым. Этот регистр должен быть пуст перед вводом функции G .

Он продолжает говорить несколько абзацев позже: на вершине стека регистров Intel387 появляется

с плавающей точкой возвращаемого значения. Затем вызывающий должен удалить значение из стека Intel387 , даже если оно не использует значение. Неспособность стороны выполнить свои обязательства ведет к неопределенному поведению программы. Стандартная вызывающая последовательность не содержит никакого способа обнаружения таких ошибок или определения несоответствий типа возвращаемого значения. Поэтому пользователь должен объявить все функции должным образом. В нет различий в представлении значений одиночной, двойной или расширенной точности в с плавающей запятой.

Поиск дальнейших ссылок на страницы 3-27 (PDF стр. 53) и 3-28 (PDF стр. 54) дает следующие запутывающие повороты. Таблица на рисунке 3-30 предполагает, что начальный режим округления «53-бит (двойная точность)», и что это режим при инициализации процесса.

Он идет дальше, чтобы дать следующее предупреждение на следующей странице:

Начальное состояние с плавающей точкой должна быть изменена с осторожностью. В частности, в многие операции с плавающей запятой могут вызывать неопределенное поведение , если для управления точностью установлено менее 53 бит. Процедура _fpstart (см. Главу 6) изменяет контроль точности на 64 бит и задает все исключения, которые необходимо задать. Это состояние по умолчанию , необходимое для соответствия стандарту ANSI C и стандарту IEEE 754 с плавающей точкой.

A couplereference с в сети указывают Linux, действительно установить x87 для расширенной точности (по крайней мере, в 32-битного ABI).

---

EDIT 2

Он оказывается протяженным точность действительно преступник. Я добавил следующий код теста, as suggested by this page:

void set_fpu (unsigned int mode) 
{ 
     asm ("fldcw %0" : : "m" (*&mode)); 
} 

// ... 

set_fpu(0x27F); 

С этими строками добавлены, тестовый пример возвращает то же значение, которые я видел с 64-битным ABI.

Итак, предполагая, что вы компилируете 32-разрядную программу под Linux, это, по-видимому, является причиной того, что вы видите странные результаты сравнения и сортировки.

Можете ли вы повторно запустить свой код сортировки и поиска с FPU, установленным на 53-битную точность, как я сделал выше, и посмотреть, устраняет ли это различия между двумя вашими лямбда-выражениями?