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

Так же, как следование до комментариев к эффективности возведения в степень путем обработки на квадрат.

преимущество того подхода состоит в том, что он выполняет в журнале (n) время. Например, если бы Вы собирались вычислить что-то огромное, такое как x^1048575 (2^20 - 1), только необходимо пройти цикл 20 раз, не 1 миллион + использование наивного подхода.

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

Редактирование:

я предполагаю, что должен разъясниться, прежде чем кто-то отметит меня для потенциала для переполнения. Этот подход предполагает, что у Вас есть своего рода hugeint библиотека.

Чрезвычайно специализированный случай, когда Вы должны сказать 2^ (-x y), где x, конечно, отрицательно, и y является слишком большим, чтобы сделать смещение на интервале. Можно все еще сделать 2^x в постоянное время путем завинчивания с плаванием.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

можно получить больше полномочий 2 при помощи двойного как базовый тип. (Большое спасибо к комментаторам для помощи придать этому сообщению квадратную форму далеко).

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

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

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

, Например, если Вы хотите вычислить x^15, метод возведения в степень обработкой на квадрат даст Вам:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

Это - в общей сложности 6 умножения.

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

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

нет никаких эффективных алгоритмов для нахождения этой оптимальной последовательности умножения. От Википедия :

проблема нахождения самой короткой дополнительной цепочки не может быть решена динамическим программированием, потому что это не удовлетворяет предположение об оптимальной подструктуре. Таким образом, не достаточно разложить питание на меньшие полномочия, каждое из которых вычисляется минимально, так как дополнительные цепочки для меньших полномочий могут быть связаны (для совместного использования вычислений). Например, в самой короткой дополнительной цепочке для aВ№вЃµ выше, подпроблема для aвЃ ¶ должна быть вычислена как (aВі) ВІ, так как aВі снова используется (в противоположность, скажем, aвЃ ¶ = aВІ (aВІ) ВІ, который также требует три, умножается).