关于数值自乘

      如果n与m是正整数，那么m^n就是把m连乘n次，用到了n次乘法运算，这是一个很没有效率的算法，那么我们来进行一下改进。主要思想就是减少乘法的运算次数。
      关键所在就是下面的定义式：
             当n=0时           m^n=1
             当n为偶数时   m^n=(m^k)^2
             当n为奇数时   m^n=m*(m^2k)
      所以在一个递归程序中分成3部分计算就可以了：第一部分看n是否为0；第二部分看n是否是偶数，如果是，就递归求m的n/2次方，算出的结果在平方就是答案了；第三部分看n是否为奇数，例如n=2k+1，m^(2k+1)=m*(m^2k)，那么就递归去算m^2k，得出的结果在与m相乘就得到结果了。
      每一次分成两个部分(m^k或m^2k)之后，都要用一个乘法把(m^k)(m^k)或m(m^2k)算出来，在最坏的情况下，就是n是奇数，m^n=m*(m^2k)，不过，m^2k却是偶数了，下一层递归就会算m^k了，然后用(m^k)(m^k)再算m^2k。因此递归的层数最多就是1+logn层，也就是乘法运算的数目，在n慢慢变大的时候，很容易知道1+logn小于n，所以这个算法的效率比连乘n次要高很多。C语言的代码如下： 

unsigned long  recursive_power(unsigned long m, unsigned long n)
{
           unsigned long temp;
           if (n == 0)
                 return 1;
           else if (n & 0x01UL == 0)
           {
                 temp = recursive_power(m, n >> 1);
                 return temp * temp;
            }
            else
                 return m * recursive_power(m, n-1);
}

        测试程序如下面的代码所示：

#include  <stdio.h></stdio.h>
#include  <stdlib.h></stdlib.h>
int main(void)
{
         char  line[100], *dummy_ptr;
         unsigned long m, n;
         printf("\nM^N Computation (M > 0 and N > 0)\n");
         printf("\nM   = ");
         gets(line);
          m = strtoul(line, &dummy_ptr, 10);
          printf("\nN   = ");
          gets(line);
          n = strtoul(line, &dummy_ptr, 10);
          printf("\n\nM^N = %lu", recursive_power(m, n));
          getchar();
}

      现在问题已经解决了，但是我们如果再多想一想的话，可不可以不用递归就把问题解决呢？
      先以求m^45为例，45的二进制为101101，所以m^45=m^(1*2^5+0*2^4+1*2^3+1*2^2+0*2^1+1*2^0)=[m^(2^5)][m^(2^3)][m^(2^2)][m^(2^0)] 在101101中，值为1的那一位(比如第i位，从右往左为0，1，2，3 ...) ，在m的指数中就有m^(2^i)哪一项。正因为这个缘故，可以依次把m^(2^0)m^(2^1)，... ，m^(2^i)，m^(2^(i+1))，... 求出来，这正好对应着n的二进制表示中从右到左的顺序，如果在n的二进制表示中第i位是1，就把m^(2^i)乘到一个用来保存最终结果的变量中(初值为1)，因此当n的每一位都查完之后，就有了答案。
      如何计算m^(2^0)，m^(2^1)，... ，m^(2^i)，m^(2^(i+1))，... 这些数据呢？看看下面的式子：
                  m^(2^(i+1))＝m^((2^i)*2)=(m^(2^i))^2
      在知道了m^(2^i)的前提下，把其平方就可以得到m^(2^(i+1))。但是m^(2^0)=m^1=m，所以求这些m^(2^i)只不过是求m的自乘而已，换句话说一开始值为m，下一次是m^2，再下次(m^2)(m^2)=m^4，接下去就是(m^4)(m^4)=m^8，... 然后就是看看如何求出n的二进制表示了。这倒是大家知道的常识了，把n用2去除的余数，就是最右面的一位，再用2去除上次得到的结果，商就是下一位了, ...
      我们通过一个表格来看一下如何算m^45：
                          n            m           temp                  说  明
           ----------------------------------------------------------------------------
                        45           m               1                     初  值
                        22         m^2            m           n为奇数，乘入temp
                        11         m^4            m           n为偶数，temp不变
                        05         m^8           m^5       n为奇数，乘入temp
                        02         m^16        m^13      n为奇数，乘入temp
                        01         m^32        m^13      n为偶数，temp不变
                        00         m^64        m^45      n为奇数，乘入temp
          ------------------------------------------------------------------------------

         C语言的代码如下：

unsigned long iterative_power(unsigned long m, unsigned long n)
{
          unsigned long  temp = 1;
          while (n > 0)
          {
                if (n & 0x01UL == 1)
                      temp *= m;
                      m *= m;
                      n >>= 1;
          }
          return temp;
}

       这个程序的while循环最多只会绕1+logn次，每绕一次，最多作两次乘法，一次m自乘，一次m乘入temp，所以最多只做2(1+logn)次乘法，所以速度是很快的，就以m^45为例，传统连乘方式要乘44次，但是利用此算法只乘了14次。