2012-12-05 3 views
11

Вот две реализации функций интерполяции. Аргумент u1 всегда находится между 0. и 1..Свойства 80-разрядных расширенных вычислений точности, начинающихся с аргументов двойной точности

#include <stdio.h> 

double interpol_64(double u1, double u2, double u3) 
{ 
    return u2 * (1.0 - u1) + u1 * u3; 
} 

double interpol_80(double u1, double u2, double u3) 
{ 
    return u2 * (1.0 - (long double)u1) + u1 * (long double)u3; 
} 

int main() 
{ 
    double y64,y80,u1,u2,u3; 
    u1 = 0.025; 
    u2 = 0.195; 
    u3 = 0.195; 
    y64 = interpol_64(u1, u2, u3); 
    y80 = interpol_80(u1, u2, u3); 
    printf("u2: %a\ny64:%a\ny80:%a\n", u2, y64, y80); 
} 

На строгом IEEE 754 с платформы 80-битных long double с, все вычисления в interpol_64() выполняются в соответствии с IEEE 754 с двойной точностью, а в interpol_80() в 80-битной расширенной точностью. Программа печатает:

u2: 0x1.8f5c28f5c28f6p-3 
y64:0x1.8f5c28f5c28f5p-3 
y80:0x1.8f5c28f5c28f6p-3 

Я заинтересован в собственности «результат, возвращаемый функцией, всегда в промежутке между u2 и u3». Это свойство ложно interpol_64(), как показано значениями в main() выше.

Есть ли у объекта шанс быть в состоянии interpol_80()? Если это не так, что такое встречный пример? Помогает ли это, если мы знаем это u2 != u3 или что между ними существует минимальное расстояние? Есть ли способ определить значительную ширину для промежуточных вычислений, при которой свойство будет гарантировано истинным?

EDIT: по всем случайным значениям, которые я пытался использовать, когда промежуточные вычисления выполнялись с расширенной точностью внутри. Если interpol_80() принял аргументы long double, было бы относительно легко построить встречный пример, но здесь речь идет конкретно о функции, которая принимает аргументы double. Это затрудняет создание встречного примера, если таковой имеется.


Примечание: а инструкции x87 генераторные компилятор может генерировать один и тот же код для interpol_64() и interpol_80(), но это по касательной к моему вопросу.

+0

ли вы уверены, что эта программа действительно использует 80 бит точности? Современные процессоры Intel/AMD IIRC имеют встроенные 128 ф. П. Устройств с SSE и друзьями. – fuz

+0

@FUZxxl «128-битные единицы FP» означают векторы двух двухточечных или четырех чисел с одной точностью. Но чтобы ответить на ваш вопрос, да, я уверен. Сборка находится здесь: http://pastebin.com/GaM20WZS –

+0

+1 для контента и презентации –

ответ

2

Да, interol_80() безопасен, давайте продемонстрируем его.

Проблема утверждает, что входы 64bits плавать

rnd64(ui) = ui 

Результат точно (в предположении, * и + математические операции)

r = u2*(1-u1)+(u1*u3) 

Оптимальное возвращаемое значение округляется до 64 бит поплавка

r64 = rnd64(r) 

Как у нас есть эти свойства

u2 <= r <= u3 

Гарантируется, что

rnd64(u2) <= rnd64(r) <= rnd64(u3) 
u2 <= r64 <= u3 

Преобразование в 80bits из u1, u2, u3 являются точными тоже.

rnd80(ui)=ui 

Теперь давайте предположим 0 <= u2 <= u3, то выполнение с неточными операций с плавающей точкой приводит к максимально 4 ошибок округления:

rf = rnd(rnd(u2*rnd(1-u1)) + rnd(u1*u3)) 

Допуская округлить до ближайшего четного, это будет не более 2 ULP от точной стоимость. Если округление выполняется с поплавком 64 бит или 80 бит поплавки:

r - 2 ulp64(r) <= rf64 <= r + 2 ulp64(r) 
r - 2 ulp80(r) <= rf80 <= r + 2 ulp80(r) 

rf64 может быть выключен на 2 ULP так интерпол-64() небезопасно, но что о rnd64(rf80)?
Мы можем сказать, что:

rnd64(r - 2 ulp80(r)) <= rnd64(rf80) <= rnd64(r + 2 ulp80(r)) 

С 0 <= u2 <= u3, то

ulp80(u2) <= ulp80(r) <= ulp80(r3) 
rnd64(u2 - 2 ulp80(u2)) <= rnd64(r - 2 ulp80(r)) <= rnd64(rf80) 
rnd64(u3 + 2 ulp80(u3)) >= rnd64(r + 2 ulp80(r)) >= rnd64(rf80) 

К счастью, как каждый номер в диапазоне (u2-ulp64(u2)/2 , u2+ulp64(u2)/2) мы получаем

rnd64(u2 - 2 ulp80(u2)) = u2 
rnd64(u3 + 2 ulp80(u3)) = u3 

так ulp80(x)=ulp62(x)/2^(64-53)

Таким образом, мы получить доказательство

u2 <= rnd64(rf80) <= u3 

Для u2 < = u3 < = 0, мы можем применить тот же доказательство легко.

