Comments 61
С ростом простых чисел, расстояние между ними постепенно увеличивается (вики). Когда встречается первый интервал больше 256 надо проверять. Так что такое сжатие допустимо только в определенных пределах.
После превышения 255 в файл пишется два байта: нулевой и байт, равный (расстояние — 255). Поскольку нулевое расстояние невозможно (сейчас нулевой байт в файле — это самый первый байт, но его можно убрать, чтобы не мешался), то нулевой байт как раз сигнализирует о более длинном расстоянии. Программа primegen ищет простые числа в диапазоне, поэтому можно вхолостую прокручивать ее, чтобы узнать расстояние для определенного диапазона.
До 10^9 интервалов >= 256 три штуки:
436273009..436273291: 282
649580171..649580447: 276
944192807..944193067: 260
Этот комментарий спонсирован PARI/GP, на котором это вычисляется в одну строчку за 20 секунд (из которых предвычисление таблицы занимает 4).
436273009..436273291: 282
649580171..649580447: 276
944192807..944193067: 260
Этот комментарий спонсирован PARI/GP, на котором это вычисляется в одну строчку за 20 секунд (из которых предвычисление таблицы занимает 4).
default(primelimit,10^9);q=0;forprime(p=2,10^9,if(p-q>=256,print(q," .. ",p,": ",p-q));q=p)
Автор хранит половину расстояния, поскольку все они четны. Поэтому указанные вами значения все еще будут помещаться в один байт.
Плюсую PARI/GP.
Плюсую PARI/GP.
PARI/GP — клёвая штука! спасибо, заценил.
Интересная задача, на сжатие диапазонов. На самом деле, с учетом отсутствием смысла хранить 0 (даже с учетом половин расстояния) сразу просится использовать значение 0 как 9й бит к следующему за ним байту. а если обобщать эту идею то использовать что-то вроде того как кодируется UTF (там в каждом приставном байте содержится пул для его дальнешейшего расширения дополнительными приставными)
в частности очень эффективным оказывается то что только коды символов до 127 оказываются однобайтовыми, зато если старший бит 1 то оставшиеся 7 складываются со следующими в одно значение - таким образом получается резкий скачек на 15-ти битные значения. (в приложении к данной задаче это скорее оверхед) Но можно сделать гораздо интереснее числа >= 256 - 2**n интерперетировать как n бит должны присоединиться к следующему байту
для n=4 пример: Числа большие либо равные 256-2**4 = 240 // что в 2-чной b11110000 т.е.
- с одной стороны мы совсем не много потеряли в доступном однобайтовом диапазоне 240/256 составляют 93.75% байтового диапазона
- с другой стороны вторым байтом мы опционально получаем 12-ти битную индексацию вплоть до 4095 что составляет 4095/256 = 1600% однобайтного
n - выбирается эмпирически. еще n может быть динамическим в зависимости от текущего числа (оно будет строго расти, потому можно апроксимировать простым правилом сколько старших значений должны резервироваться под "расширяющие" биты)
- с ростом n все сильнее будет срезаться однобайтовый диапазон. Но он всегда необходим для записи простых близнецов которые похоже попадаются бесконечно
в общем случае для всех последующих байт рекурсивно подходит та же конструкция расширения бит.
в свое время я реализовал алгебраическую систему с переменным основанием разряда и предикативным косвенным значением его максимума - это пожалуй апогей сжатия таким способом, но он ресурсоемок т.к. требует деления длинной арифметики
пример без длинной арифметики тут: https://codepen.io/impfromliga/pen/xxggRoq
- любители питона могут дешево интегрировать идею имя встроенную длинную арифметику (для объемных данных все равно придется числа дробить, иначе даже питон не справиться)
Вообще интересный вектор анализа простых чисел задает эта задача.
Есть ли какая-то неравномерность вероятности появления конкретных диапазонов?
UFO just landed and posted this here
Идея состоит в том, чтобы перемножить 14 миллионов первых простых чисел, прибавить 2. Убедиться, что последняя цифра не 5.
Полученное число будет иметь остаток от деления на любое из первых 14 миллионов простых чисел, равное 2.
То есть надо проверять делимость на числа после 14-миллионного простого числа, хотя до корня их гораздо больше, чем 14 миллионов.
Хочу составить простое число размером в 100 миллионов разрядов и выиграть 150 тысяч долларов :) EFF Cooperative Computing Awards. Вот только как доказать, что оно простое, за разумное время?
Полученное число будет иметь остаток от деления на любое из первых 14 миллионов простых чисел, равное 2.
То есть надо проверять делимость на числа после 14-миллионного простого числа, хотя до корня их гораздо больше, чем 14 миллионов.
Хочу составить простое число размером в 100 миллионов разрядов и выиграть 150 тысяч долларов :) EFF Cooperative Computing Awards. Вот только как доказать, что оно простое, за разумное время?
UFO just landed and posted this here
Алексей, а вы понимаете, что проверок делимости вам придется сделать не просто больше, чем 14 млн, а целых 10^50?
Мой вам совет: не переводите время попусту.
Мой вам совет: не переводите время попусту.
А вы прикинули сколько времени эти будут умножаться?
И зачем вам для этой задачи извращения с компактным хранением? 14 миллионов чисел, даже если взять 128 бит на число, будут занимать 224 мегабайта.
И зачем вам для этой задачи извращения с компактным хранением? 14 миллионов чисел, даже если взять 128 бит на число, будут занимать 224 мегабайта.
Идея понятна, сам подобным занимался.
Вопрос собственно только в том зачем вы вообще собрались хранить простые числа в БД да ещё в виде расстояний если единственное для чего они нужны — это получить их произведение???
Не проще ли вычислять простое число и сразу умножать его на предыдущие? И хранить нигде не надо будет.
Вопрос собственно только в том зачем вы вообще собрались хранить простые числа в БД да ещё в виде расстояний если единственное для чего они нужны — это получить их произведение???
Не проще ли вычислять простое число и сразу умножать его на предыдущие? И хранить нигде не надо будет.
вообще-то надо признать двойку простым числом и к произведению прибавлять единицу. Полученное число не проверять — оно однозначно простое. Для начала можно ознакомиться с доказательством Эвклида бесконечности множества простых чисел. На мой взгляд — вообще самое элегантное из доказательств.
А где будем хранить 10107.7 временных чисел? Ведь для проверки вашего полученного волшебного числа, вам нужно будет найти простые на диапазоне 2.7*108..Sqrt(N)
очередной диванный математик не понимает, что такое 100 Миллионов разрядов))
1) Последняя цифра будет не 5. Она точно будет равна 2, так как в произведении будут присутствовать множители 2 и 5, что даст нам один ноль в десятичной записи.
2) Нет, остаток от деления на 2 будет равен 0, поэтому число будет составным.
2) Нет, остаток от деления на 2 будет равен 0, поэтому число будет составным.
Это не способ получить длинное простое число.
2*3*5*7+2 делится на 2.
Ваша идея, по всей вероятности, основана на известном доказательстве того факта, что простых чисел бесконечно много.
Дескать, допустим, что простых чисел конечное количество, перемножим их все, прибавим 1, и получим число, которое не делится ни на одно из известных простых чисел, значит есть бОльшее простое число.
Так вот, это доказательство не является конструктивным. Оно не говорит, какое именно простое число болшее перемноженных существует.
Как уже написали, не переводите время попусту. Потратьте его лучше на углубленное изучение теории чисел.
2*3*5*7+2 делится на 2.
Ваша идея, по всей вероятности, основана на известном доказательстве того факта, что простых чисел бесконечно много.
Дескать, допустим, что простых чисел конечное количество, перемножим их все, прибавим 1, и получим число, которое не делится ни на одно из известных простых чисел, значит есть бОльшее простое число.
Так вот, это доказательство не является конструктивным. Оно не говорит, какое именно простое число болшее перемноженных существует.
Как уже написали, не переводите время попусту. Потратьте его лучше на углубленное изучение теории чисел.
Формула может быть двух видов:
1) P+1, где в P используется множитель 2.
2) P+2, где в P НЕ используется множитель 2.
Доказательство Евклида вполне логичное. Сначала он принял на веру некоторое утверждение, затем пришел к противоречию, вывод: изначальное утверждение неверно. Знать значение простого числа в качестве делителя для каждого (произведения плюс 1) нет смысла: достаточно знать, что оно существует, что и показано Евклидом.
1) P+1, где в P используется множитель 2.
2) P+2, где в P НЕ используется множитель 2.
Доказательство Евклида вполне логичное. Сначала он принял на веру некоторое утверждение, затем пришел к противоречию, вывод: изначальное утверждение неверно. Знать значение простого числа в качестве делителя для каждого (произведения плюс 1) нет смысла: достаточно знать, что оно существует, что и показано Евклидом.
А почему вы решили, что такое число будет простым?
Смотрите, считаем произведение в Maxima:
(%i1) 3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2;
(%o1) 278970415063349480483707697
Видим, что последняя цифра не 5.
Теперь факторизуем:
(%i2) factor(3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2);
(%o2) 107 229 2832808637 4019033726627
и вуаля, число распадается на простые множители, которых не было в исходном ряде и которые превышают любое из чисел исходного ряда.
Так что для проверки простоты 100M значного числа вам нужно его факторизовать. Вы к этому готовы?
Смотрите, считаем произведение в Maxima:
(%i1) 3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2;
(%o1) 278970415063349480483707697
Видим, что последняя цифра не 5.
Теперь факторизуем:
(%i2) factor(3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71+2);
(%o2) 107 229 2832808637 4019033726627
и вуаля, число распадается на простые множители, которых не было в исходном ряде и которые превышают любое из чисел исходного ряда.
Так что для проверки простоты 100M значного числа вам нужно его факторизовать. Вы к этому готовы?
Хорошо, когда у задачи есть цель в виде чисел с плавающей точкой в базе данных какого-нибудь европейского банка. Это придает сил…
Чего-то я не понимаю. Вот обычное решето Эратосфена: pastebin.com/ck9kuEMg
700к считает примерно за секунду (нужно взять хотя бы 15М чисел).
20М считает секунд за 40.
Вывод не считаю, поскольку не зависит от алгоритма. Зачем решето Аткина?
700к считает примерно за секунду (нужно взять хотя бы 15М чисел).
20М считает секунд за 40.
Вывод не считаю, поскольку не зависит от алгоритма. Зачем решето Аткина?
> А расстояние между соседними простыми числами всегда должно быть небольшим, предположил, что уместится в один байт.
смелое предположение.
смелое предположение.
Меня вот только начальные данные смутили… В смысле, то что 700тыс. чисел вы считали аж 3 часа, при этом не когда-то давно, а буквально «давеча». Разве что на бейсике, нет?
У меня просто аналогичная задача стояла лет 10 назад, ещё во времена модемного интернета. Хотелось насчитать праймов для хэш-таблички. Компы были ещё 32-битными, так что больше было не нужно. Я просто взял блоб на 512Мб и считал в нём битмаской (как раз 2^32 бит) решетом Эратосфена. На 1-поточном 32-битном 4-м пентиуме это заняло какое-то незначительное время (то ли 5, то ли 10 минут, а возможно и намного меньше — за давностью лет уже не помню). Но никак не 3 часа! Потому собственно, и удивляюсь: как так?
(ЗЫ: по итогу мне нужны были не все числа, а с шагом увеличения в 1.2 раза. Потому вывод дополнительно проредил и табличку потом поместил в код хэша)
У меня просто аналогичная задача стояла лет 10 назад, ещё во времена модемного интернета. Хотелось насчитать праймов для хэш-таблички. Компы были ещё 32-битными, так что больше было не нужно. Я просто взял блоб на 512Мб и считал в нём битмаской (как раз 2^32 бит) решетом Эратосфена. На 1-поточном 32-битном 4-м пентиуме это заняло какое-то незначительное время (то ли 5, то ли 10 минут, а возможно и намного меньше — за давностью лет уже не помню). Но никак не 3 часа! Потому собственно, и удивляюсь: как так?
(ЗЫ: по итогу мне нужны были не все числа, а с шагом увеличения в 1.2 раза. Потому вывод дополнительно проредил и табличку потом поместил в код хэша)
> Таким образом, 141 — максимально-возможное расстояние по простое число значением до 1 миллиарда.
Вы, наверное, хотели сказать, что 282 (вдвое большее) — максимальное возможное расстояние.
Первое число, для которого половина расстояния между простыми перестанет помещаться в один байт, — это 304 599 508 537. Его разность со следующим простым равна 514.
По-английски это называется prime gap и им посвящена обширная литература. Можно начать хотя бы с википедии.
Вы, наверное, хотели сказать, что 282 (вдвое большее) — максимальное возможное расстояние.
Первое число, для которого половина расстояния между простыми перестанет помещаться в один байт, — это 304 599 508 537. Его разность со следующим простым равна 514.
По-английски это называется prime gap и им посвящена обширная литература. Можно начать хотя бы с википедии.
«Есть идея, как еще сильнее сжать БД простых чисел» © Хранить их в виде программы, которая их вычисляет. Тогда можно все простыe, меньшие n, запаковать в архив длины O(log n). Фантастическое, экспоненциальное сжатие данных!
Я намекаю на то, что чем более хитрый алгоритм сжатия вы придумаете (с разделение на файлы, с хранением разных видов разностей, разделенных на что-нибудь), тем дольше будет длиться распаковка вплоть до того момента, когда она сравняется с вычислением простых чисел на лету при помощи primegen.
Я намекаю на то, что чем более хитрый алгоритм сжатия вы придумаете (с разделение на файлы, с хранением разных видов разностей, разделенных на что-нибудь), тем дольше будет длиться распаковка вплоть до того момента, когда она сравняется с вычислением простых чисел на лету при помощи primegen.
(сорри, промахнулся веткой)
Интересно, как же решето получилось так неудачно?
Код на питончике
делает 726517 простых секунд за 30.
Интересно, как же решето получилось так неудачно?
Код на питончике
def eratosthenes(N):
simp, nonsimp = [2], set()
for i in range(3, N + 1, 2):
if i not in nonsimp:
nonsimp |= {j for j in range(3 * i, N + 1, 2 * i)}
simp.append(i)
return simp
print(len(eratosthenes(11 * 10 ** 6)))
делает 726517 простых секунд за 30.
Насколько я понимаю Python, у вас реализовано не решето Эратосфена (сложность N log log N), а что-то порядка N^2, из-за того, что операция объединения множеств |= занимает линейное время по каждому из аргументов.
Операция |= занимает время порядка N / 2i (количество элементов в добавляемом множестве).
В питоне операции с множествами имеют O(1).
N^2 на 11 миллионах замер бы навсегда…
В питоне операции с множествами имеют O(1).
N^2 на 11 миллионах замер бы навсегда…
Вероятно, вы правы. Но тогда почему в пайтон-вики (ссылка в предыдущем комментарии) пишется иное?
Вы уверены, что после |= не приходится реаллоцировать все множество на новое место в памяти или что-нибудь в этом роде?
Вы уверены, что после |= не приходится реаллоцировать все множество на новое место в памяти или что-нибудь в этом роде?
Там всё устроено следующим образом: в питоне множества — это хеш-таблицы. Сначала создаётся таблица на 16 элементов. По заполнении 2/3 происходит реаллокация с увеличением размера в 4 раза. По достижении размера в 32768 таблица не учетверяется, а удваивается. Таким образом у нас будет O(log n) реаллокаций. Практически все они произойдут в момент добавления нечётных чисел, делящихся на три. То есть мы сразу фигакаем хеш-таблицу на 2^(log(N/6) + 1) элементов, а дальше её потихоньку заполняем и другими не-простыми.
Посмотрел в вики. Если было бы написано
nonsimp = nonsimp | {j for j in range(3 * i, N + 1, 2 * i)}
то было бы O(сумма элементов там и там)
Но мы подливаем в существующее множество, поэтому имеем O(количество добавляемых элементов)
nonsimp = nonsimp | {j for j in range(3 * i, N + 1, 2 * i)}
то было бы O(сумма элементов там и там)
Но мы подливаем в существующее множество, поэтому имеем O(количество добавляемых элементов)
Самое неправильное — это использование хэша вместо массива. Асимптотика, конечно, у них обоих O(1), но константы очень сильно разные.
По мелочи:
— вычёркивание, начинающееся с
— после того, как
По мелочи:
— вычёркивание, начинающееся с
3 * i, теряет кучу времени, повторяя заведомо уже вычеркнутое до i * i,— после того, как
i достигнет корня из N, операция |= вообще молотит вхолостую.import array
def eratosthenes(N):
# nonsimp[j] corresponds to 2j+1
simp, nonsimp = [2], array.array('b', [0 for i in xrange((N + 1) // 2)])
i = 3
while i * i <= N:
if not nonsimp[(i - 1) // 2]:
for j in xrange((i * i - 1) // 2, (N + 1) // 2, i):
nonsimp[j] = 1
simp.append(i)
i += 2
simp.extend([2 * j + 1 for j in xrange((i - 1) // 2, (N + 1) // 2) if not nonsimp[j]])
return simp
print(len(eratosthenes(11 * 10 ** 6)))Действительно, про i * i я не задумывался. Про корень из N я забил, в питоне оно слабо влияет на время.
У меня для вас плохие новости: ваш алгоритм быстрее всего в два раза…
А после оптимизаций аналогичных вашим на моём компе 2.9с к 2.3с.
В целом вы правы, константы разные, но прикол в том, что в питоне множества и словари молниеносно быстры, в то время как обычная арифметика не так, чтобы летает (по сравнению с сями). Поэтому если цель сделать что-то быстро, то нет нужды заморачиваться.
константы очень сильно разные
У меня для вас плохие новости: ваш алгоритм быстрее всего в два раза…
А после оптимизаций аналогичных вашим на моём компе 2.9с к 2.3с.
В целом вы правы, константы разные, но прикол в том, что в питоне множества и словари молниеносно быстры, в то время как обычная арифметика не так, чтобы летает (по сравнению с сями). Поэтому если цель сделать что-то быстро, то нет нужды заморачиваться.
А после оптимизаций аналогичных вашим на моём компе 2.9с к 2.3с.
А покажите версию после оптимизаций, интересно.
def eratosthenes(N):
simp, nonsimp = [2, 3], {i for i in range(3, N + 1, 3)}
for i in range(5, int(N ** 0.5), 2):
if i not in nonsimp:
nonsimp |= {j for j in range(i * i, N + 1, 2 * i)}
simp.append(i)
simp.extend([j for j in range(i, N + 1, 2) if j not in nonsimp])
return simp
print(len(eratosthenes(11 * 10 ** 6)))
Там есть ещё возможности оптимизировать, но они дурацкие и дают малый прирост.
Мне нравится такой подход: программа (зачастую стороннее ПО) выполняет свою работу, результатом ее работы должен стать, например, файл. После чего эта программа уже не нужна. С полученным файлом можно работать, используя другое ПО. Таким образом получается пошаговое получение результатов.
То есть разработчик не связан какой-то тучей программ, программа выдала результат, он сохранил результат и забыл про нее, сосредоточился на дальнейшем решении задач. И вот так, маленькими шажками, как маленький ребенок :)
То есть разработчик не связан какой-то тучей программ, программа выдала результат, он сохранил результат и забыл про нее, сосредоточился на дальнейшем решении задач. И вот так, маленькими шажками, как маленький ребенок :)
А можно для каждого числа сохранять количество делителей, отличающихся от единицы и самого числа. Простые числа — это частный случай с таким количеством делителей равным нулю.
Вообще интересно построить какие-нибудь графики по этим данным… например чтобы увидеть, как количество простых чисел уменьшается с увеличением x…
y=количество_простых_чисел_до(x)
по идее должно быть что-то типа sqrt(x)
ну и дальше поиграть с масштабами, чтобы понять что за кривая.
Вообще интересно построить какие-нибудь графики по этим данным… например чтобы увидеть, как количество простых чисел уменьшается с увеличением x…
y=количество_простых_чисел_до(x)
по идее должно быть что-то типа sqrt(x)
ну и дальше поиграть с масштабами, чтобы понять что за кривая.
Нет, y ~ x / ln x. Это утверждение теоремы о распределении простых чисел.
График количества делителей (правда с учетом единицы и самого числа).
График количества делителей (правда с учетом единицы и самого числа).
В чем смысл статьи?
Автор открыл для себя дельта-кодирование?
2/3 текста занимает листинг программы, считающей (обожемой) статистику по расстоянию между соседними простыми числами. Зачем он? Кому он может оказаться полезен?
В чем состоит тайна простых чисел, анонсированная в первой строке? В том, что они… хммм… простые?
И, наконец, при чем тут вообще Big Data?
Детский сад какой-то, чесслово.
Автор открыл для себя дельта-кодирование?
2/3 текста занимает листинг программы, считающей (обожемой) статистику по расстоянию между соседними простыми числами. Зачем он? Кому он может оказаться полезен?
В чем состоит тайна простых чисел, анонсированная в первой строке? В том, что они… хммм… простые?
И, наконец, при чем тут вообще Big Data?
Детский сад какой-то, чесслово.
Тогда встал вопрос, как сохранить 14 миллионов простых чисел?
Можно же использовать длинную арифметику. Это же проще, поддерживается в ряде языков (Java, .Net). Да, вычисления могут быть чуть дольше. Зато код сократится.
del
Пусть это здесь полежит:
gmplib.org/
github.com/libtom/libtommath
github.com/infusion/PHP/tree/master/ext/bcmath/libbcmath (хоть и лежит в дистрибутиве php, вполне самостоятельна)
gmplib.org/
github.com/libtom/libtommath
github.com/infusion/PHP/tree/master/ext/bcmath/libbcmath (хоть и лежит в дистрибутиве php, вполне самостоятельна)
700к чисел за 3 часа — это на телефоне что ли считалось?
Я простыми числами интересовался лет 10 назад (на совершенно дилетантском уровне), когда у меня был Celeron-667 со 128 метрами памяти — и именно память меня лимитировала, поскольку уход в своп катастрофически снижал скорость. Но если не превышать, все считалось быстро.
Ну в общем, я считал решето Эратосфена, в котором каждое число было битом, причем за пропуском четных, как заведомо не простых. То есть число не кодировалось непосредственно, а задавалось позицией в массиве. В каждом байте таким образом содержалось 16 чисел, в каждом int — 64 числа. И бегал я по этому массиву Битовыми масками.
Точную производительность уже не помню, есессно, но ни про какие 3 часа речи не шло. Несколько минут может. Это на той технике.
Я простыми числами интересовался лет 10 назад (на совершенно дилетантском уровне), когда у меня был Celeron-667 со 128 метрами памяти — и именно память меня лимитировала, поскольку уход в своп катастрофически снижал скорость. Но если не превышать, все считалось быстро.
Ну в общем, я считал решето Эратосфена, в котором каждое число было битом, причем за пропуском четных, как заведомо не простых. То есть число не кодировалось непосредственно, а задавалось позицией в массиве. В каждом байте таким образом содержалось 16 чисел, в каждом int — 64 числа. И бегал я по этому массиву Битовыми масками.
Точную производительность уже не помню, есессно, но ни про какие 3 часа речи не шло. Несколько минут может. Это на той технике.
Я бы порекомендовал автору всесторонне изучить сайт Kim Walisch — primesieve
Fast C/C++ prime number generator — и код самой primesieve; реализация шикарная, полированная, ибо человек лет 15 серьезно этим вопросом занимается. Работает primesieve с сумасшедшей производительностью даже на настольном скромном тазике, а подробности реализации сегментированного решета и wheel факторизации полностью документированы. Однако, он явным образом пишет, что «primesieve can generate primes and prime k-tuplets up to 2^64» и всё, край географии. Интересно, почему. Наверное он просто такой задачи себе не ставил, сделать больше.
Fast C/C++ prime number generator — и код самой primesieve; реализация шикарная, полированная, ибо человек лет 15 серьезно этим вопросом занимается. Работает primesieve с сумасшедшей производительностью даже на настольном скромном тазике, а подробности реализации сегментированного решета и wheel факторизации полностью документированы. Однако, он явным образом пишет, что «primesieve can generate primes and prime k-tuplets up to 2^64» и всё, край географии. Интересно, почему. Наверное он просто такой задачи себе не ставил, сделать больше.
Записал в файл простые числа в бинарном виде сплошняком «бит к биту» так, что получился файл размером 126 Кб. Сжал его архиватором 7-Zip методом сжатия Deflate на уровне сжатия Ультра. Архив получился меньше оригинального файла всего лишь на 3%. Это говорит о том, что в последовательности простых чисел практически нет никакой зависимости.
Sign up to leave a comment.
База данных простых чисел