Трюки с float: быстрое вычисление логарифмов.

Алгоритм быстрого вычисления логарифма, исходя из представления чисел с плавающей точкой

Для быстрого приближенного вычисления некоторых математических функций можно использовать знания о внутреннем устройстве типа float:

union ADVFLOAT
{
  float x;
  struct
  {
    unsigned int mant : 23; /* Mantissa without leading one */ 
    unsigned int exp  : 8;  /* Exponential part */
    unsigned int sign : 1;  /* Indicator of the negative number */
  };
};

Согласно стандарту IEEE 754, число с плавающей точкой будет представлено следующим образом: x = (1 + mant) * 2 ^ (exp - 127). Таким образом, чтобы, например, удвоить число, достаточно сделать следующую операцию:

AdvFloat.exp++;

Модуль числа можно получить, наложив AND'ом маску 0x7FFFFFFF.
Более интересный случай представляет вычисление более сложных математических функций, например, логарифма. Однако, воспользовавшись свойствами логарифма и первым членом "волшебного" ряда Тейлора, легко получить достаточно точный результат:
log2(x) = log2((1 + mant) * 2 ^ (exp - 127)) = log2(1 + mant) + log2(2 ^ (exp - 127)) = = ln(1 + mant) / ln(2) + (exp - 127) = ln(1 + mant) / ln(2) + (exp - 127) = mant * log2(e) + (exp - 127).

Таким образом, функция для вычисления логаримфма выглядит так:

#define LOG2E 1.44269504088896340736f

float fastLog2( float x )
{
  ADVFLOAT ax;
  int exp;

  ax.x = x;
  exp = ax.exp - 127;
  ax.sign = 0;
  ax.exp = 127;

  return (ax.x - 1.0f) * LOG2E + exp;
}

Ошибка обычно появляется лишь во втором-третьем знаке, что весьма неплохо для такой примитивной аппроксимации. Однако, проведя более тщательный математический анализ, можно найти добиться и более высокой точности, если найти менее тривиальные коэффициенты, чем 1.0f и LOG2E. Важно, однако, сохранить линейный или по крайней мере квадратичный характер приближения, иначе весь смысл такой аппроксимации сойдёт на нет.
Приведёную функцию можно использовать и в готовом виде, или же можно ещё более её ускорить, использую побитовые операции. Наконец, логарифм - не единственное, что посчитать приближенно. Например, очень полезно использовать функцию fastSqrt(), построенную на том же принципе приближенного вычисления.

14 апреля 2010

Комментарии [155]