Матьиматика

[OKTA]

А что даст корень уравнения?

[Igors]

А что даст корень уравнения?

Корень и есть "какое y соответствует данному x". Но вот считать его для каждой точки - подозреваю будет накладно. Кстати ф-ция немонотонна и неизвестно правильно ли это вообще.

Да, и возможна ситуация когда одному x соответствует неск y, т.е. результат не определен. Поэтому по-простому-народному выберите диапазон y (напр от 0 до 10), там все монотонно, создайте массив напр 1000 значений x и спокойно находите через lower_bound

[m_ax]

А что даст корень уравнения?

Корень и есть "какое y соответствует данному x". Но вот считать его для каждой точки - подозреваю будет накладно. Кстати ф-ция немонотонна и неизвестно правильно ли это вообще.

Да, и возможна ситуация когда одному x соответствует неск y, т.е. результат не определен. Поэтому по-простому-народному выберите диапазон y (напр от 0 до 10), там все монотонно, создайте массив напр 1000 значений x и спокойно находите через lower_bound

Функция как раз монотонна, и однозначна (во всяком случае для x >= 0). Бисекшин - достаточно быстрый метод, никаких "накладно" вы там не заметите..   

Поэтому по-простому-народному выберите диапазон y (напр от 0 до 10), там все монотонно, создайте массив напр 1000 значений x и спокойно находите через lower_bound

А вот так лучше как раз не делать)

[Igors]

Функция как раз монотонна, и однозначна (во всяком случае для x >= 0). Бисекшин - достаточно быстрый метод, никаких "накладно" вы там не заметите..  

Ну что Вы мне парите Пусть бисекшин - простая дихотомия, т.е. деление отрезка пополам (иначе еще хуже). Напр 10 шагов - уже 10 раз вычислена exp, а это разложение в ряд и.т.п.

А вот так лучше как раз не делать)

Аргументы?

[OKTA]

Посижу, почитаю, поучусь у умных дядек 

[m_ax]

Ну что Вы мне парите Плачущий Пусть бисекшин - простая дихотомия, т.е. деление отрезка пополам (иначе еще хуже). Напр 10 шагов - уже 10 раз вычислена exp, а это разложение в ряд и.т.п.

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

Аргументы?

А они для Вас не очевидны? Давайте сравним две реализации.. С условием, что вычислять функцию нужно с заданной точностью при любом положительном x. Думаю тогда все вопросы сразу отпадут)
 

[m_ax]

Посижу, почитаю, поучусь у умных дядек 

Рано меня ещё в "дядьки" записывать)

[Igors]

А они для Вас не очевидны? Давайте сравним две реализации.. С условием, что вычислять функцию нужно с заданной точностью при любом положительном x. Думаю тогда все вопросы сразу отпадут)

bisect требует диапазона аргумента (в данном случае y). Откуда Вы его возьмете? Ну напр y = 50, exp(50) - уже "слишком много" чтобы реально использоваться в задаче. Поэтому разговоры о "любом положительном x" неуместны. Более того, на практике часто вообще интересен диапазон [0..1]. Так что давайте реалистичнее, тогда пожалуйста - сравним 

[m_ax]

Откуда Вы его возьмете? Ну напр y = 50, exp(50) - уже "слишком много" чтобы реально использоваться в задаче.

Верхнюю границу y можно оценить, и поверьте, она  50ти никогда не будет равна, для любого разумного x..
Так что разговор уместен)

Более того, на практике часто вообще интересен диапазон [0..1].

Это Вы с потолка опять взяли? А мне нужно график, например от 0 до 1000000.. И что мне с вашим от 0 до 1 делать? Ммм?

 

[Igors]

Это Вы с потолка опять взяли? А мне нужно график, например от 0 до 1000000.. И что мне с вашим от 0 до 1 делать? Ммм?

Я говорю о значениях аргумента (y). exp(100000..) вернет nan. Наверное Вы имеете ввиду график х(y) где макс x - достаточно большое. Ну что ж, потрачу больше памяти чтобы добиться нужной точности. Да, если Вы не поняли (судя по постам) то массив строится 1 раз на этапе предрасчета. Поэтому соревноваться с ним в скорости поиска довольно глупо 

[m_ax]

Я говорю о значениях аргумента (y). exp(100000..) вернет nan.

Я понимаю, о чём Вы говорите.. Я тоже говорю о значениях y..  Ситуации с nan никогда не возникнет, поскольку верхняя граница y для всех разумных x, будет порядка 10, а то и меньше.. Я имею в виду функцию y(x)

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

Давайте, проверим) Выкладывайте свою реализацию "по-народному", а я выложу свою) 
Условие прежние посчитать y(x) для любого положительного x с заданной точностью)

  

