#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define isz(x) (int)(x).size()
typedef unsigned long long ull;
const uint64_t seed = (uint64_t)(std::chrono::high_resolution_clock::now().time_since_epoch().count());
const int mod = int((1LL << 31) - 1);
int remainder(uint64_t x) {
    x = (x >> 31) + (x & mod) + 1;
    x = (x >> 31) + (x & mod);
    return int((x >> 31) + (x & mod) - 1);
}

struct CustomHash {
    uint64_t operator()(uint64_t x) const {
        static const uint64_t a = remainder(seed);
        static const uint64_t b = remainder(a * a);
        static const uint64_t c = remainder(a * b);
        static const uint64_t d = remainder(a * c);
        static const uint64_t m = (1 << 16) - 1;
        return remainder((x&m)*a+((x>>16)&m)*b+((x>>32)&m)*c+((x>>48)&m)*d);
    }
};

template<typename HashType>
void report(const char * filename) {
// This function reads numbers from file `filename` and counts number of collisios
    std::map<int,int> collisions;
    auto file = fopen(filename, "rt");
    for (ull num; fscanf(file, "%llu", &num) == 1; ) {
        auto res = HashType()(num);
        collisions[res & ((1 << 18) - 1)]++;
    }
    fclose(file);
    std::vector<int> vec;
    for (auto p : collisions) { vec.push_back(p.second-1); }
    std::sort(all(vec));
    auto median = vec[isz(vec)/2];
    auto average = std::accumulate(all(vec), 1.0) / isz(vec);
    std::cerr << "report for file " << filename << ":\n";
    std::cerr << "buckets = " << collisions.size() << "\n";
    std::cerr << "average collisions num = " << average << "\n";
    std::cerr << "median of collisions num = " << median << "\n";
    std::cerr << "max = " << vec.back() << "\n";
    std::cerr << "min = " << vec.front() << "\n";
}

int main() {
	std::cout << std::fixed << std::setprecision(3);
    //report<CustomHash>("stat1.txt");
    // This part of code test CustomHash on runtime:
    double tin = (double)clock();
    std::mt19937 gen(seed);
    std::uniform_int_distribution<uint64_t> dist(ull(0), ~ull(0));
    ull sum = 0;
    const int numOper = 50 * 1000 * 1000;
    for (int i = 0; i < numOper; i++) {
        sum += CustomHash()(dist(gen));        
    }
    double tout = ((double)clock() - tin) / CLOCKS_PER_SEC;
    std::cout << "checksum = " << sum << std::endl;
    std::cout << "number of operations is " << numOper << ", runtime is " << tout << "s" << std::endl;
    return 0;
}