#include
#include
include
include
include
using namespace std;
long long fast_exponenciation(int a, int b)
{
if (b == 0)
{
return 1;
}
long long smallerVal = fast_exponenciation(a, b / 2);
smallerVal *= smallerVal;
if (b % 2 == 0)
{
return smallerVal;
}
else
{
return a * smallerVal;
}
}
long long fast_expo_Bitmasking(long long a, int b)
{
long long res = 1;
while (b > 0)
{
int las_bit = (b & 1);
if (las_bit)
{
res *= a;
}
a *= a;
b = b >> 1;
}
return res;
}
long long brute_force_expo(long long a, int b)
{
long long res = 1;
b = b + 1;
for (int i = 1; i != b; i++)
{
res *= a;
}
return res;
}
int main()
{
std::chrono::time_pointstd::chrono::steady_clockstart, end;
std::chrono::duration duration;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
start = std::chrono::high_resolution_clock::now();
cout << fast_exponenciation(100, 9) << endl;
end = std::chrono::high_resolution_clock::now();
duration = end - start;
cout << "this fast_exponenciation took " << duration.count() << endl;
start = std::chrono::high_resolution_clock::now();
cout << fast_expo_Bitmasking(100, 9) << endl;
end = std::chrono::high_resolution_clock::now();
duration = end - start;
cout << "this fast_expo_Bitmasking took " << duration.count() << endl;
start = std::chrono::high_resolution_clock::now();
cout << brute_force_expo(100, 9)<< endl;
end = std::chrono::high_resolution_clock::now();
duration = end - start;
cout << "This brute force expo took " << duration.count() << endl;
return 0;
}
