Самое быстрое вычисление суммы x ^ 5 + x ^ 4 + x ^ 3 + x ^ 0 (возможно побитовое?) с x = 16

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

newIndex = nowIndex + 1 + (localChildIndex*X)

x будет, например: X = 45 + 44 + 43 + 42 +4< суп>0.

Примечание: 4 — это коэффициент ветвления. На самом деле это будет 16, так что степень 2. Это должно быть полезно для использования побитового материала?

Было бы очень плохо, если бы потребовался цикл для вычисления X (performancewise) и таких вещей, как деление/умножение. Это кажется интересной задачей, которую я не смог придумать как-то красиво.

Поскольку это часть обхода дерева, возможны 2 режима: абсолютный расчет, независимый от предыдущих вычислений, И инкрементальный расчет, который начинается с того, что в переменной хранится высокий X, а затем с каждым более глубоким уровнем дерева выполняются некоторые минимальные действия. .

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


c optimization math assembly hpc
person user1610743    schedule 03.01.2014    source источник
comment
Просто чтобы уточнить: ^ это мощность или xor?   -  person Mysticial    schedule 03.01.2014
comment
Личность: X^n + X^(n-1) + ... + X^1 + X^0 = {X^(n + 1) - 1} / {X - 1}   -  person Brett Hale    schedule 03.01.2014
comment
Также является переменной x? В противном случае это было бы тривиально.   -  person    schedule 03.01.2014
comment
@Набла - хороший момент. Если x фиксировано, просто рассчитайте один раз и сохраните его.   -  person Chowlett    schedule 03.01.2014
comment
Его сила. Извините, надо было уточнить. Да, x фиксирован, потому что он зависит от коэффициента ветвления (обычно 16). Я тоже думал о справочной таблице. Хотя не уверен.   -  person user1610743    schedule 03.01.2014
comment
Что ж, если x является степенью числа 2, то и x^n тоже. Это просто вопрос установки соответствующего бита в 1...   -  person Oliver Charlesworth    schedule 03.01.2014
comment
(111111)‹‹3 = 1 1111 1000 = десятичное число 1017   -  person deviantfan    schedule 03.01.2014

Ответы (1)


arrow_upward
6
arrow_downward

Я отвечу на это с возрастающей сложностью и общностью.

  • Если x фиксировано равным 16, просто используйте постоянное значение 1118481. Ура! (Назовите это, использование магических чисел — плохая практика)

  • Если у вас есть несколько случаев, известных во время компиляции, используйте несколько констант или даже определений, например:

    #define X_2 63
#define X_4 1365
#define X_8 37449
#define X_16 1118481
...

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

    int _X[MAX_EXPONENT]; // note: give it a more meaningful name :)

    Инициализируйте его, а затем просто получите доступ к известному показателю 2^exp во время выполнения.

    newIndex = nowIndex + 1 + (localChildIndex*_X[exp]);

  • Как предварительно рассчитываются эти значения или как их эффективно вычислять на лету: Сумма X = x^n + x^(n - 1) + ... + x^1 + x^0 представляет собой геометрический ряд и его конечная сумма:

    X = x^n + x^(n - 1) + ... + x^1 + x^0 = (1-x^(n + 1))/(1-x)

  • Что касается побитовых операций, то, как сказал Оли Чарльзворт, если x является степенью числа 2 (в двоичном формате 0..010..0), x^n также является степенью числа 2, а сумма различных степеней два эквивалентны операции ИЛИ. Таким образом, мы могли бы составить выражение вида:

    Пусть exp будет показателем степени, так что x = 2^exp. (Для 16 exp = 4). Затем,

    X = x^5 + ... + x^1 + x^0
X = (2^exp)^5 + ... + (2^exp)^1 + 1
X = 2^(exp*5) + ... + 2^(exp*1) + 1

    теперь побитовое, 2^n = 1<<n

    X = 1<<(exp*5) | ... | 1<<exp | 1

    In C:

    int X;
int exp = 4; //for x == 16
X = 1 << (exp*5) | 1 << (exp*4) | 1 << (exp*3) | 1 << (exp*2) | 1 << (exp*1) | 1;

  • И, наконец, я не могу не сказать: если бы ваше выражение было более сложным и вам нужно было вычислить произвольный многочлен a_n*x^n + ... + a_1*x^1 + a_0 от x, вместо реализации очевидного цикла, более быстрый способ вычислить многочлен — это использовать правило Хорнера.

person DSquare    schedule 03.01.2014