幂次方算法pow

     最简单的，调用math头文件，使用pow函数

自定义的递归算法，代码要求的时间与空间复杂度较高，不适合嵌入式设备进行快速计算。代码由C++实现。

double mypow(double x, int y) //x不能为0
{
    if (y >= 0)
    {
        if (y == 0)
            return 1;
        else if (y==1)
        {
            return x;
        }
        else
        {
            return mypow(x, y - 1)*x;
        }   
    }
    else
    {
        if (y == -1)
            return 1 / x;
        else
        {
            return mypow(x, y + 1) / x;
        }

    }
}

迭代算法，复杂度也挺高的。

double mypow(double x, int y) //x不能为0
{
    double temp=1.0f;
    if (y >= 0)
    {
        if (y == 0)
            return 1;
        else
        {
            while (y >=1)
            {
                temp *=x;
                y--;
            }
            return temp;
        }
    }
    else
    {
        while (y <= -1)
        {
            temp /= x;
            y++;
        }
        return temp;
    }
}

优化后的递归算法：
原理：

递归优化

double mypow(double x, int y) 
{
    if (y == 0)
        return 1;
    if (y > 0)
    {
        if (!(y & 1))//偶数
        {
            return mypow(x, y / 2)*mypow(x, y / 2);
            y /= 2;
        }
        else//奇数
        {
            return mypow(x, y - 1)*x;
            --y;
        }
    }
    else//负数
    {
        if (!(y & 1))//偶数
        {
            return mypow(x, y / 2)*mypow(x, y/2);
            y /= 2;
        }
        else//奇数
        {
            return mypow(x, y + 1)/x;
            ++y;
        }
    }
}

同理，迭代pow也可以优化

double mypow(double x, int y) //x不能为0
{
    if (y == 0)
        return 1;
    int tempy = y, tempx = 1;
    double res = 1;
    if (y < 0)
    {
        tempx = -1;
    }
    while (tempy>0)
    {
        tempy /= 2;
        tempx *= 2;
    }
    while (tempy < 0)
    {
        tempy /= 2;
        tempx *= 2;
    }
    tempy = y;
    while (tempx>1)
    {
        tempx /= 2;
        res *= res;
        if (tempy >= tempx)
        {
            res *= x;
            tempy -= tempx;
        }
    }
    while (tempx < -1)
    {
        tempx /= 2;
        res *= res;
        if (tempy <= tempx)
        {
            res /= x;
            tempy -= tempx;
        }
    }
    return res;
}

原理其实也是根据指数奇偶来优化该算法。

double mypow(double x, int y) //x不能为0
{
    if (y == 0)
        return 1;
    double res = 1;
    int tag[65], index = 0,tempy=y;
    while (tempy != 0)
    {
        tag[index++] = tempy & 1;//奇偶标志
        tempy /= 2;
    }
    for (int i = index - 1; i >= 0; i--)
    {
        res *= res;
        if (y > 0)
        {
            if (tag[i] != 0)
            {
                res *= x;
            }
        }
        else if(y<0)
        {
            if (tag[i] != 0)
            {
                res /= x;
            }
        }
    }
    return res;
}