Язык Си в примерах/Степень числа

Для вычисления функции ${\displaystyle f(n)=a^{n}\,\!}$ есть рекуррентная формула:

${\displaystyle a^{n}=a\cdot a^{n-1},\quad a^{0}=1.\,\!}$

Вот программа, которая основана на этой формуле:

 /* 
   Степень числа: простая рекурсия
 */
 
 #include<stdio.h>
 
 double power(double x, long n) {
    if(n == 0) return 1;
    if(n < 0) return power ( 1.0 / x, -n);
    return x * power(x, n - 1);
 }
 
 void main() {
     double x;
     long n;
     while (scanf ("%lf %ld", &x, &n) == 2) {
        printf("%lf\n", power (x, n));
     }
 }

Приведёный выше пример не будет работать для отрицательных показателей степени (см. третью строку функции "power"). Правильнее было бы так:

 /* 
   Степень числа: простая рекурсия
 */
 
 #include<stdio.h>

 double power(double x, long n) {
    if(n == 0) return 1.0;
    if(n < 0) return 1.0 / (x * power (1.0 / x, n + 1));
    return x * power(x, n - 1);
 }

 void main() {
     double x;
     long n;
     while (scanf ("%lf %ld", &x, &n) == 2) {
        printf("%16.16lf\n", power (x, n));
     }
 }

Но есть более «умная» рекурсивная функция: ${\displaystyle a^{n}=\left\{{\begin{matrix}a\cdots a^{n-1},&{\mbox{if }}n{\mbox{ is odd}}\\(a^{n/2})^{2},&{\mbox{if }}n{\mbox{ is even}}\end{matrix}}\right.\,\!}$

Например, если обозначить стрелочкой ${\displaystyle \to \,\!}$ слово «сводится к », то при вычислении ${\displaystyle a^{12}\,\!}$ для первой рекурсии получим цепочку длины 12:

${\displaystyle a^{12}\to a^{11}\to a^{10}\to a^{9}\to a^{8}\to a^{7}\to a^{6}\to a^{5}\to a^{4}\to a^{3}\to a^{2}\to a^{1}\to a^{0}.\,\!}$

А для второй рекурсии цепочку из 5 шагов: ${\displaystyle a^{12}\to a^{6}\to a^{3}\to a^{2}\to a^{1}\to a^{0}.\,\!}$

Для больших n разница в длине цепочки более разительная. В частности ${\displaystyle a^{10000}\,\!}$ первой рекурсией вычисляется за 10000 шагов, а второй -- за 19 шагов.

 /*
  Программа 2: степень числа -- оптимизированная рекурсия.
 */
 double power(double x, long n)
 {
    if(n == 0) return 1;
    if(n < 0) return power ( 1 / x, -n);
    if(n % 2) return x * power (x, n - 1);
    return power(x * x, n / 2);
 }

 /* 
    Программа 3: cтепень числа -- оптимизированный алгоритм без рекурсии.
 */
 double power(double x, long n)
 {
     double a = 1;
     while(n) {
         if(n % 2) {
             a *= x;
             n--;
         }
         else{  
             x *= x;
             n /= 2;    
         }
     }
     return a;
 }

• Напишите программу, вычисляющую double в степени double.
• Сколько шагов требуется для вычисления ${\displaystyle a^{30}\,\!}$ вторым методом?
• Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху ${\displaystyle 2\cdot \log _{2}n\,\!}$ (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).
• Объясните, как работает программа 3.