Можете подробнее про Ваш вариант рассказать?
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.
Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.
Можно сжать, если проверять на простоту с помощью МТФ — хранить только те, которые не являются простыми но проходят проверку.
Нашел в Викпедии, что 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 широко известен, почему-то даже ученые его игнорируют при практическом применении
Вы абсолютно правы, у меня в изначальной версии был именно ulong[]. Просто я не упомянул еще некоторые неудобства:
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.
Верхняя планка чисел всегда ограничена количеством памяти на компьютере и разрядностью. Поправьте меня, если я ошибаюсь, но стандартная de-facto вычислительная модель, если не оговорено обратное — машина Тьюринга, что эквивалентно компьютеру с бесконечным количеством памяти.
Интересная идея! Насколько я понимаю, все же, скорость проверки не удастся сохранить O(1).
Впрочем, далеко не во всех задачах требуется константная скорость проверки, тогда, действительно, можно пожертвовать скоростью ради уменьшения размера базы. В предельном случае, если я правильно понимаю, можно вообще ничего не хранить, и применять AKS-тест каждый раз заново.
При генерации простых чисел будет много random writes, боюсь, будет слишком медленно. Лучше тогда использовать сегментированное решето Эратосфена, вычислять в памяти по кускам и скидывать найденные куски на диск. Тогда можно будет генерить простые числа, в принципе, до бесконечности.
А при использовании готовой базы — да, конечно, вместо того, чтобы загружать базу в память, можно просто читать с диска по нужному смещению.
Я нашел одну реально работающую оптимизацию, с помощью которой удалось ускорить алгоритм примерно в пять раз, и добить до N=70 (запустив на ночь на восьмиядерной машине). К сожалению,
Суть оптимизации вот в чем:
Понятно, что первые два числа в последовательности не могут быть одновременно четными, так как тогда все остальные числа тоже будут четными. Более того, четных чисел только N/2, поэтому два подряд четных числа могут встретиться только во второй половине последовательности. Аналогично, если два идущих подряд числа делятся на три, то все следующие числа тоже делятся на три, поэтому они могут встретиться только в последней трети последовательности. Обобщая, если два идущих подряд числа a, b имеют наибольший общий делитель g, то индекс числа a не может быть меньше N — N/g. В частности, в первой половине последовательности идущие подряд числа взаимно просты.
Я это в конце концов понял, но вначале я рассуждал как Deosis, и мне тоже казалось, что это должно сильно ускорить поиск: для числа n количество его делителей d(n) растет очень медленно, см. ссылку: d(n)=O(n^ε) для любого ε.
Однако, в той же ссылке приведено, что сумма d(n) по всем n<N будет порядка N*lnN.
А при поиске вперед для любого n мы просматриваем N/n вариантов. Если просуммировать, то получим Sum(N/n)=N*Sum(1/n) ~ N*lnN, то есть, в среднем оба метода дают одинаковое количество итераций.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ShaleNumbers
{
public class ShaleSequence
{
private static readonly object syncRoot = new object();
private int Length;
private int[] Sequence;
private byte[] Bucket;
public ShaleSequence(int N, int a, int b)
{
Sequence = new int[N];
Bucket = new byte[N];
for (int i = 0; i < Bucket.Length; i++) Bucket[i] = 1;
Add(a);
Add(b);
}
public int N => Bucket.Length;
public int[] ToArray() => Sequence.Take(Length).ToArray();
public override string ToString() => String.Join(" ", ToArray());
public bool IsFound => Length == Sequence.Length;
private bool IsSet(int n) => Bucket[n - 1] == 1;
private void Add(int x)
{
Sequence[Length++] = x;
Bucket[x - 1] = 0;
}
private void Remove(int x)
{
Length--;
Bucket[x - 1] = 1;
}
public void Scan()
{
Scan(Sequence[0], Sequence[1]);
}
private void Scan(int a, int b)
{
if (IsFound)
{
string info = ToString();
lock (syncRoot) Console.WriteLine(info);
return;
}
for (int c = a - (b % a); c <= N; c += a)
{
if (!IsSet(c)) continue;
Add(c);
Scan(b, c);
Remove(c);
}
}
public static void FindShaleSequences(int N)
{
DateTime start = DateTime.UtcNow;
List<Task> tasks = new List<Task>();
for (int a = 1; a <= N; a++)
{
for (int b = 1; b <= N; b++)
{
if (a == b) continue;
ShaleSequence sequence = new ShaleSequence(N, a, b);
Task task = Task.Factory.StartNew(sequence.Scan);
tasks.Add(task);
}
}
Task.WaitAll(tasks.ToArray());
DateTime end = DateTime.UtcNow;
Console.WriteLine($"N: {N}; Time: {(int)(end - start).TotalSeconds} sec");
}
}
public class Program
{
public static void Main(string[] args)
{
for(int N = 3; N <= 100; N++)
{
ShaleSequence.FindShaleSequences(N);
}
}
}
}
Да, я тоже дошел до N^N/N! = O(e^N) ( кстати, получилась хорошая задачка! ), но дальше не смог продвинуться: для улучшения оценки надо учитывать, что, так как все числа должны быть разные, много вариантов для третего числа отбрасываются.
Я, кстати, посчитал количество обработанных последовательностей для каждого N. Что и можно было ожидать, их количество растет ровно с той же скоростью, что и сложность алгоритма:
Да, это одна из первых оптимизаций, которые я пробовал. Удивительно, но это не принесло никакого эффекта, время работы практически не изменилось!
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Действительно, похоже на e/2! Я, правда, не представляю, как это можно доказать (хотя достаточно просто показать, что скорость роста не превосходит e^N). Но например, если доказать, что для большинства последовательностей в переборе алгоритм доходит как минимум до длины N/2, то это даст нижнюю оценку в (e/2)^N.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.
Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.
1) P = 1 — ( 1/2 * 2/3 * 3/4 *… * 89/90 * 90/91 ) = 1 — 1/91 = 90/91 ~ 0.989
2) P = 1 — ( (1*3)/(2*2) * (2*4)/(3*3) * (3*5)/(4*4) *… * (89*91)/(90*90) * (90*92)/(91*91) ) = 1 — 1/2 * 92/91 = 45/91 ~ 0.495
Нашел в Викпедии, что Baillie–PSW primality test, который является комбинацией двух вероятностных тестов на простоту (Ферма и Лукаса), вообще не имеет исключений для 64-битных чисел. Больше того, даже для произвольно больших чисел за сорок лет ни одного исключения так и не нашли. Так что Ваша идея тут кстати: размер базы будет нулевой практически всегда. А если вдруг кто-нибудь найдет составное число, проходящее этот тест, он даже получит премию в 30 долларов!
А из более поздних исследований нашел эту статью 2015 года — они утверждают, что их алгоритм самый быстрый (скорость проверки — чуть больше миллиона 64-битных чисел в секунду) из класса алгоритмов, не требующих предварительных вычислений.
Забавно, но я у них нашел такую цитату:
То есть, они тоже считают, что для некоторых случаев битовая таблица — лучшее решение, но даже они говорят о бите на каждое нечетное число! Хотя Wheel factorization широко известен, почему-то даже ученые его игнорируют при практическом применении
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.
Понятно, спасибо. Я почему-то думал, что MT — это обобщенное название класса машин, эквивалентных классической MT с одномерной лентой.
Впрочем, далеко не во всех задачах требуется константная скорость проверки, тогда, действительно, можно пожертвовать скоростью ради уменьшения размера базы. В предельном случае, если я правильно понимаю, можно вообще ничего не хранить, и применять AKS-тест каждый раз заново.
А при использовании готовой базы — да, конечно, вместо того, чтобы загружать базу в память, можно просто читать с диска по нужному смещению.
N: 52; Results: 0; Time: 89 sec
N: 53; Results: 0; Time: 213 sec
N: 54; Results: 0; Time: 204 sec
N: 55; Results: 0; Time: 336 sec
N: 56; Results: 0; Time: 316 sec
N: 57; Results: 0; Time: 438 sec
N: 58; Results: 0; Time: 453 sec
N: 59; Results: 0; Time: 1109 sec
N: 60; Results: 0; Time: 974 sec
N: 61; Results: 0; Time: 2230 sec
N: 62; Results: 0; Time: 2357 sec
N: 63; Results: 0; Time: 3099 sec
N: 64; Results: 0; Time: 3016 sec
N: 65; Results: 0; Time: 4896 sec
N: 66; Results: 0; Time: 4462 sec
N: 67; Results: 0; Time: 9399 sec
N: 68; Results: 0; Time: 9157 sec
N: 69; Results: 0; Time: 12960 sec
N: 70; Results: 0; Time: 12709 sec
Суть оптимизации вот в чем:
Понятно, что первые два числа в последовательности не могут быть одновременно четными, так как тогда все остальные числа тоже будут четными. Более того, четных чисел только N/2, поэтому два подряд четных числа могут встретиться только во второй половине последовательности. Аналогично, если два идущих подряд числа делятся на три, то все следующие числа тоже делятся на три, поэтому они могут встретиться только в последней трети последовательности. Обобщая, если два идущих подряд числа a, b имеют наибольший общий делитель g, то индекс числа a не может быть меньше N — N/g. В частности, в первой половине последовательности идущие подряд числа взаимно просты.
Однако, в той же ссылке приведено, что сумма d(n) по всем n<N будет порядка N*lnN.
А при поиске вперед для любого n мы просматриваем N/n вариантов. Если просуммировать, то получим Sum(N/n)=N*Sum(1/n) ~ N*lnN, то есть, в среднем оба метода дают одинаковое количество итераций.
Я, кстати, посчитал количество обработанных последовательностей для каждого N. Что и можно было ожидать, их количество растет ровно с той же скоростью, что и сложность алгоритма:
Думаю, что время работы программы линейно зависит от количества перебранных вариантов (то есть, максимальных последовательностей длины N1<=N), а их количество не зависит от того, идем мы с начала или с конца.
Насчет производительности: к сожалению, из-за экспоненциального роста оптимизация в разы дает только константное увеличение N. Например, даже если я ускорю программу в 10 раз, запустив на компьютере с 40 ядрами (вместо 4), то, в лучшем случае, я смогу проверить только 6-7 дополнительнх значений для N. Надо искать алгоритм с лучшей асимптотикой, но совсем не факт, что он существует.
Вообще, имхо, эта задача интересна с точки зрения теории чисел. Например, она в чем-то похожа на проблему нахождения простых чисел Мерсенна (простые числа, на единицу меньшие степени двойки). Их до сих пор найдено только около 50, и до сих пор неизвестно, конечно или бесконечно ли их число.
Такой вопрос: сколько времени у вас работала программа для N=51?