Skip to content

Instantly share code, notes, and snippets.

@orlp

orlp/gist:3ddc35db57f6bdb2bad3 Secret

Last active Aug 29, 2015
Embed
What would you like to do?
#include <iostream>
#include <cmath>
#include <cstdint>
#include <map>
#include <utility>
double T(int64_t n, double p) {
static std::map<std::pair<int64_t, double>, double> cache;
std::pair<int64_t, double> cache_index(n, p);
if (n <= 1) return n;
if (cache.count(cache_index)) return cache[cache_index];
double r = n + T(std::floor(p * (n-1)), p) + T(std::ceil((1-p) * (n-1)), p);
cache[cache_index] = r;
return r;
}
double h(double p) {
return -p * std::log(p) - (1-p) * std::log(1 - p);
}
double cT(int64_t n, double p) {
return n * std::log(n) / h(p);
}
int main(int argc, char** argv) {
int64_t n = 100000000000000ll;
// 2.13222: 2.10339
std::cout << cT(n, 0.1) / cT(n, 0.5) << ": " << T(n, 0.1) / T(n, 0.5) << "\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment