альтернатива оператору if в C++

Question

Я работаю над алгоритмом и хочу, чтобы мой код стал более эффективным. В моем коде используются простые арифметические и сопоставления. Однако я хочу заменить операторы if, поскольку они могут занять много времени. код будет работать более миллиона раз, так что даже малейшее улучшение appreciated.please ответ! вот код-

int_1024 sqcalc(int_1024 s,int_1024 f){ 
    f=f*20; 
    s=s-81; 
    s=s-(f*9); 
    if(s>=0){ 
     return 9; 
    } 
    s=s+f; 
    s=s+17; 
    if(s>=0){ 
     return 8; 
    } 
    s=s+f; 
    s=s+15; 
    if(s>=0){ 
     return 7; 
    } 
    s=s+f; 
    s=s+13; 
    if(s>=0){ 
     return 6; 
    } 
    s=s+f; 
    s=s+11; 
    if(s>=0){ 
     return 5; 
    } 
    s=s+f; 
    s=s+9; 
    if(s>=0){ 
     return 4; 
    } 
    s=s+f; 
    s=s+7; 
    if(s>=0){ 
     return 3; 
    } 
    s=s+f; 
    s=s+5; 
    if(s>=0){ 
     return 2; 
    } 
    s=s+f; 
    s=s+3; 
    if(s>=0){ 
     return 1; 
    } 
    s=s+f; 
    s=s+1; 
    if(s>=0){ 
     return 0; 
    } 
} 

я хотел бы заменить, если чеки, так как я думаю, «» они делают алгоритм медленно. любые предложения? int_1024 - это переменная ttmath с 1000 бит, поэтому сохранение на ней может быть хорошим вариантом? Деление или умножение для такого большого числа может быть медленным, поэтому я попытался использовать дополнение, но безрезультатно.

Answer 1

Я не знаю, если он быстрее, но он значительно короче (и легче анализировать).

int k[] = { 17, 15, 13, 11, 9, 7, 5, 3, 1 }; 
int r = 0; 
f *= 20; 
s -= 81; 
s -= f * 9; 
while (s < 0) { 
    s += f; 
    s += k[r]; 
    if (++r == 9) break; 
} 
if (s >= 0) return 9-r; 

Edit: В самом деле, оригинальный плакат придумал хитрый способ оптимизировать этот цикл путем предварительного вычисления суммы констант в k массиве, и по сравнению s против сумм, а не постепенно добавляя их к s.

Редактировать: Я следовал за методом анализа лун-теней, но пришел к другому уравнению. Оригинал форматирования TeX заменены ASCII искусства (я пытался получить MathJax чтобы сделать TeX для меня, но это не работает):

S[0] = s      >= 0 => 9 - 0 
S[1] = S[0] + f + 19 - 2*1 >= 0 => 9 - 1 
S[2] = S[1] + f + 19 - 2*2 >= 0 => 9 - 2 
... 
S[i] = S[i-1] + f + 19 - 2*i >= 0 => 9 - i 

Так рассчитать S[n]:

S[n] = S[n-1] + f + 19 - 2n 
       .-- n 
=> S[n] = s + >  (f + 19 - 2*i) 
       `-- i=1  .-- n 
=> S[n] = s + n(f + 19) - 2 >  i 
          `-- i=1 
=> S[n] = s + n(f + 19) - n(n+1) 
          2 
=> S[n] = s + n(f + 18) - n 

Таким образом, неравенство S[n] >= 0 - квадратичное уравнение в n. Предполагая s < 0, мы хотим, чтобы n был потолком решения квадратичного.

+--       --+ 
    |    _____________ | 
    |   /  2  | 
    | f + 18 - ./(f + 18) + 4s | 
    |   `     | 
n = | --------------------------- | 
    |    2    | 

Так что процедура будет выглядеть примерно так:

f *= 180; 
s -= 81; 
s -= f; 
if (s >= 0) return 9; 
f /= 9; 
f += 18; 
s *= 4; 
int1024_t ff = f; 
ff *= f; 
ff += s; 
ff = ff.Sqrt(); 
f -= ff; 
f += f.Mod2(); 
return 9 - f/2; 

Однако я не уверен, что расход выполнения этих операций над большими целыми объектами стоит реализации заменить простой цикл, показанный выше. (Если вы не ожидаете расширения функции и потребуете гораздо более длинного цикла.)

Чтобы быть быстрее цикла, реализация целочисленного квадратного корня должна была бы сходиться в течение 4 итераций, чтобы превзойти средние ожидаемые 4.5 итерации существующий цикл while. Однако реализация ttmath, по-видимому, не вычисляет целочисленный квадратный корень. Кажется, он вычисляет квадратный корень с плавающей точкой, а затем округляет результат, который, как я предполагал, будет намного медленнее, чем цикл.

Answer 2

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

Теперь функция начинается с

f=f*20; 
s=s-81; 
s=s-(f*9); 
if(s>=0){ 
    return 9; 
} 

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

s + (f+17) >= 0: 8 
s + (f+17) + (f+15) >= 0: 7 
s + (f+17) + (f+15) + (f+13) >= 0: 6 
. 
. 
s + (f+17) + (f+15) + (f+13) + ... + (f+1) >= 0: 0 

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

(s + ((9-n)*f) + (2*n)-1 >= 0)

Давайте переставить, что так п на одной стороне.

(s + (9*f) - (n*f) + (2*n)-1 >= 0)

(s + (9*f) +1 >= (n*f) - (2*n))

(s + (9*f) +1 >= n*(f - 2))

n <= ((s + (9*f) +1)/(f - 2)

Теперь функция имеет диапазон возвращаемых значений для разных входов. На самом деле нас интересуют значения n в диапазоне 0..8: предоставленная функция не определена для входов, которые приведут к n < 0 (см. Выше). Преамбула гарантирует, что мы никогда не увидим входные данные, которые приведут к n > 8. Таким образом, мы можем просто сказать

int_1024 sqcalc(int_1024 s,int_1024 f){ 
    f=f*20; 
    s=s-81; 
    s=s-(f*9); 
    if(s>=0){ 
     return 9; 
    } 
    return (s + (9*f) +1)/(f - 2); 
} 

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

Демонстрация точности на http://ideone.com/UzMZs.

Answer 3

Согласно замечанию OP, то функция пытается найти все значения, которые удовлетворяют неравенству:

N * ((20 * F) + N) <= S 

Для всех N, дано F и S.

Использование алгебры, это выходит чтобы:

1) N^2 + 20Fn - S <= 0 (where N^2 is N*N or sqr(N)) 

ОП должен использовать некоторые константы для F и N и решить алгебраически или искать в Интернете «C++ найти корень квадратного уравнения» (зр?).

Выбрана функция, затем профилируйте функцию и при необходимости оптимизируйте.

Answer 4

Я попытался решить квадратику, и это делает функцию медленнее для больших цифр. Следуя ответом от @ user315052, я сделал этот код.

int_1024 sqcalc(int_1024 s,int_1024 f){ 
int k[] = { 0, 17, 32, 45, 56, 65, 72, 77, 80, 81 }; 
f=f*20; 
s=((f*9)+81)-s; 
int i=0; 
while(s>k[i]){ 
s-=f; 
i++; 
} 
return 9-i; 
} 

в этом коде, вместо вычитания числа, а затем сравнивая с нуля, я непосредственно сравнить его с number.by далеко, это производит самый быстрый results.i может сделать бинарный поиск, хотя ....