Блог

Мне нужна функция для быстрого сравнения корня квадратичной функции и заданного значения и функция для быстрого сравнения двух корней двух квадратичных функций.

Я пишу первую функцию

 bool isRootLessThanValue (bool sqrtDeltaSign, int a, int b, int c, int value) {
    bool ret;

    if(sqrtDeltaSign){
        if(a < 0){
            ret = (2*a*value   b < 0) || (a*value*value   b*value   c > 0);
        }else{
            ret = (2*a*value   b > 0) amp;amp; (a*value*value   b*value   c > 0);
        }
    }else{
        if(a < 0){
            ret = (2*a*value   b < 0) amp;amp; (a*value*value   b*value   c < 0);
        }else{
            ret = (2*a*value   b > 0) || (a*value*value   b*value   c < 0);
        }
    }
    return ret;
};
 

Когда я пытаюсь написать это для второй функции, она становится очень большой и сложной…

 bool isRoot1LessThanRoot2 (bool sqrtDeltaSign1, int a1, int b1, int c1, bool sqrtDeltaSign2, int a2, int b2, int c2) {
    //...
}
 

Есть ли у вас какие-либо предложения, как я могу упростить эту функцию?

Если вы считаете, что это глупая идея для оптимизации, пожалуйста, скажите мне, почему 🙂

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

 #include <iostream>
#include <cmath> // for main testing
int isRootLessThanValue (int a, int b, int c, int value)
  {
    if (a<0){ b *= -1;  c *= -1;   a *= -1;}
    int xt, delta;
    xt = 2 * a * value   b;
    if (xt < 0) return false; // value is left to reflection point
    delta = b*b - 4*a*c;
 // compare square distance between value and the root
    return  ( (xt * xt) > delta )? true: false;
  }
 

В программе test main () корни сначала вычисляются для наглядности:

 int main()
{
    int a, b, c, v;

    a = -2;
    b = 4;
    c = 3;
    double r1, r2, r, dt;
    dt  = std::sqrt(b*b-4.0*a*c);
    r1 = (-b   dt) / (2.0*a);
    r2 = (-b - dt) / (2.0*a);
    r = (r1>r2)? r1 : r2;
    while (1)
    {
       std::cout << "Input the try value = ";
       std::cin >> v;
       if (isRootLessThanValue(a,b,c,v)) std::cout << v <<" > " << r << std::endl;
       else std::cout << v <<" < " << r  << std::endl;
    }
    return 0;
 }
 

Тестовый запуск

Далее предполагается, что обе квадратичные функции имеют действительные, взаимно отличные корни, и a1 = a2 = 1 . Это упрощает обозначения, хотя в общем случае можно использовать аналогичную логику.

Предположим f(x) = x^2 b1 x c1 , имеет реальные корни u1 < u2 и g(x) = x^2 b2 x c2 имеет реальные корни v1 < v2 . Тогда существует 6 возможных порядков сортировки.

• (1)    u1 < u2 < v1 < v2
• (2)    u1 < v1 < u2 < v2
• (3)    u1 < v1 < v2 < u2
• (4)    v1 < u1 < u2 < v2
• (5)    v1 < u1 < v2 < u2
• (6)    v1 < v2 < u1 < u2

Пусть v будет корнем g так, что g(v) = v^2 b2 v c2 = 0 тогда v^2 = -b2 v - c2 и, следовательно f(v) = (b1 - b2) v c1 - c2 = b12 v c12 , где b12 = b1 - b2 и c12 = c1 - c2 .

Из этого следует Sf = f(v1) f(v2) = b12(v1 v2) 2 c12 , что Pf = f(v1) f(v2) = b12^2 v1 v2 b12 c12 (v1 v2) c12^2 и. Используя отношения Виеты v1 v2 = c2 и v1 v2 = -b2 так в конце Sf = f(v1) f(v2) = -b12 b2 2 c2 и Pf = f(v1) f(v2) = b12^2 c2 - b12 c12 b2 c12^2 . Аналогичные выражения могут быть вычислены для Sg = g(u1) g(u2) и Pg = g(u1) g(u2) .

(Следует отметить, что Sf, Pf, Sg, Pg выше приведены арифметические выражения в коэффициентах, не включающие sqrt квадратные корни. Однако существует вероятность переполнения целых чисел. Если это действительно проблема, то вычисления должны выполняться с плавающей запятой вместо целых чисел.)

• Если Pf = f(v1) f(v2) < 0 тогда ровно один корень f находится между корнями v1, v2 g .
  • Если ось f находится слева от g единицы, то это означает -b1 < -b2 , что это меньший корень u1 f , который находится между v1, v2 , т.е. случай (5).
  • В противном случае, если -b1 > -b2 тогда это больший корень, т.е. случай (2).
