Около года назад я работал в этой области для libc ++ при реализации неупорядоченных (хэш) контейнеров для C ++ 11.Я думал, что поделюсь своим опытом здесь.Этот опыт поддерживает принятый Marcog ответ для разумного определения "грубой силы".
Это означает, что даже простая грубая сила будет достаточно быстрой вВ большинстве случаев, принимая O (ln (p) * sqrt (p)) в среднем.
Я разработал несколько реализаций size_t next_prime(size_t n), где спецификация для этой функции:
Возвращает: Наименьшее простое число, которое больше или равно n.
Каждая реализация next_prime сопровождается вспомогательной функцией is_prime.is_prime следует считать частной реализацией;не предназначен для непосредственного вызова клиентом.Каждая из этих реализаций была, конечно, проверена на корректность, но также проверена с помощью следующего теста производительности:
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double, std::milli> ms;
Clock::time_point t0 = Clock::now();
std::size_t n = 100000000;
std::size_t e = 100000;
for (std::size_t i = 0; i < e; ++i)
n = next_prime(n+1);
Clock::time_point t1 = Clock::now();
std::cout << e/ms(t1-t0).count() << " primes/millisecond\n";
return n;
}
Я должен подчеркнуть, что это тест производительности, и он не отражает типичное использование, которое выглядело бы болеенапример:
// Overflow checking not shown for clarity purposes
n = next_prime(2*n + 1);
Все тесты производительности были скомпилированы с:
clang++ -stdlib=libc++ -O3 main.cpp
Реализация 1
Существует семь реализаций.Цель отображения первой реализации состоит в том, чтобы продемонстрировать, что если вы не прекратите тестировать простое число кандидатов x для факторов на sqrt(x), то вам не удастся даже реализовать реализацию, которая может быть классифицирована как грубая сила.Эта реализация ужасно медленная .
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; i < x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
Только для этой реализации мне пришлось установить e на 100 вместо 100000, просто чтобы получить разумное время выполнения:
0.0015282 primes/millisecond
Реализация 2
Эта реализация является самой медленной из реализаций brute force , и единственным отличием от реализации 1 является то, что она прекращает тестирование на простоту, когдакоэффициент превосходит sqrt(x).
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
Обратите внимание, что sqrt(x) не рассчитывается напрямую, а определяется q < i.Это ускоряет процесс в тысячи раз:
5.98576 primes/millisecond
и подтверждает предсказание Marcog:
... это вполне в рамках большинства проблем, принимающих порядокмиллисекунда на самом современном оборудовании.
Реализация 3
Можно почти удвоить скорость (по крайней мере, на оборудовании, которое я использую), избегая использованияоператора %:
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
11.0512 primes/millisecond
Реализация 4
До сих пор я даже не использовал общеизвестный факт, что 2 является единственным четным простым числом.Эта реализация включает в себя эти знания, почти вдвое увеличивая скорость:
bool
is_prime(std::size_t x)
{
for (std::size_t i = 3; true; i += 2)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
if (x <= 2)
return 2;
if (!(x & 1))
++x;
for (; !is_prime(x); x += 2)
;
return x;
}
21.9846 primes/millisecond
Реализация 4, вероятно, имеет в виду большинство людей, когда они думают, что "грубая сила".
Реализация 5
Используя следующую формулу, вы можете легко выбрать все числа, которые не делятся ни на 2, ни на 3:
6 * k + {1, 5}
, где k> = 1. Следующая реализация использует эту формулу,но реализовано с помощью симпатичного трюка xor:
bool
is_prime(std::size_t x)
{
std::size_t o = 4;
for (std::size_t i = 5; true; i += o)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
o ^= 6;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
switch (x)
{
case 0:
case 1:
case 2:
return 2;
case 3:
return 3;
case 4:
case 5:
return 5;
}
std::size_t k = x / 6;
std::size_t i = x - 6 * k;
std::size_t o = i < 2 ? 1 : 5;
x = 6 * k + o;
for (i = (3 + o) / 2; !is_prime(x); x += i)
i ^= 6;
return x;
}
Это фактически означает, что алгоритм должен проверять только 1/3 целых чисел на простоту вместо 1/2 чисел, а тест производительности показывает ожидаемоепочти на 50%:
32.6167 primes/millisecond
Реализация 6
Эта реализация является логическим расширением реализации 5: она использует следующую формулу для вычисления всех чисел, которыене делятся на 2, 3 и 5:
30 * k + {1, 7, 11, 13, 17, 19, 23, 29}
Он также развертывает внутренний цикл в is_prime и создает список "маленьких простых чисел", которыеЭто полезно для работы с числами меньше 30.
static const std::size_t small_primes[] =
{
2,
3,
5,
7,
11,
13,
17,
19,
23,
29
};
static const std::size_t indices[] =
{
1,
7,
11,
13,
17,
19,
23,
29
};
bool
is_prime(std::size_t x)
{
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
for (std::size_t i = 3; i < N; ++i)
{
const std::size_t p = small_primes[i];
const std::size_t q = x / p;
if (q < p)
return true;
if (x == q * p)
return false;
}
for (std::size_t i = 31; true;)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
}
return true;
}
std::size_t
next_prime(std::size_t n)
{
const size_t L = 30;
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
// If n is small enough, search in small_primes
if (n <= small_primes[N-1])
return *std::lower_bound(small_primes, small_primes + N, n);
// Else n > largest small_primes
// Start searching list of potential primes: L * k0 + indices[in]
const size_t M = sizeof(indices) / sizeof(indices[0]);
// Select first potential prime >= n
// Known a-priori n >= L
size_t k0 = n / L;
size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices;
n = L * k0 + indices[in];
while (!is_prime(n))
{
if (++in == M)
{
++k0;
in = 0;
}
n = L * k0 + indices[in];
}
return n;
}
Возможно, это выходит за рамки "грубой силы" и хорошо для увеличения скорости еще на 27,5% до:
41.6026 primes/millisecond
Реализация 7
Практически сыграть в вышеуказанную игру еще на одну итерацию, разработавформула для чисел, не делимых на 2, 3, 5 и 7:
210 * k + {1, 11, ...},
Исходный код здесь не показан, но очень похож на реализацию 6.
Это реализация, которую я решил использовать для неупорядоченных контейнеров.
libc ++ , и этот исходный код является открытым исходным кодом (находится по ссылке).
Эта последняя итерация хороша для еще одного увеличения скорости на 14,6% до:
47.685 primes/millisecond
Использование этого алгоритма гарантирует, что клиенты хеш-таблиц libc ++ могут выбирать
любое простое число, которое они решат, наиболее выгодно для их ситуации, и производительность
для этого приложения вполне приемлемо.