Последний изучаемый вопрос - u2 < = 0 < = u3. Если мы вычтем 2 большие значения, результат может быть до ulp (большой)/2, а не ulp (big-large)/2 ...
Таким образом, это утверждение мы сделали не дотягивает больше:

r - 2 ulp64(r) <= rf64 <= r + 2 ulp64(r) 

К счастью, u2 <= u2*(1-u1) <= 0 <= u1*u3 <= u3 и это сохраняется после округления

u2 <= rnd(u2*rnd(1-u1)) <= 0 <= rnd(u1*u3) <= u3 

Таким образом, поскольку добавляемые величины имеют противоположный знак:

u2 <= rnd(u2*rnd(1-u1)) + rnd(u1*u3) <= u3 

То же самое происходит после округления, поэтому мы можем еще раз гарантировать

u2 <= rnd64(rf80) <= u3 

QED

Для полноты мы должны заботиться о denormal входов (постепенное недополнение), но я надеюсь, вы не будете, что порочным с стресс-тестами. Я не буду демонстрировать то, что происходит с теми ...

EDIT:

Вот прослеживание как следующее утверждение было немного приблизительны и породил некоторые комментарии, когда 0 < < = u2 = u3

r - 2 ulp80(r) <= rf80 <= r + 2 ulp80(r) 

Мы можем написать следующие неравенства:

rnd(1-u1) <= 1 
rnd(1-u1) <= 1-u1+ulp(1)/4 
u2*rnd(1-u1) <= u2 <= r 
u2*rnd(1-u1) <= u2*(1-u1)+u2*ulp(1)/4 
u2*ulp(1) < 2*ulp(u2) <= 2*ulp(r) 
u2*rnd(1-u1) < u2*(1-u1)+ulp(r)/2 

Для следующая операция округления, мы используем

ulp(u2*rnd(1-u1)) <= ulp(r) 
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r)/2 + ulp(u2*rnd(1-u1))/2 
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r)/2 + ulp(r)/2 
rnd(u2*rnd(1-u1)) < u2*(1-u1)+ulp(r) 

Для второй части суммы, мы имеем:

u1*u3 <= r 
rnd(u1*u3) <= u1*u3 + ulp(u1*u3)/2 
rnd(u1*u3) <= u1*u3 + ulp(r)/2 

rnd(u2*rnd(1-u1))+rnd(u1*u3) < u2*(1-u1)+u1*u3 + 3*ulp(r)/2 
rnd(rnd(u2*rnd(1-u1))+rnd(u1*u3)) < r + 3*ulp(r)/2 + ulp(r+3*ulp(r)/2)/2 
ulp(r+3*ulp(r)/2) <= 2*ulp(r) 
rnd(rnd(u2*rnd(1-u1))+rnd(u1*u3)) < r + 5*ulp(r)/2 

я не доказал оригинал претензии, но не так далеко ...

+0

Ваш ответ помогает мне более четко рассказать о моем собственном вопросе, но кое-что еще не понимаю. Когда я пытаюсь вычислить себя за разницу между математическими и плавающими версиями выражения 'u2 * (1-u1) + (u1 * u3)', я получаю 'ulp (u2) + ulp (u3) + ulp (u2 + u3) ', первый член - ошибка' u2 * (1-u1) ', вторая - ошибка' (u1 * u3) ', а третья - ошибка, введенная продуктом. Ваш результат 2-полосок кажется лучше, но я не уверен, как вы его получите ... –

+0

@PascalCuoq, вы правы, это было немного быстро ... С предположением 0 <= u2 <= u3, все члены положительны и имеют низкую по величине сумму r, поэтому ulp (u2 * (1-u1)) + ulp (u3 * u1) <= 2 * ulp (r), а округление ограничено ulp/2 после основных операций ... У вас также есть одна ошибка округления при выполнении rnd (1-u1) –

+0

О, в отношении денормалов, нет необходимости беспокоиться: когда 'u1',' u2' и 'u3' являются номерами с двойной точностью, то ни одна из подпунктов -выражения 'u2 * (1.0 - (long double) u1) + u1 * (long double) u3' могут быть« длинной двойной »денормальностью. –

2

Основным источником потери точности в interpol_64 является умножение. Умножение двух 53-битных мантисса дает 105- или 106-бит (в зависимости от того, несет ли бит бит) мантисса. Это слишком велико, чтобы соответствовать 80-битовому расширенному значению точности, поэтому в целом вы также получите потерю точности в 80-битной версии. Количественное определение того, когда это происходит, очень сложно; наиболее легко сказать, что это происходит, когда накапливаются ошибки округления. Обратите внимание, что при добавлении двух терминов также существует небольшой шаг округления.

Большинство людей, вероятно, просто решить эту проблему с помощью функции, как:

double interpol_64(double u1, double u2, double u3) 
{ 
    return u2 + u1 * (u3 - u2); 
} 

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

+0

'u1' 0.025, а не 0.25, поэтому у него больше бит, мантисса 1999999999999a. –

+0

@R .: 'u1' .025, не .25; его значение (а не мантисса) имеет более одного бита. И вопрос заключается не в том, как изменить вычисление для получения результатов в диапазоне, вопрос в том, при каких обстоятельствах вычисление может быть вне пределов досягаемости. –

+0

О, я пропустил это. –