• Если Pf = f(v1) f(v2) > 0 тогда либо оба , либо ни один из корней f находятся между корнями g . В этом случае f(v1) и f(v2) должны иметь один и тот же знак, и они будут либо оба отрицательными, если Sf = f(v1) f(v2) < 0 или оба положительными, если Sf > 0 .
  • Если f(v1) < 0 и f(v2) < 0 тогда оба корня v1, v2 g находятся между корнями f , т.е. случай (3).
  • По симметрии, если Pg > 0 и Sg < 0 , то g(u1) < 0 и g(u2) < 0 , так что оба корня u1, u2 f находятся между корнями g , т.е. случай (4).
  • В противном случае последняя комбинация остается f(v1), f(v2) > 0 и g(u1), g(u2) > 0 там, где интервалы (u1, u2) и (v1, v2) не перекрываются. Если -b1 < -b2 ось f находится слева от g единицы, то есть case (1), иначе это case (6).

Как только порядок сортировки между всеми корнями определен, следует сравнение любой конкретной пары корней.

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

 bool isRootLessThanValue (bool sqrtDeltaSign, int a, int b, int c, int value)
{
    const int a_value = a * value;
    const int two_a_b_value = 2 * a_value   b;
    const int a_squared_b = a_value * value   b * value   c;
    const bool two_ab_less_zero = (two_a_b_value < 0);
    bool ret = false;
    if(sqrtDeltaSign)
    {
        const bool a_squared_b_greater_zero = (a_squared_b > 0);
        if (a < 0)
        {
            ret = two_ab_less_zero || a_squared_b_greater_zero;
        }
        else
        {
            ret = !two_ab_less_zero amp;amp; a_squared_b_greater_zero;//(edited)
        }
    }
    else
    {
        const bool a_squared_b_less_zero = (a_squared_b < 0);
        if (a < 0)
        {
            ret = two_ab_less_zero amp;amp; a_squared_b_less_zero;
        }
        else
        {
            ret = !two_ab_less_zero || a_squared_b_less_zero;//(edited)
        }
    }
    return ret;
};  
 

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

Сравните язык ассемблера этой функции с вашим. Также тест. Как я уже сказал, я не ожидаю здесь большой экономии времени, но я не знаю, сколько раз эта функция вызывается в вашем коде.

Я реорганизовал свой код и нашел некоторые возможности 🙂

При вычислении a, b и c я могу сохранить структуру, чтобы получить только a> 0 🙂 и я знаю, что мне нужен маленький или большой корень 🙂

таким образом, функция для сравнения корня со значением возвращается к форме ниже

 bool isRootMinLessThanValue (int a, int b, int c, int value) {
    const int a_value = a * value;
    const int u = 2*a_value   b;
    const int v = a_value*value   b*value   c;
    
    return u > 0 || v < 0 ;
};
bool isRootMaxLessThanValue (int a, int b, int c, int value) {
    const int a_value = a*value;
    const int u = 2*a_value   b;
    const int v = a_value*value   b*value   c;
    
    return u > 0 amp;amp; v > 0;
}
 

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

Ниже приведен код для быстрого (и медленного традиционного) сравнения корня со значением без предположений

 bool isRootLessThanValue (bool sqrtDeltaSign, int a, int b, int c, int value) {
    const int a_value = a*value;
    const int u = 2*a_value   b;
    const int v = a_value*value   b*value   c;
    const bool s = sqrtDeltaSign;
    
    return      (  a < 0  amp;amp;  s amp;amp; u < 0 ) || 
                (  a < 0  amp;amp;  s amp;amp; v > 0 ) || 
                (  a < 0  amp;amp; !s amp;amp; u < 0 amp;amp; v < 0) ||
                (!(a < 0) amp;amp; !s amp;amp; u > 0 ) ||
                (!(a < 0) amp;amp; !s amp;amp; v < 0 ) ||
                (!(a < 0) amp;amp;  s amp;amp; u > 0 amp;amp; v > 0);
};
bool isRootLessThanValueTraditional (bool sqrtDeltaSign, int a, int b, int c, int value) {
    double delta = b*b - 4.0*a*c;
    double calculatedRoot = sqrtDeltaSign ? (-b   sqrt(delta))/(2.0*a) : (-b - sqrt(delta))/(2.0*a);
    return calculatedRoot < value;
};
 

результаты тестирования ниже:

• isRootLessThanValue (оптимизировано): 10000000000 сравнивается за 152,922 с
• isrootlesthanvaluetraditional : 10000000000 сравнивается за 196.168с

Любые предложения, как я могу еще больше упростить функцию isRootLessThanValue? 🙂

Я попытаюсь подготовить функцию для сравнения двух корней разных уравнений

отредактировано::2020-11-30

 bool isRootLessThanValue (bool sqrtDeltaSign, int a, int b, int c, int value) {
const int a_value = a*value;
const int u = 2*a_value   b;
const int v = a_value*value   b*value   c;

return  sqrtDeltaSign ? 
    (( a < 0 amp;amp; (u < 0 || v > 0) ) || (u > 0 amp;amp; v > 0)) :
    (( a > 0 amp;amp; (u > 0 || v < 0) ) || (u < 0 amp;amp; v < 0));
 

};