Плавающая запятая и разные процессоры

[shade]

Рассмотрим выражение:

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y)

Процессор A вычисляет это выражение с точностью +/- 0.00001 (к примеру)
Процессор B вычисляет это выражение с точностью +/- 0.00005
В результате разница между результатом A и результатом B будет +/- 0.00006

Теперь когда мы проверяем

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y) > 0

что эквивалентно тому, что требуется

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) > (tx - Gear2^.X) * (ty - Gear1^.Y)

Допустим что при абсолютной точности (значение (которое мы не полученное аналитическим путем) равно нулю. И оба процессора ошибутся в знаке с вероятностью 50%
А если мы сравниваем следующим образом:

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y) > e

где е = 0.00007 (больше чем 0.00001 + 0.00005), вероятность ошибки в знаке равна 0%

[unC0Rr]

Допустим что при абсолютной точности (значение (которое мы не полученное аналитическим путем) равно нулю. И оба процессора ошибутся в знаке с вероятностью 50%
А если мы сравниваем следующим образом:

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y) > e

где е = 0.00007 (больше чем 0.00001 + 0.00005), вероятность ошибки в знаке равна 0%

Хм... Забавно... Что-то в этом есть... А если значение выражения

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y)

отрицательно? Вообще, смысл в том, чтобы проверить с какой стороны один вектор находится относительно другого... Причём случай равенства значения нулю можно принять за частный случай отрицательного значения Получается, с какой-то точностью принимаем значение за ноль (или, что то же самое, за отрицательное). Таким образом, код опять превращается в бессмысленное

Код: Выделить всё

(tx - Gear1^.X) * (ty - Gear2^.Y) > (tx - Gear2^.X) * (ty - Gear1^.Y) + e

Или я что-то не так понимаю?

[shade]

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

Если разность сравниваемых значений имеет тот же порядок что и e (примерно равны), то возможна ошибка в знаке, НО оба процессора ошибутся одинаково, в отличии от обычного сравнения где каждый процессор ошибается по своему.

Здесь, наверное, нужно пояснить:
Есть два точных значения A и B, из-за ошибок вычисления у нас
на первом процессоре A1 и B1, такие что A - 0.00001 <= A1 <= A + 0.00001 и B - 0.00001 <= B1 <= B + 0.00001
на втором A2 и B2, такие что A - 0.00005 <= A2 <= A + 0.00005 и B - 0.00005 <= B <= B + 0.00005
Берем Е > max(0.00001, 0.00005), например Е = 0.00006

Пусть A = 0.000021 и B = 0.000022, тогда
для первого процессора 0.000011 <= A1 <= 0.000031 и 0.000012 <= B1<= 0.000042
для второго процессора -0.000029 <= A2 <= 0.000071 и -0.000028 <= B <= 0.000062

Применяем формулу A - B > Е
для первого: -0.000001 <= A1 - B1 <= 0.000001, что меньше E, т.е. false
для второго: -0.000001 <= A2 - B2 <= 0.000001, что меньше E, т.е false
Теперь видно: что как бы не ошиблись оба процессора, они оба дадут один результат false
При обычном сравнении может возникнуть такая ситуация:
A1 = 0.000025; B1 = 0.000027 и A1 < B1 (результат false)
A2 = 0.000029; B2 = 0.000028 и A1 > B1 (результат true)
A1 - B1 = -0.000002 < 0.00006; результат false
A2 - B2 = +0.000001 < 0.00006; результат false


PS: в предыдущем посте ошибся (меня отвлекли). е достаточно выбрать большим чем максимальная погрешность каждого процессора.

[unC0Rr]

для первого процессора 0.000011 <= A1 <= 0.000031 и 0.000012 <= B1<= 0.000042
для второго процессора -0.000029 <= A2 <= 0.000071 и -0.000028 <= B <= 0.000062

Применяем формулу A - B > Е
для первого: -0.000001 <= A1 - B1 <= 0.000001, что меньше E, т.е. false
для второго: -0.000001 <= A2 - B2 <= 0.000001, что меньше E, т.е false

А по-моему, получается:
-0.000031 <= A1 - B1 <= 0.000019
-0.000091 <= A2 - B2 <= 0.000099

[shade]

Короче уменьшим для наглядности число нулей

E1 = 0.01 - погрешность первого
E2 = 0.05 - погрешность второго
E = 0.06

A = 0.021; B = 0.022
0.011 <= A1 <= 0.031
0.012 <= B1 <= 0.032
-0.029 <= A2 <= 0.071
-0.028 <= B2 <= 0.072

