Я реализую универсальное хеширование и использую следующую универсальную хеш-функцию:
h (k) = ((A * k) mod 2 ^ 64) rsh 64-р
где A — случайное число между
2 ^ 61 и 2 ^ 62.
rand()
функция в C ++ имеет тип возврата целое число и он не может генерировать такие большие числа. Итак, как я могу генерировать случайные числа в этом диапазоне? (числа должны быть очень случайными, т. е. каждое число должно иметь равную вероятность выбора)
Замечания:
long long int random=rand();
не работает как число, возвращаемое rand
является ИНТ.
В C ++ 11 Вы можете использовать случайный заголовок а также станд :: uniform_int_distribution вместе с 64-битный экземпляр std :: mersenne_twister_engine это должно делать что хочешь (увидеть это в прямом эфире):
#include <iostream>
#include <random>
#include <cmath>
int main()
{
std::random_device rd;
std::mt19937_64 e2(rd());
std::uniform_int_distribution<long long int> dist(std::llround(std::pow(2,61)), std::llround(std::pow(2,62)));
std::cout << std::llround(std::pow(2,61)) << std::endl;
std::cout << std::llround(std::pow(2,62)) << std::endl;
for (int n = 0; n < 10; ++n) {
std::cout << dist(e2)<< ", " ;
}
std::cout << std::endl ;
}
Если C ++ 11 это не вариант, то кажется, что есть исходный код для несколько 64-битных реализаций Mersenne Twister.
((long long)rand() << 32) | rand()
РЕДАКТИРОВАТЬ: это предполагает, что rand () генерирует 32 случайных бита, чего не может быть.