Верхняя планка чисел всегда ограничена количеством памяти на компьютере и разрядностью. Поправьте меня, если я ошибаюсь, но стандартная 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, и до сих пор неизвестно, конечно или бесконечно ли их число.
Понятно, спасибо. Я почему-то думал, что 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?