小朋友学算法(6):求幂pow函数的四种实现方式

在math.h中,声明了一个函数pow(x, n),用于求x的n次方。 假如咱们不调用math.h中的pow函数,如何实现求x ^ n的算法呢?

一、while非递归

#include <stdio.h>
double pow1(double x, unsigned int n)
{
    int res = 1;
    while(n--)
    {
        res *= x;
    }
    return res;
}
int main()
{
    printf("2 ^ 10 = %f\n", pow1(2, 10));
    printf("5 ^ 3 = %f\n", pow1(5, 3));
    printf("10 ^ 0 = %f\n", pow1(10, 0));
    return 0;
}

运行结果:

2 ^ 10 = 1024.000000
5 ^ 3 = 125.000000
10 ^ 0 = 1.000000

二、递归方法1

#include <stdio.h>
double pow2(double x, unsigned int n)
{
    if(0 == n)
    {
        return 1;
    }
    if(1 == n)
    {
        return x;
    }
    return x * pow2(x, n - 1);
}
int main()
{
    printf("2 ^ 10 = %f\n", pow2(2, 10));
    printf("5 ^ 3 = %f\n", pow2(5, 3));
    printf("10 ^ 0 = %f\n", pow2(10, 0));
    return 0;
}

三、递归方法2

#include <stdio.h>
double pow3(double x, unsigned int n)
{
    if(0 == n)
    {
        return 1;
    }
    if(1 == n)
    {
        return x;
    }
    if(n & 1)   // 如果n是奇数
    {
        // 这里n/2会有余数1,所以需要再乘以一个x
        return pow3(x * x, n / 2) * x;
    }
    else        // 如果x是偶数
    {
        return pow3(x * x, n / 2);
    }
}
int main()
{
    printf("2 ^ 10 = %f\n", pow3(2, 10));
    printf("5 ^ 3 = %f\n", pow3(5, 3));
    printf("10 ^ 0 = %f\n", pow3(10, 0));
    return 0;
}

四、快速求幂算法

上面三种方法都有一个缺点,就是循环次数多,效率不高。举个例子: 3 ^ 19 = 3 * 3 * 3 * … * 3 直接乘要做18次乘法。但事实上可以这样做,先求出3的2^k次幂: 3 ^ 2 = 3 * 3 3 ^ 4 = (3 ^ 2) * (3 ^ 2) 3 ^ 8 = (3 ^ 4) * (3 ^ 4) 3 ^ 16 = (3 ^ 8) * (3 ^ 8) 再相乘: 3 ^ 19 = 3 ^ (16 + 2 + 1) = (3 ^ 16) * (3 ^ 2) * 3 这样只要做7次乘法就可以得到结果: 3 ^ 2 一次, 3 ^ 4 一次, 3 ^ 8 一次, 3 ^ 16 一次, 乘四次后得到了3 ^ 16 3 ^ 2 一次, (3 ^ 2) * 3 一次, 再乘以(3 ^ 16) 一次, 所以乘了7次得到结果。

如果幂更大的话,节省的乘法次数更多(但有可能放不下)。 即使加上一些辅助的存储和运算,也比直接乘高效得多。

我们发现,把19转为2进制数:10011,其各位就是要乘的数。这提示我们利用求二进制位的算法:

所以就可以写出下面的代码:

#include <stdio.h>
double pow4(double x, int n)
{
    double res = 1;
    while (n)
    {
        if (n & 1)        // 等价于 if (n % 2 != 0)
        {
            res *= x;
        }
        n >>= 1;
        x *= x;
    }
    return res;
}
int main()
{
    printf("2 ^ 10 = %f\n", pow4(2, 10));
    printf("5 ^ 3 = %f\n", pow4(5, 3));
    printf("10 ^ 0 = %f\n", pow4(10, 0));
    printf("3 ^ 19 = %f\n", pow4(3, 19));
    return 0;
}

运行结果:

2 ^ 10 = 1024.000000
5 ^ 3 = 125.000000
10 ^ 0 = 1.000000
3 ^ 19 = 1162261467.000000

五、效率比较

#include <stdio.h>
#include <math.h>
#include <time.h>
using namespace std;
#define COUNT 100000000
double pow1(double x, unsigned int n)
{
    int res = 1;
    while(n--)
    {
        res *= x;
    }
    return res;
}
double pow2(double x, unsigned int n)
{
    if(0 == n)
    {
        return 1;
    }
    if(1 == n)
    {
        return x;
    }
    return x * pow2(x, n - 1);
}
double pow3(double x, unsigned int n)
{
    if(0 == n)
    {
        return 1;
    }
    if(1 == n)
    {
        return x;
    }
    if(n & 1)   // 如果n是奇数
    {
        // 这里n/2会有余数1,所以需要再乘以一个x
        return pow3(x * x, n / 2) * x;
    }
    else        // 如果x是偶数
    {
        return pow3(x * x, n / 2);
    }
}
double pow4(double x, int n)
{
    double result = 1;
    while (n)
    {
        if (n & 1)
            result *= x;
        n >>= 1;
        x *= x;
    }
    return result;
}
int main()
{
    int startTime, endTime;
    startTime = clock();
    for (int i = 0; i < COUNT; i++)
    {
        pow(2.0, 100.0);
    }
    endTime = clock();
    printf("调用系统函数计算1亿次,运行时间%d毫秒\n", (endTime - startTime));
    startTime = clock();
    for (int i = 0; i < COUNT/100; i++)
    {
        pow1(2.0, 100);
    }
    endTime = clock();
    printf("调用pow1函数计算100万次,运行时间%d毫秒\n", (endTime - startTime));
    startTime = clock();
    for (int i = 0; i < COUNT; i++)
    {
        pow2(2.0, 100);
    }
    endTime = clock();
    printf("调用pow2函数计算1亿次,运行时间%d毫秒\n", (endTime - startTime));
    startTime = clock();
    for (int i = 0; i < COUNT; i++)
    {
        pow3(2.0, 100);
    }
    endTime = clock();
    printf("调用pow3函数计算1亿次,运行时间%d毫秒\n", (endTime - startTime));
    startTime = clock();
    for (int i = 0; i < COUNT; i++)
    {
        pow4(2.0, 100);
    }
    endTime = clock();
    printf("调用pow4函数计算1亿次,运行时间%d毫秒\n", (endTime - startTime));
    return 0;
}

运行结果:

调用系统函数计算1亿次,运行时间187毫秒
调用pow1函数计算100万次,运行时间7982毫秒
调用pow2函数计算1亿次,运行时间90141毫秒
调用pow3函数计算1亿次,运行时间6319毫秒
调用pow4函数计算1亿次,运行时间3243毫秒

从运行结果可以看出来, 最快的是math.h提供的函数pow, 接下来依次是pow4、pow3、 pow2, 最慢的是pow1,100万次用了近8秒,1亿次至少需要几十分钟或几个小时。

六、math.h中的pow函数源码

我使用的编译器是CodeBlocks,没法查看math.h的源码。 但是我在网络上找到了微软的math.h源码 http://www.bvbcode.com/cn/z9w023j8-107349 这里有关于pow函数的实现

template<class _Ty> inline
        _Ty _Pow_int(_Ty _X, int _Y)
        {unsigned int _N;
        if (_Y >= 0)
                _N = _Y;
        else
                _N = -_Y;
        for (_Ty _Z = _Ty(1); ; _X *= _X)
                {if ((_N & 1) != 0)
                        _Z *= _X;
                if ((_N >>= 1) == 0)
                        return (_Y < 0 ? _Ty(1) / _Z : _Z); }}

这个实现思路跟pow4的实现思路是一致的。

七、结论

在实际编程时,可以直接调用math.h提供的pow函数; 如果在特定场合需要自己定义的话,使用pow4的方式。

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

732
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

831
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2582
来自专栏数据结构与算法

1012. 变换密码

1012. 变换密码 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 一密码变换规则如下:一...

3014
来自专栏数据小魔方

左右用R右手Python9——字符串合并与拆分

在文本处理和数据清洗阶段,对字符串或者字符型变量进行分割、提取或者合并虽然谈不上什么高频需求,但是往往也对很重要的。 接下来跟大家大致盘点一下在R语言与Pyh...

3515
来自专栏深度学习思考者

一文搞懂算法的时间复杂度与空间复杂度

一 时间复杂度的概念   一般情况下,算法的基本操作重复执行的次数是模块n的某一函数f(n),因此,算法的时间复杂度记做 T(n) = O(f(n))。 随着模...

7688
来自专栏锦小年的博客

Python数据分析(2)-pandas数据结构操作

pandas是一个提供快速、灵活、表达力强的数据结构的Python库,适合处理‘有关系’或者‘有标签’的数据。在利用Python做数据分析的时候,pandas是...

26110
来自专栏抠抠空间

算法基础

1164
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

2040
来自专栏chenjx85的技术专栏

leetcode-78-子集(用bfs解决)

vector<vector<int>> subsets(vector<int>& nums)

4421

扫码关注云+社区

领取腾讯云代金券