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

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

#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 сделал трюк здесь.