pow(double a, unsigned int n)的实现

看到一篇要求实现pow(double a, double b)幂运算的面试题有感而发，经过研究实现了其中简单的部分，即指数的整数部分。但是指数可能比较大，例如指数是50000，自乘50000次显然是浪费时间的。这里可以把指数n拆分成多项式n = t + 2 ^ k，其中t是非负整数，k是log2(n)的整数部分。但是我不打算用log函数，避免使用math库，而且该计算的时间复杂度为log(n)，于是手动计算：

a ^ n = a ^ (t + 2 ^ k)
      = (a ^ t) * [a ^ (2 ^ k)]

t如果大于0就继续用a ^ n代入a ^ t

这里的a ^ (2 ^ k)只需要循环k次，而k必然小于n，时间复杂度为log(n)，展开式整体仍然是log(n)

int globalCount = 0;

long double powByPow2(long double a, unsigned long k) {
    long double result = a;
    for (unsigned long i = 0; i < k; i++) {
        result *= result;
        globalCount++;
    }
    return result;
}

unsigned long powOf2l(unsigned int index) {
    unsigned long result = 1;
    while (index > 0) {
        result <<= 1;
        index--;
        //globalCount++;  //这里虽然也有循环，但是没有底数自乘的运算
    }
    return result;
}

void modAndPow(long double a, unsigned int n, unsigned int *k, unsigned int *t, long double *result) {
    unsigned int index = 0;
    long temp = ceill(n);
    while (temp > 1) {
        temp >>= 1;
        index++;
    }
    unsigned int pow2 = (unsigned int)powOf2l(index);
    *result = powByPow2(a, index);
    *k = index;
    *t = n - pow2;
}

long double myPowl(long double a, unsigned int n) {
    if (a == 0) {
        if (n == 0) {
            return 1;
        } else {
            return 0;
        }
    }
    if (n == 0) {
        return 1;
    }
    long double result = 1;
    unsigned int temp = n;
    while (temp > 0) {
        unsigned int k, t;
        long double tempResult;
        modAndPow(a, temp, &k, &t, &tempResult);
        temp = t;
        result *= tempResult;
        globalCount++;
//        printf("k:%u, t:%u, tempResult:%Lf\n", k, t, tempResult);
    }
    return result;
}

最终的计算用myPowl函数。
试了一下，底数自乘的计算次数，在指数等于50000的时候globalCount为118，符合预估的时间复杂度。