0.011 - 0.032 <= A1 - B1 <= 0.031 - 0.012
-0.021 <= A1 - B1 <= 0.019 < 0.06

-0.029 - 0.072 <= A2 - B2 <= 0.071 - (-0.028)
-0.101 <= A2 - B2 <= 0.099 > 0.06

Да, видимо E должно быть больше... на полагать 0.1, хотя я уже не уверен (выч мат мы давно проходили...).

А, вспомнил. При сложении/вычитании абсолютные погрешности складываются, т.е. если A1 и B1 с погрешностью E1 = 0.01, то погрешность A1-B1 будет 2*E1 = 0.02, а если A2 и B2 с погрешностью E2 = 0.05, то A2 - B2 с погрешностью 2 * E2 = 0.1 Но в таком случае E1, E2 - это погрешности не процессоров, а самих выражений A и B.
E нужно в таком случае выбирать как E >= E(A) + E(B), где E(A), E(B) погрешности сравниваемых значений A и B соответственно.

В общем проще выбрать некоторую погрешность Е0 и следить, чтобы все (под)выражения вычислялись с погрешностью не более E0.

Короче ищи по ключевым словам "Вычислительная математика" и "Численные методы", можно в библиотеку сходить и найти книжку-учебник по данной теме.

[unC0Rr]

Если честно, то я аспирант по специальности "Математическое моделирование, численные методы и комплексы программ" .)

Так вот о чём я... Погрешность второго компа 0.05, числа A и B более чем в два раза меньше погрешности .) В эдаком случае проще выбрать один результат true или false и считать его всегда верным

Вообще, не вижу, как введение оценки погрешностей поможет правильно определять положение точки относительно вектора. Или даже пусть не совсем правильно, но воспроизводимо на любом компе.

[Sergei I. Gorelkin]

Код: Выделить всё

D := (tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y);
if D > epsilon then       { точка слева от вектора }
else if D < -epsilon then { точка справа от вектора }
else { точка на самом векторе или на его продолжении }


[*vmr]

Вдогонку:
За точность вычисления FPU отвечают 8-11 биты слова управления(CW):
8-9 биты- контроль точности: 00 -24 бита, 01 - зарезервированно, 10 - 53 бита и 11 - 64 бита.Чем меньше точность, тем больше скорость выполнения некоторых команд FPU
10-11 биты- контроль направления округления. 00 - к ближайлему числу, 01 - к минус бесконечности, 10 - к плюс бесконечности, 11 - к нолю (усечение).

Но это только для Intel/AMD
Возможно точности 64-бит вполне хватит чтоб использовать вариант предложеный в предыдущем посте

[unC0Rr]

Код: Выделить всё

D := (tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y);
if D > epsilon then       { точка слева от вектора }
else if D < -epsilon then { точка справа от вектора }
else { точка на самом векторе или на его продолжении }


Т.е. предлагается вместо меньше-или-равно/больше перейти к ответу меньше/равно/больше?

Но это только для Intel/AMD

В том и проблема, что необходима кроссплатформенная программа. Если бы только х86, то никаких проблем: все имеющиеся в округе процессоры, какие я нашёл, считают одинаково.

А вообще, всем спасибо, я решил проблему написанием своей реализации чисел с фиксированной запятой. Спасибо фрипаскалю за перегрузку операторов и прочие вкусности

[shade]

Код: Выделить всё

D := (tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y);
if D > epsilon then       { больше }
else { меньше или равно }

[unC0Rr]

Код: Выделить всё

D := (tx - Gear1^.X) * (ty - Gear2^.Y) - (tx - Gear2^.X) * (ty - Gear1^.Y);
if D > epsilon then       { больше }
else { меньше или равно }

Ещё раз, чем отличается

Код: Выделить всё

if D > epsilon then

от

Код: Выделить всё

if D > 0 then

принципиально? Если epsilon меньше значений X и Y хотя бы на порядок

[shade]

Ну может вы и правы и нет никакой разницы. Разница конечно, есть но в данном случае похоже что она не применима.

Тогда так: у нас есть D и нам нужно проверить его знак.
Допустим, что |D| < 2^30 и задан с точностью до двух знаков после запятой (первая цифра после запятой верная).
Тогда проверим знак D следующим образом:
if Round(D) > 0 then {больше)
else {меньше или равно}

или попробовать перейти на целочисленную арифметику или, действительно, реализовать свою эмуляцию вещественных чисел если производительность не критична.

[Иван Шихалев]

А вообще, всем спасибо, я решил проблему написанием своей реализации чисел с фиксированной запятой.

Самый правильный способ