Почему некоторые арифметические операции занимают больше времени, чем обычно?

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

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

const int MAX_ITER = 100000000;

int main(int argc, char *argv[]){
    double x = 1.0, y;
    int i;
    clock_t t1, t2;
    scanf("%lf", &y);
    t1 = clock();
    for (i = 0; i < MAX_ITER; i++)
        x *= y;
    t2 = clock();
    printf("x = %lf\n", x);
    printf("Time: %.5lfsegs\n", ((double) (t2 - t1)) / CLOCKS_PER_SEC);
    return 0;
}

Вот два разных прогона программы:

С y = 0,5

x = 0.000000
Время: 1.32000сек.
С y = 0,9

x = 0.000000
Время: 19.99000segs

Я использую ноутбук со следующими спецификациями для проверки кода:

CPU: процессор Intel® Core ™ 2 Duo T5800 @2.00GHz × 2
ОЗУ: 4 ГБ
ОС: Ubuntu 12.04 (64 бит)
Модель: Dell Studio 1535

Может ли кто-нибудь объяснить подробно, почему это происходит? Я знаю, что при y = 0,9 значение x переходит в 0 медленнее, чем при y = 0,5, поэтому я подозреваю, что проблема напрямую связана с этим.

Ответ 1

Денормальные (или, скорее, субнормальные) числа часто являются хитом производительности. Медленно сходящийся к 0, на ваш второй пример, будет генерировать больше субнормальных значений. Подробнее здесь и здесь. Для более серьезного чтения проверьте часто цитируемый (и очень плотный) Что каждый компьютерный ученый должен знать о арифметике с плавающей точкой.

Из второго источника:

В IEEE-754 числа с плавающей запятой представлены в двоичном формате как:

Number = signbit \* mantissa \* 2exponent

Существует потенциально несколько способов представления одного и того же числа, используя десятичное число в качестве примера, число 0,1 может быть представлено как 1 * 10-1 или 0,1 * 100 или даже 0,01 * 10. Стандарт диктует, что числа всегда сохраняются с первым битом как единым. В десятичном значении соответствует примеру 1 * 10-1.

Теперь предположим, что наименьший показатель, который может быть представлен, равен -100. Поэтому наименьшее число, которое может быть представлено в нормальной форме, равно 1 * 10-100. Однако, если мы расслабляем ограничение, что ведущий бит один, тогда мы можем фактически представлять меньшие числа в одном и том же пространство. Взяв десятичный пример, мы могли бы представить 0,1 * 10-100. Эта называется субнормальным числом. Назначение субнормальных чисел состоит в том, чтобы сгладить зазор между наименьшим нормальным числом и нулем.

Очень важно понять, что обозначены субнормальные числа с меньшей точностью, чем обычные. Фактически, они торгуют уменьшенная точность их меньшего размера. Следовательно, расчеты, которые используют субнормальные числа не будут иметь такую же точность, как расчеты на нормальные числа. Таким образом, приложение, которое делает значительное вычисление на субнормальных числах, вероятно, стоит исследуя, можно ли перемасштабировать (т.е. умножить числа на некоторый коэффициент масштабирования) приведет к меньшему количеству субнормальных значений и более точному Результаты.

Я думал об объяснении этого сам, но приведенное выше объяснение чрезвычайно хорошо написано и кратким.

Ответ 2

Вы получаете измеримую разницу не потому, что 0.9^n математически сходится к 0 медленнее, чем 0.5^n, но поскольку в реализациях с плавающей запятой IEEE-754 она вообще не сходится к 0.

Наименьший положительный double в представлении IEEE-754 равен 2 ^-1074 наименьшая положительная норма равна 2 ^-1021 поэтому при y = 0.5 цикл встречается 53 субнормальных числа. Как только будет достигнуто наименьшее положительное субнормальное значение, следующий продукт будет равен 2 ^-1075 но из-за округленного к округлу округления округления до нуля (IEEE) -754 чисел чисел с плавающей запятой и режима округления округления до последнего бита-нуля по умолчанию довольно повсеместно распространены на стандартном потребительском оборудовании, даже если стандарт не полностью реализован.) С этого момента у вас есть умножение 0*y, который является обычным умножением с плавающей запятой (этот быстрый, даже если y является субнормальным числом).

С 0.5 < y < 1, как только вы достигнете нижнего конца (положительного) субнормального диапазона, результат x*y снова округляется до значения x (для y = 0.9, неподвижная точка итерация 5 * 2 ^-1074). Поскольку это достигается после нескольких тысяч итераций (0.9^7 < 0.5), вы в основном умножаете субнормальное число с ненулевым числом для всего цикла. На многих процессорах такое умножение нельзя обрабатывать напрямую и должно обрабатываться в микрокоде, что намного медленнее.

Если скорость важнее семантики IEEE-754 (или если это нежелательно по другим причинам), многие компиляторы предлагают опции для отключения этого поведения и подсвечивают субнормальные числа до 0, если это поддерживает аппаратное обеспечение. Я не смог найти однозначный вариант на моей странице gcc man, но -ffast-math сделал трюк здесь.