Быстрое 1/X деление (обратное)

Question

Есть ли способ улучшить взаимное (деление 1 по X) относительно скорости, если точность не имеет решающего значения?

Итак, мне нужно рассчитать 1/X. Есть ли способ обхода, поэтому я теряю точность, но делаю это быстрее?

Answer 1

Во-первых, убедитесь, что это не случай преждевременной оптимизации. Вы знаете, что это ваше узкое место?

Как Мистический говорит, 1/x можно рассчитать очень быстро. Убедитесь, что вы не используете тип данных double для 1 или делителя. Поплавки намного быстрее.

Это говорит, бенчмарк, бенчмарк, бенчмарк. Не тратьте свое время на часовые часы на численную теорию, чтобы обнаружить, что источником плохой работы является доступ к IO.

Answer 2

Прежде всего, если вы включите оптимизацию компилятора, компилятор, скорее всего, оптимизирует вычисление (например, вытащить его из цикла). Чтобы увидеть эту оптимизацию, вам нужно создать и запустить в режиме Release.

Подразделение может быть тяжелее, чем умножение (но комментатор указал, что обратные так же быстро, как умножение на современные процессоры, и в этом случае это неверно для вашего случая), поэтому, если у вас есть 1/X, внутри цикла (и более одного раза), вы можете помочь, кэшируя результат внутри цикла (float Y = 1.0f/X;), а затем используя Y. (Оптимизация компилятора может сделать это в любом случае.)

Кроме того, некоторые формулы могут быть переработаны для удаления деления или других неэффективных вычислений. Для этого вы можете опубликовать более крупное вычисление. Даже там сама программа или алгоритм иногда могут быть реструктурированы, чтобы предотвратить частое попадание вредных циклов.

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

Однако, в общем, нет возможности ускорить деление. Если бы это было, компиляторы уже это делали.

Answer 3

Самый быстрый способ, которым я знаю, - использовать операции SIMD. http://msdn.microsoft.com/en-us/library/796k1tty(v=vs.90).aspx

Answer 4

Я считаю, что то, что он искал, является более эффективным способом аппроксимации 1.0/x вместо некоторого технического определения приближения, в котором говорится, что вы можете использовать 1 как очень непростой ответ. Я также считаю, что это удовлетворяет это.

__inline__ double __attribute__((const)) reciprocal(unsigned long long x) { 
    //The type is unsigned long long, but you are restricted to a max value of 2^32-1, not 
    // 2^64-1 like the unsigned long long is capable of storing 
    union { 
     double dbl; 
     unsigned long long ull; 
    } u = {.dbl=(x*=x)};  // x*x = pow(x, 2) 
    u.ull = (0xbfcdd6a18f6a6f52ULL - u.ull) >> (unsigned char)1; 
           // pow(pow(x,2), -0.5) = pow(x, -1) = 1.0/x 
           // This is done via the 'fast' inverse square root trick 
    return u.dbl; 
} 

__inline__ double __attribute__((const)) reciprocal(double x) { 
    union { 
     double dbl; 
     unsigned long long ull; 
    } u; 
    u.dbl = x; 
    u.ull = (0xbfcdd6a18f6a6f52ULL - u.ull) >> (unsigned char)1; 
            // pow(x, -0.5) 
    u.dbl *= u.dbl;     // pow(pow(x,-0.5), 2) = pow(x, -1) = 1.0/x 
    return u.dbl; 
} 

__inline__ float __attribute__((const)) reciprocal(float x) { 
    union { 
     float dbl; 
     unsigned uint; 
    } u; 
    u.dbl = x; 
    u.uint = (0xbe6eb3beU - u.uint) >> (unsigned char)1; 
            // pow(x, -0.5) 
    u.dbl *= u.dbl;     // pow(pow(x,-0.5), 2) = pow(x, -1) = 1.0/x 
    return u.dbl; 
} 

Хм ....... я wounder если процессор производит знал, что вы могли бы получить обратное только с одной многократно , вычитание и бит-сдвиг, когда они спроектировали CPU .... хм .........

Что касается Разметка, аппаратных х инструкции в сочетании с инструкциями аппаратного вычитательных так же быстро, как аппаратные средства 1,0/х инструкция на современных дневных компьютерах (мои тесты были на i7 Intel, но я предполагаю, аналогичные результаты для других процессоров). Однако, если бы этот алгоритм был внедрен в аппаратное обеспечение в качестве новой инструкции по сборке, то увеличение скорости, вероятно, было бы достаточно хорошим, чтобы эта инструкция была вполне практичной.

И, наконец, эта реализация основана на замечательном "fast" inverse square root algorithm.

Answer 5

Это должно сделать это с количеством предварительно развернутых итераций Ньютона оценивается как полином Хорнера, который использует слит-кратно аккумулировать операции самый современный день процессора выполнять в одном цикле Clk (каждый раз):

float inv_fast(float x) { 
    union { float f; int i; } v; 
    float w, sx; 
    int m; 

    sx = (x < 0) ? -1:1; 
    x = sx * x; 

    v.i = (int)(0x7EF127EA - *(uint32_t *)&x); 
    w = x * v.f; 

    // Efficient Iterative Approximation Improvement in horner polynomial form. 
    v.f = v.f * (2 - w);  // Single iteration, Err = -3.36e-3 * 2^(-flr(log2(x))) 
    // v.f = v.f * (4 + w * (-6 + w * (4 - w))); // Second iteration, Err = -1.13e-5 * 2^(-flr(log2(x))) 
    // v.f = v.f * (8 + w * (-28 + w * (56 + w * (-70 + w *(56 + w * (-28 + w * (8 - w))))))); // Third Iteration, Err = +-6.8e-8 * 2^(-flr(log2(x))) 

    return v.f * sx; 
} 

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