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

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

$a^n=a\cdot a^{n-1},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));
     }
 }

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

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

$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 шагов: $a^{12}\to a^6\to a^3\to a^2\to a^1\to a^0.$

Для больших n разница в длине цепочки более разительная. В частности $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.
• Сколько шагов требуется для вычисления $a^{30}$ вторым методом?
• Покажите, что второй алгоритм выполняется за логарифмическое по n число шагов, а точнее ограничено сверху $2\cdot {\log }_{2}n$ (еще точнее: в точности равно числу знаков в двоичной записи числа n плюс число единичек в этой записи).
• Объясните, как работает программа 3.