一个求幂算法的研究

在 《计算机算法的设计与分析(The Design and Analysis of Computer Algorithms)》
(机械工业出版社 Alfred V.Aho  && John E.Hopcroft && Jeffrey D.Ullman) 一书中有
一个用化简的 “ALGOL” 描述的求幂算法
  f(n)= n^n 对所有整数 n>= 1 否则 f(n) = 0;
书(p5)中源码如下：
begin
    read r1;
    if r1 <= 0 then write 0
    else
        begin r2 <- r1;
r3 <- r1-1;
while r3 > 0 do
     begin
  r2 <- r2 * r1;
         r3 <- r3 - 1;
     end
   write r2
    end
end
在中文译本的附录中有一个用C语言描述的同样的问题：
代码如下：
#include <iostream>
#include <stdlib.h>
using namespace std;
int nPowerN()
{
int r1;
cin>>r1;
if(r1 <= 0){
  cout << 0;
}
else{
  int r2 = r1;
  int r3 = r1 - 1;
  while(r3 > 0){
   r2 = r2 * r1;
   r3 = r3 - 1;
  }
  cout << r2 << "\n\n";
}
return 0;
}
int main(void)
{
nPowerN();
system("Pause");
return 0;
}
分析其算法时间复杂度为 O(n), 我们是否可以能设计一种更好的算法，以提高效率呢？
答案是肯定的，
在《计算机程序的构造和解释(Structure and Interpretation of Computer Programs)》一书中有解，
此书中给出了一个求p的n次方的快速算法：
      |-> p*p^n-1  当n为奇数时；
p^n = |
      |-> (p^n/2)^2 当n为偶数时；
  需要计算的次数为log n 加上n的二进制表示中1的个数减1，故总共的次数总是会少于2*log n的，
所以其时间复杂度为O(log n).
至于算法的描述可以用Lisp或C/C++等。
用Lisp(Scheme):
(define (expt p n)
  (cond ((= n 0) 1)
        ((even? n) (square (expt p (/ n 2))))
        (else (* p (expt p (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))
(define (square base)
  (* base base))
用C/C++:
unsigned long ValPowerN(int Val, int n)
{
if(n == 0)
  return 1;
else if(n % 2 ){
  n--;
  return (Val * ValPowerN(Val, n));
}
else{
  n /= 2;
  return (ValPowerN(Val, n) * ValPowerN(Val, n));
}
}
若要计算n^n的只需这样调用就行了：(expt n n) or ValPowerN(n, n)
用Lisp(Scheme)描述的，几乎能算出任意的，只要求n是整数就行了；
但是用C/C++描述的，得考虑数据过大或过小时会引起溢出。