/*
* 使用暴力枚举计算x的n次幂
*/
#include<iostream>
using namespace std;

double pow(double x, int n) {
    double res = 1.0;
    for (int i = 0; i < n; i++) {
        res *= x;
    }
    return res;
}

/*
* 使用递归法计算x的n次幂
*/
#include<iostream>
using namespace std;

double pow(double x, int n) {
    if (n == 0) {
        return 1.0;
    }
    double res = pow(x, n / 2);
    if (n % 2 == 0) {
        return res * res;
    }
    else {
        return res * res * x;
    }
}

/*
* 使用快速幂算法计算x的n次幂
*/
#include<iostream>
using namespace std;

double pow(double x, int n) {
    double res = 1.0;
    for (; n; n >>= 1) {
        if (n & 1) {
            res *= x;
        }
        x *= x;
    }
    return res;
}

/*
* 测试上述三种算法的性能，计算x的n次幂，其中x=2.0，n=10^7
*/
#include<iostream>
#include<chrono>

using namespace std;

int main()
{
    int n = 10000000;
    double x = 2.0;

    auto start = chrono::high_resolution_clock::now();
    double a = pow(x, n);
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cout << "暴力枚举算法计算结果：" << a << endl;
    cout << "暴力枚举算法所用时间：" << duration.count() << "微秒" << endl;

    start = chrono::high_resolution_clock::now();
    double b = pow(x, n);
    end = chrono::high_resolution_clock::now();
    duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cout << "递归法算法计算结果：" << b << endl;
    cout << "递归法算法所用时间：" << duration.count() << "微秒" << endl;

    start = chrono::high_resolution_clock::now();
    double c = pow(x, n);
    end = chrono::high_resolution_clock::now();
    duration = chrono::duration_cast<chrono::microseconds>(end - start);
    cout << "快速幂算法算法计算结果：" << c<< endl;
    cout << "快速幂算法所用时间：" << duration.count() << "微秒" << endl;

    return 0;
}

暴力枚举算法计算结果：1.26765e+30103
暴力枚举算法所用时间：613805微秒
递归法算法计算结果：1.26765e+30103
递归法算法所用时间：1165微秒
快速幂算法算法计算结果：1.26765e+30103
快速幂算法所用时间：308微秒