Более быстрый способ нахождения кратного двойного

Question

Если имеется следующая функция C, используемая для определения, является ли одно число кратным другого, для произвольного допуска

#include <math.h>

#define TOLERANCE 0.0001

int IsMultipleOf(double x,double mod)
{
    return(fabs(fmod(x, mod)) < TOLERANCE);
}

Он отлично работает, но профилирование показывает, что оно очень медленное, в том смысле, что оно стало кандидатом на оптимизацию. Около 75% времени тратится на modulo, а оставшееся время на fabs. Я пытаюсь найти способ ускорить процесс, используя что-то вроде справочной таблицы. Параметр x меняется регулярно, тогда как mod меняется нечасто. Число возможных значений x достаточно мало, чтобы пространство для поиска не было проблемой, обычно это будет одно из нескольких сотен возможных значений. Я могу легко избавиться от fabs, но не могу найти разумную альтернативу по модулю. Любые идеи о том, как оптимизировать выше?

Редактировать Код будет работать на многих настольных и мобильных устройствах Windows, поэтому процессоры могут включать Intel, AMD для настольных ПК и ARM или SH4 для мобильных устройств. VisualStudio 2008 - это компилятор.

Answer 1

Вы действительно должны использовать modulo для этого?

Не было бы возможно просто result = x / mod и затем проверить, близка ли десятичная часть result к 0. Например:

11 / 5.4999 = 2.000003  ==> 0.000003 < TOLERANCE 

Или что-то в этом роде.

Answer 2

Может быть, вы можете избежать длинных длинных вместо двойных, если у вас есть сопоставимый масштаб данных.Например, long long будет достаточно для 60 астрономических единиц в микрометровом разрешении .

Answer 3

Я вообще не проверял это, но, насколько я понимаю, fmod это должно быть эквивалентно встроенному, что может позволить компилятору оптимизировать его лучше, хотя я бы подумал, что математическая библиотека (или встроенные) компилятора будет работать простотакже.(также я даже не знаю наверняка, если это правильно).

#include <math.h>

int IsMultipleOf(double x, double mod) {
    long n = x / mod;  // You should probably test for /0 or NAN result here
    double new_x = mod * n;
    double delta = x - new_x;
    return fabs(delta) < TOLERANCE;  // and for NAN result from fabs
}

Answer 4

Я думаю, вам нужно проверить внутренности вашей функции C RTL fmod(): FPU X86 имеет инструкции ' FPREM / FPREM1 ', которые вычисляют остатки путем повторного вычитания.

Хотя деление с плавающей запятой - это отдельная инструкция, вам, возможно, придется неоднократно вызывать FPREM, чтобы получить правильный ответ для модуля, поэтому ваш RTL может его не использовать.

Answer 5

Следующее, вероятно, является излишним и неоптимальным. Но то, что это стоит, - это один из способов сделать это.

Мы знаем формат двойного ...

• 1 бит для знака
• 11 битов для смещенного показателя
• 52 битовых дроби

Пусть ...

• значение = х / мод;
• exp = показательные биты значения - BIAS;
• lsb = младший бит битов дробного значения;

Как только вы получите это ...

/*
 * If applying the exponent would eliminate the fraction bits
 * then for double precision resolution it is a multiple.
 * Note: lsb may require some massaging.
 */
if (exp > lsb)
    return (true);

if (exp < 0)
    return (false);

Единственный оставшийся случай - это случай допуска. Постройте свой двойник, чтобы избавиться от всех цифр слева от десятичной дроби.

• знаковый бит равен нулю (положительный)
• экспонента - это БИАС (1023, думаю ... посмотрите, чтобы убедиться)
• сдвинуть биты дроби соответствующим образом

Теперь сравните это с вашей терпимостью.

Answer 6

Деление (с плавающей запятой или нет, fmod в вашем случае) часто является операцией, в которой время выполнения сильно варьируется в зависимости от процессора и компилятора:

• GCC имеет встроенную замену для
  что если вы дадите ему правильную компиляцию флаги или если вы используете __builtin_fmod в явном виде. Это тогда может отобразить операция на небольшом количестве Инструкция по сборке.
• там могут быть специальные единицы, такие как SSE на процессорах Intel, где это операция реализована более эффективно

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

Answer 7

Я полагаю, что модуль выглядит примерно так внутри:

mod(x,m) {
  while (x > m) {
    x = x - m
  }
  return x
}

Я думаю, что с помощью какого-то поиска я мог бы быть оптимизирован: например:

fastmod(x,m) {
  q = 1

  while (m * q < x) {
    q = q * 2
  }

  return mod((x - (q / 2) * m), m)
}

Вы можетедаже решили заменить последний вызов мода на другой вызов fastmod, добавив условие, что если x

Answer 8

Требуется ли для двойной точности?В зависимости от того, насколько хороша ваша математическая библиотека, она должна быть быстрее:

#include <math.h>

#define TOLERANCE 0.0001f

bool IsMultipleOf(float x, float mod)
{
    return(fabsf(fmodf(x, mod)) < TOLERANCE);
}