[m_ax]

Похоже, народное решение мы не увидим.. Ну да ладно)

Скажу несколько слов о производительности метода bisect..
Написал пробный тест, где сравнивается скорость построения графика нашей функции (exact) y(x) (обратной к y*exp(y))
и очень на неё похожей функции (approx) y = log(1 + x)/1.35. На приаттаченом рисунке они обе изображены.

Переменная x проходит от 0 до 10000 с шагом dx = 1. Результат записывается в файл.

Исходник с замером времени:

Код

C++ (Qt)
#include <iostream>
#include <fstream>
#include <chrono>
 
#include <specmath/roots.h>
 
 
template <class T>
T exact_func(const T & x, const T & err = 0.000001)
{
    static const T e = exp(1);
 
    const T ln_x = log(x);
    const T min = (x < e) ? 0 : 1;
    const T max = (x < e) ? 1 : ln_x;
 
    return specmath::bisect([&](const T& s) { return (x < e) ? (x - s * exp(s)) : (ln_x - s - log(s)); },  min, max, err);
}
 
template <class T>
T approx_func(const T & x)
{
    return log(1 + x)/1.35;
}
 
int main()
{
    double x = 0;
    const double xmax = 10000;
    const double dx = 1;
 
 
    std::ofstream out1("data1.txt");
    std::ofstream out2("data2.txt");
 
    auto start = std::chrono::high_resolution_clock::now();
    while (x < xmax)
    {
        out1 << x << " " << exact_func(x) << std::endl;
        x += dx;
    }
    auto stop = std::chrono::high_resolution_clock::now();
 
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(stop-start).count();
 
    std::cout << " bisection: total time = " << elapsed << "ms" << std::endl;
 
 
 
    x = 0;
    start = std::chrono::high_resolution_clock::now();
    while (x < xmax)
    {
        out2 << x << " " << approx_func2(x) << std::endl;
        x += dx;
    }
    stop = std::chrono::high_resolution_clock::now();
 
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(stop-start).count();
 
    std::cout << "aprox func: total time = " << elapsed << "ms" << std::endl;
 
    return 0;
}
 

 

Результаты трёх прогонов следующие:

Код

Bash
 bisection: total time = 58ms
aprox func: total time = 50ms
 
 bisection: total time = 58ms
aprox func: total time = 50ms
 
 bisection: total time = 58ms
aprox func: total time = 51ms
 

Как видно, разница ничтожна..  
"Народный" вариант от igors однозначно проиграл бы по памяти (это мягко говоря), да и по скорости тоже есть сомнения..
Так что делаем выводы..

ЗЫ В примере выше, вместо boost::bisect использовалась более  быстрая её версия.. Но сути это не меняет..

[Igors]

Что-то не то, не так. В approx всего лишь один log, в exact уже до bisect тот же log плюс сам bisect чего-то весит, сколь бы чудесным он ни был. Вычислительная нагрузка в exact по меньшей мере в неск раз больше. Чего же это времена отличаются ненамного? Напечатайте сколько раз зовется функтор bisect, тогда будет ясно

f = ln_x - s - log(s)  // прологарифмированное исходное
f(1) = log(1) - 1 - log(1) = -1  // нижний предел
f(log(x)) = log(x) - x - log(log(x)) < 0 // верхний предел

Похоже bisect'у нечего считать т.к. оба предела < 0

Похоже, народное решение мы не увидим..

Я найду время, просто "не сию минуту" - есть и другие дела 

[m_ax]

Что-то не то, не так. В approx всего лишь один log, в exact уже до bisect тот же log плюс сам bisect чего-то весит, сколь бы чудесным он ни был. Вычислительная нагрузка в exact по меньшей мере в неск раз больше. Чего же это времена отличаются ненамного? Напечатайте сколько раз зовется функтор bisect, тогда будет ясно

Ну вообще то, эти результаты: два графика были построены после запуска этого примера.. Строится всё корректно) Время тоже считается честно)  

f = ln_x - s - log(s)  // прологарифмированное исходное
f(1) = log(1) - 1 - log(1) = -1  // нижний предел
f(log(x)) = log(x) - x - log(log(x)) < 0 // верхний предел

Похоже bisect'у нечего считать т.к. оба предела < 0

Нет, если внимательно посмотреть, то в самой лямбде тоже проверяется условие (x < e) и в зависимости от него выбирается своя схема..
Там всё корректно, иначе результат (график) не получился бы)  

Поменял местами exact и approx.. Результаты не изменились..

[m_ax]

Приаттачиваю проект, на всякий случай..