Итерационный реализация мощн (х, п)

Question

Я нашел итеративный реализацию Pow (х, п), которая принимает O (журнал п) и постоянное место, как показано ниже:

double pow(double x, int n) { 
    double left = x; 
    double right = 1; 

    if (n<0) return 1/(x*pow(x,-n-1)); // Avoid binary overflow!!!! 

    if (!n) return 1; 

    while (n>1) 
    { 
     if (n%2==1) right *= left; 
     left = left * left; 
     n = n/2; 
    } 

    return left * right; 
} 

Но я не мог найти какое-либо объяснение этого алгоритма. Я понимаю рекурсивное решение с использованием техники разделения и покорения, и я предполагаю, что это решение использует подобный трюк. Но я не понимаю, почему это работает. Может ли кто-нибудь объяснить этот алгоритм мне? Спасибо!

Answer 1

Этот алгоритм разбивает экспоненту, n, на биты, которые представляют число.

Первая строка обрабатывает отрицательные показатели, вычисляя обратную величину и меняя знак n. не то, что она тянет х^1 из Pow() функции путем вычитания одного,

if (n<0) return 1/(x*pow(x,-n-1)); 

Алгоритм обрабатывает биты, которые равны нулю, заметив, что х^0 = 1 (см эту строку):

if (!n) return 1; 

Цикл while многократно возводит в квадрат x (см. Left = x; left = left * left;), поскольку он делит показатель n на 2. Правильный коэффициент используется для вычисления значения i-го бита при его установке.

while (n>1) 
{ 
    if (n%2==1) right *= left; 
    left = left * left; 
    n = n/2; 
} 

Цикл заканчивается, когда п < = 1, и в этот момент значение левого == х^(2 * я) для г-го бита, а правая == х^(2 * (i- 1)) + ... x^(2 * (in)), для битов, которые являются «включенными».