Last active
November 22, 2020 23:18
-
-
Save ranisalt/19332b42d945b729f29a3030ef96c6e3 to your computer and use it in GitHub Desktop.
hand rolled fast pow() vs std::pow()
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <array> | |
#include <cassert> | |
#include <chrono> | |
#include <cmath> | |
#include <cstdint> | |
#include <iostream> | |
#include <numeric> | |
#include <random> | |
#include <vector> | |
constexpr auto tries_v(uint64_t level, double multiplier) { | |
return static_cast<uint64_t>(50 * std::pow(multiplier, level - 1)); | |
} | |
int main() { | |
using namespace std; | |
using namespace std::chrono; | |
// CONFIGURATION | |
constexpr auto reps = numeric_limits<unsigned>::max() >> 10; | |
constexpr auto MAXLVL = 250, VOCS = 8; | |
auto skillMultiplier = array<double, VOCS>{}; | |
fill_n(skillMultiplier.begin(), 4, 1.4); | |
random_device rd; | |
mt19937 rng(rd()); | |
geometric_distribution<mt19937::result_type> randlvl(0.01); | |
uniform_int_distribution<mt19937::result_type> randvoc(0, VOCS - 1); | |
{ | |
auto counter = std::vector<uint64_t>{}; | |
rng.seed(0); | |
auto start = high_resolution_clock::now(); | |
for (unsigned i = 0u; i < reps; ++i) { | |
auto level = static_cast<uint64_t>(randlvl(rng)) % MAXLVL; | |
auto group = level / 10; | |
if (group >= counter.size()) { | |
counter.resize(group + 1); | |
} | |
counter[group] += 1; | |
} | |
cout << "Distribution of levels generated:\n"; | |
for (auto i = 0; i < counter.size(); ++i) { | |
cout << (i * 10) << '-' << (i + 1) * 10 << "\t" | |
<< string(counter[i] / (reps >> 9), '*') << " (" << counter[i] | |
<< ")\n"; | |
} | |
} | |
{ | |
auto skillCaches = array<vector<uint64_t>, VOCS>{}; | |
auto counter = 0ull; | |
rng.seed(0); | |
auto start = high_resolution_clock::now(); | |
for (unsigned i = 0u; i < reps; ++i) { | |
auto voc = randvoc(rng); | |
auto &skillCache = skillCaches[voc]; | |
auto level = static_cast<uint64_t>(randlvl(rng)) % MAXLVL; | |
if (level >= skillCache.size()) { | |
skillCache.resize(level + 1); | |
} | |
auto tries = skillCache[level]; | |
if (!tries) { | |
tries = skillCache[level] = tries_v(level, skillMultiplier[voc]); | |
} | |
counter += tries; | |
} | |
auto end = high_resolution_clock::now(); | |
cout << counter << "\t" | |
<< duration_cast<nanoseconds>(end - start).count() / reps << "ns\n"; | |
} | |
{ | |
auto counter = 0ull; | |
rng.seed(0); | |
auto start = high_resolution_clock::now(); | |
for (unsigned i = 0u; i < reps; ++i) { | |
auto voc = randvoc(rng); | |
auto level = static_cast<uint64_t>(randlvl(rng)) % MAXLVL; | |
auto tries = tries_v(level, skillMultiplier[voc]); | |
counter += tries; | |
} | |
auto end = high_resolution_clock::now(); | |
cout << counter << "\t" | |
<< duration_cast<nanoseconds>(end - start).count() / reps << "ns\n"; | |
} | |
return 0; | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <chrono> | |
#include <cmath> | |
#include <iostream> | |
constexpr double fast_pow(double base, uint32_t exp) { | |
double result = 1.0; | |
while (exp) { | |
if (exp & 1) { | |
result *= base; | |
} | |
exp >>= 1; | |
base *= base; | |
} | |
return result; | |
} | |
int main() { | |
using namespace std; | |
using namespace std::chrono; | |
constexpr auto reps = numeric_limits<unsigned>::max() >> 5; | |
{ | |
auto x = 1, counter = 0; | |
auto start = high_resolution_clock::now(); | |
for (unsigned i = 0u; i < reps; ++i) { | |
x = fast_pow(i, x); | |
} | |
auto end = high_resolution_clock::now(); | |
std::cout << x << "\t" << duration_cast<milliseconds>(end - start).count() | |
<< "ms\n"; | |
} | |
{ | |
auto x = 1, counter = 0; | |
auto start = high_resolution_clock::now(); | |
for (unsigned i = 0u; i < reps; ++i) { | |
x = std::pow(i, x); | |
} | |
auto end = high_resolution_clock::now(); | |
std::cout << x << "\t" << duration_cast<milliseconds>(end - start).count() | |
<< "ms\n"; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment