Возведение в степень не работает

124
02 февраля 2021, 12:10

Обычная задача по возведению в степень. Есть 2 функции. Подскажите, почему при значениях x = 0.00001 n = 2147483647 работает только первая (вторая не проходит по времени)? ведь идет простое перемножение.

double myPow1(double x, int n) {
    if(n==1)
        return x;
    if(n==0)
        return 1;
    if(n==-1)
        return 1/x;
    if(n==2)
        return x*x;
    return myPow(myPow(x, n/2), 2)* myPow(x, n%2);
}
double myPow2(double x, int n){
    double result = 1;
    if (n>=0){
        while (n-->=1) {
            result *= x;
        }
    }
    else {
        while (n++<0) {
            result /= x;
        }
    }
    return result;
}
Answer 1

Первая работает за О(log2(n)), вторая за О(n). Допустим нужно 2 ^ 16. Первая посчитает это (((2 ^ 2) ^ 2) ^ 2) ^ 2. Итого 4 действий. 4 = log2(16). На самом деле их несколько больше, но логарифмическая зависимости остаётся. Для 2147483647 понадобится порядка log2(2147483647) = 31 операций. Во втором же способе будет честно 2147483647 умножений. Правда ответ будет достаточно неверный ни там, ни там. Он просто в double не влезет. Минимальное положительное число у double ≈ 2.2*e-308. А 0.00001 ^ 2147483647 сильно меньше.

READ ALSO
передача в ostream объекта

передача в ostream объекта

Есть такой код

100
Как прибавить +1 к числовому содержимому HTML элемента?

Как прибавить +1 к числовому содержимому HTML элемента?

есть вот в каждом комментарии такая ссылка,при нажатии которой отправляется post запрос следующим кодом

157
Помогите сделать авторизацию на сайте

Помогите сделать авторизацию на сайте

я сделал регистрацию а как сделать заход на сайт то есть login in не понимаю помогите плиз

124
Динамическая загрузка javascript кода

Динамическая загрузка javascript кода

В html имеем следующий код:

140