Комментарии 28
А при использовании готовой базы — да, конечно, вместо того, чтобы загружать базу в память, можно просто читать с диска по нужному смещению.
Впрочем, далеко не во всех задачах требуется константная скорость проверки, тогда, действительно, можно пожертвовать скоростью ради уменьшения размера базы. В предельном случае, если я правильно понимаю, можно вообще ничего не хранить, и применять AKS-тест каждый раз заново.
Для оценки сложности логичнее использовать RAM-машину с бесконечной памятью, а не машину Тюринга, потому что даже простое обращение к ячейке N в RAM-машине имеет сложность O(1), а МТ — O(N).
В любом случае ссылаться на конечность данных реальных компьютеров при анализе алгоритмов — верный признак недопонимания. С другой стороны, и константу перед главным членом в реальности тоже надо учитывать.
Можно сжать, если проверять на простоту с помощью МТФ — хранить только те, которые не являются простыми но проходят проверку.
Нашел в Викпедии, что Baillie–PSW primality test, который является комбинацией двух вероятностных тестов на простоту (Ферма и Лукаса), вообще не имеет исключений для 64-битных чисел. Больше того, даже для произвольно больших чисел за сорок лет ни одного исключения так и не нашли. Так что Ваша идея тут кстати: размер базы будет нулевой практически всегда. А если вдруг кто-нибудь найдет составное число, проходящее этот тест, он даже получит премию в 30 долларов!
А из более поздних исследований нашел эту статью 2015 года — они утверждают, что их алгоритм самый быстрый (скорость проверки — чуть больше миллиона 64-битных чисел в секунду) из класса алгоритмов, не требующих предварительных вычислений.
Забавно, но я у них нашел такую цитату:
If we expect that we’ll need to test a significantly large number of small integers for primality, the best solution might be precomputing all possible answers
and then answering each query in constant time. The canonical implementation
uses one bit for each odd number, i.e., 2b/16 bytes of memory if the valid inputs are b-bit integers
То есть, они тоже считают, что для некоторых случаев битовая таблица — лучшее решение, но даже они говорят о бите на каждое нечетное число! Хотя Wheel factorization широко известен, почему-то даже ученые его игнорируют при практическом применении
Я пытался написать максимально быстрое решето, и упаковка 30 чисел в байт проигрывает по скорости хранению только нечетных из-за необходимости вычисления остатка.
Сработал вариант хранения восьми отдельных массивов для отдельных остатков.
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.
Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.
/// <summary>
/// Test only numbers like Size*k + Offsets[i]
/// </summary>
private struct Wheel {
public int Size;
public int[] Offsets;
public int[] Deltas;
public DivMod[,] DivMods;
}
private static T EratospheneWheel<T>(T consumer, int bound, Wheel wheel)
where T : struct, IConsumer {
int low = (int) Math.Sqrt(bound);
int length = bound / wheel.Size + 1;
var sieves = new BitArray[wheel.Offsets.Length];
for (int i = 0; i < sieves.Length; i++) {
sieves[i] = new BitArray(length, true);
}
int k = 0, num = wheel.Offsets[1], sieve = 1;
while (num <= low) {
if (sieves[sieve][k]) {
consumer.Consume(num);
for (int other = 0; other < sieves.Length; other++) {
var divMod = wheel.DivMods[sieve, other];
var bits = sieves[divMod.Idx];
var start = k * (num + wheel.Offsets[other]) + divMod.Div;
for (int idx = start; idx < length; idx += num) {
bits[idx] = false;
}
}
}
num += wheel.Deltas[sieve];
sieve++;
if (sieve == sieves.Length) {
++k;
sieve = 0;
}
}
while (num <= bound) {
if (sieves[sieve][k]) {
consumer.Consume(num);
}
num += wheel.Deltas[sieve];
sieve++;
if (sieve == sieves.Length) {
++k;
sieve = 0;
}
}
return consumer;
}
Это самый быстрый вариант, который у меня получился. Наилучший размер колеса — 210.
Этот код суммирует простые числа до миллиарда за 5 секунд.
И конечно в числодробилке не надо использовать ничего сверх минимума. Только массивы, только хардкор. Try и Exception сильно бьют по призводительности.
Деления и остатки вычисляются заранее, но возможно компилятор сможет оптимизировать деление на константу.
Хотя я согласен, битовая арифметика будет замедляет алгоритм в любом случае.
Теоретически, если искать простые числа не в одном большом массиве на гигабайты, а разделить его на куски по несколько мегабайт, чтобы весь битовый массив поместился в кеш третьего уровня, может, тогда ускорение доступа к памяти может исправить замедление от битовых операций.
А в чём трудности с битовой арифметикой при использовании ulong
вместо byte
? Насколько я понимаю, она остаётся той же самой, просто массивы INDEX_TO_BIT
и BIT_TO_INDEX
увеличиваются в 8 раз (с соответствующим заполнением значений, шаблон такого заполнения легко вычисляется), а деление на 30 превращается в деление на 240.
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.
- Начинаем с 0.
На каждое натуральное число нужен 1 бит - Далее 2: можно не хранить чётные, экономим 50% («правильный» остаток — 1, «неправильный» — 0), сама двойка в уме.
- Далее к двойке присоединяется тройка, остатки от деления на 6, соответственно, 1 и 5; на каждые 6 чисел (натуральных) требуется 2 бита, ещё полуторакратное улучшение, 2 и 3 в уме.
- Тут к двойке с тройкой присоединяется пятёрка: делитель 30, остатков 8, соответственно, 30 чисел в восьми битах (по сравнению с предыдущим вариантом выигрыш всего 20%: до этого те же 30 чисел занимали 10 бит), 2, 3 и 5 в уме.
- Тут на сцену могла бы выйти семёрка, но 210 чисел в 48-ми битах — это дополнительный выигрыш всего около 14% (уже 35 чисел на те же 8 бит), а код ещё более сложный и он должен работать, а значит тратить процессорное и наше время.
И так можно продолжать довольно долго.
Лично я остановился бы уже на тройке, но при байтовой организации, как ни странно, при переходе от тройки к пятёрке код волшебным образом упрощается вместо ожидаемого усложнения :)
Хочу только отметить, что если взять достаточно большое количество простых чисел, можно добиться произвольно большого сжатия. Я когда-то подсчитал, что для факторизации по первым четырем миллиардам простых чисел потребуется примерно 0.0225 бит на натуральное число. Однако на практике, конечно, этот алгоритм неприменим, потому что выгода начнется только для простых чисел, состоящих из триллионов (десятичных) знаков. Кроме того, размер таблицы INDEX_TO_BIT будет больше количества атомов во вселенной.
Кстати, подозреваю, что максимальной эффективности можно достичь, включив простых чисел примерно до корня квадратного из максимально доступного для хранения, а это ну очень много для более или менее больших чисел. И подозреваю, что эффект по-прежнему будет «в разы», а не «в десятки раз», хотя, конечно, зависит от масштабов.
При добавлении 11 только «правильных» остатков становится 480 (всего 2310)
P.S. работаю над реализацией Эратосфена на Python без хранения как простых, так и составных (по крайней мере, большей их части).
Результаты уже есть — на сотни миллиардов натуральных чисел (как проверенных, так и пропущенных) приходятся только десятки мегабайт памяти. Планирую статью на эту тему и наработки в Open Source
P.P.S. К сожалению (только моему), существующие реализации (тоже на Python) перебора простых, основанные на существующих тестах на простоту, не только дают схожий результат по производительности (более скрупулёзное сравнение ещё не производил), но ещё и позволяют не выбирать простые последовательно, а даже, например, обращаться за ними по порядковому номеру (!) в ряду простых
Самый известный алгоритм для нахождения всех простых чисел, не больших заданного, – решето Эратосфенамогу ещё порекомендовать Решето Сундарама — в некотором смысле, это то же решето Эратосфена, только оптимизированное в плане полного избавления от повторных вычёркиваний
Хочу только уточнить, что избавление от повторных вычеркиваний не полное — например, число 45 = 5 * 9 все равно вычеркивается дважды: (n-1)/2 = 22 = i + j + 2ij для {i=1, j=7}, а также для {i=2, j=4}.
Если я правильно понимаю, практически любая оптимизация решета Эратосфена делает аналогичную вещь: в коде вместо
for (long i = 7; i * i < Length; i++)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += i) ClearPrime(d);
}
надо 1 заменить на 2 в двух местах:
for (long i = 7; i * i < Length; i += 2)
{
if (!IsPrime(i)) continue;
for (long d = i * i; d < Length; d += 2 * i) ClearPrime(d);
}
и получится полный аналог алгоритма Сундарама в плане избавления от повторных вычеркиваний.
Но вы правы, можно перевести все вычисления в (n-1)/2, код получится даже проще (хотя, конечно, для понимания сложнее, чем интуитивно понятное решето Эратосфена)
Некропостинг, конечно же, зло, но вот сейчас занимаюсь похожей задачей и оказалось, что вообще-то хранить в каждом байте можно по биту на десяток для последней десятичной цифры (т.е. вычеты считать вообще не придется)
Если число заканчивается на 1, 3, 7 или 9, то на на каждые 10+х, 20+х и 30+х нужно всего два бита, потому что 21 и 27 делятся на три и 33 и 39 делятся на 3.
Тогда хранение будет таким же как у вас, таким же производительным как только для четных чисел
Для уменьшения базы можно брать большие чем 30 примариальные базы. Например, при хранении битов по вычетам для базы 30 у нас есть 8 остатков на каждые 30 чисел. По базе 30*7 = 210 количество остатков по вычетам будет 43 и на каждый байт уже будет 39 . При базе 210*11 = 2310 количество остатков по вычетам будет 339, и на каждый байт придется в среднем больше чем по 54 числа. Ну, а при базе 2310*13=30030 количество остатков по вычетам получается что-то около 3000 и каждый байт будет кодировать около 75 простых чисел.
Я бы вообще хранил массивы только до следующего праймориала, а потом использовал сохраненный массив для расчета следующей базы вычетов и еще более емкого хранения. Гипотетически, там довольно быстро растут интервалы которые кодируются одним байтом.
Я пока не проверил, но ожидаю, что на базе праймориала 31 (это чуть больше чем 200.5 млрд) будет всего около одного миллиарда вычетов и каждый байт будет кодировать около 1600 чисел
База данных простых чисел до ста миллиардов на коленке