Pull to refresh

Comments 58

Круто сделано и хорошо написано, прочитал с удовольствием, читать легко и увлекательно даже дилетанту, на личном примере свидетельствую.
Вопрос про оценку эффективности сжатия. Сначала вам удалось достичь примерно такого же, как в случае 7-zip, примерно восьмикратного сжатия с использованием разностей без использования их структуры. Потом, поиграв с пилообразными закономерностями в распределении разностей, вы обошли 7-zip почти в полтора раза, добившись более чем 11-кратного сжатия, но этот результат 7-zip смог ужать на 5%. То есть выходит, что если 7-zip может поджать, есть что поджимать, но если не может, то это ничего не значит.
Можно ли оценить эффективность сжатия от предельно возможного, как-то сравнивая результат сжатия с распределением случайной величины, с белым шумом? (Насколько я понимаю с дилетантских позиций, случайная величина несжимаема).
Может, там до идеально возможного остается несколько процентов, которые труда не стоят, а может оказаться, что еще есть куда стремиться, хотя неясно, как.
Иными словами, вы в конце публикации попробовали как-то улучшить результат еще, но явного успеха уже не получается.
А можно ли просто оценить, насколько он вообще может быть улучшен в принципе?
Теорема Шеннона об источнике шифрования
Однако помимо статистических распределений бывают знания (эвристики) о структуре сжимаемых данных, на них наложить математических ограничений не получится, это, по сути, предел предсказательной возможности модели кодировщика (в пределе решением является алгоритм генерации последовательности по её номеру, см. «Архиватор Бабушкина» :))
Если уж говорить о количестве информации, то последовательность простых чисел можно сжать в пару килобайт. Именно столько займёт программа, которая эту последовательность на лету сгенерирует.

Другое дело что автор хотел получать числа быстрее чем генерируя их каждый раз, так что мы пытаемся найти баланс между размером файла и скоростью доступа. Для такого баланса теоретических формул не бывает.
Всё так. Алгоритм генерации простых чисел в этом смысле и будет эвристикой, знанием о структуре генерируемой последовательности.
UFO just landed and posted this here
Вроде как совершенно стандартный подход: если надо записывать числа, упорядоченные (или порядок которых не важен — тогда предварительно отсортировать) и находящиеся, как правило, на небольшом расстоянии друг от друга, то хорошо работает голомб-райсово кодирование дельт. Это касается не только простых чисел, а очень много чего.
UFO just landed and posted this here
Я пробовал. Именно эту разность, именно методом Хаффмана, именно на этом объеме, именно после изучения частот. Деталей уже не помню, но факт, что 7-zip, сжимал лучше чем моя реализация метода Хаффмана. С тех пор они и хранятся, (2---512)/2-1, и потом 7-zip. Что же касается 6 исключений то я вообще не заморачивался с ними, просто вбил их явно в программу распаковщик. Но я не ставил перед собой задачу хранить числа больше триллиона.
Интересно было бы посчитать интервалы и закодировать их в обычные 16-битные или 32-битные числа (можно даже пополам не делить и двойку не выкидывать), а потом скормить на вход, например, обычному gzip. По идее, он должен хорошо справиться с такой задачей.
UFO just landed and posted this here
Извините, не понял ваш комментарий.
Это значит, что в каждом числе последний бит заранее известен, а значит не несет никакой информации.
Это я прекрасно понимаю. Я высказал гипотезу, что gzip с такой избыточностью должен сам хорошо справиться.
Не думаю, что будет большая разница между традиционной компрессией последовательности простых и последовательности интервалов между простыми, между ними нет принципиальной разницы. Т.е., сжатие будет приличное, но не олимпийское. Пробовать, честно говоря, лень :)
В передаче биржевой информации часто возникает похожая задача, когда надо сжимать относительно большие числа с небольшой разницей. И в протоколе FAST используется красивое решение — 7-битные байты (поверх дельт, конечно же).

В байте 7 бит отдаются под информацию, а 8-й бит говорит, надо ли читать еще 1 байт, чтобы получить текущее значение. Таким образом, при хранении разрядность не ограничена в принципе, а место равно количеству байт, необходимых, чтобы разложить все значущие биты по 7. Также, плюс, что не требуются словари, и состояние алгоритма максимально простое.
Это всего лишь ленивый аналог алгоритма Хаффмана.
UFO just landed and posted this here
Это песочница какие тут могут быть объяснения :))

У меня такое чувство. что половина из отметившихся в комментариях не уловила, суть идеи в строго детерминированном характере частотности интервалов. Традиционное же кодирование исходит из некоторых общих представлений о данных. Поскольку частотность интервалов детерминирована, нет никаких проблем рассчитать эффективность любого другого метода кодирования, на последней диаграмме я несколько таких примеров привел. Есть предложение? Посчитайте сами. Итоги в студию.
За старание и за качественное изложение — несомненный плюс.
Но. Но к чему такая сложность? Для простых чисел, если это небольшие числа, то есть если это не всякие порядка 2^256, а как здесь меньше 2^40 вполне годится тупое хренение битовой маски. Есть правда одна «хитрость», но это хитрость достаточно очевидна.
Давай посчитаем. Пусть у нас есть простые до 10е12. Для хранения прямо вот просто битовой маски достаточно 1,25е11 бит. Это сразу же 116 ГиБ. Заметим также, что если взять произведение нескольких простых чисел, то простые числа могут попадать не на все, а только на некоторые остатки от деления на это произведение (кроме самых первых):
2 — только остаток 1
2*3=6 — только остатки 1 и 5
2*3*5=30 — только 1, 7, 11, 13, 17, 19, 23, 29 (8 чисел)
Для 2*3*5*7=210 можно тоже вручную посчитать, даже для 2*3*5*7*11=2310 можно маску сохранить. Дальше выигрыш совершенно несущественный.
В решете Эратосфена эту оптимизацию часто называют wheel optimization. Мы можем хранить не все биты, а только попадающие в остатки. То есть для «колеса» в 30 не все 30 бит, а только 8. Это даёт нам сразу менее 32 ГиБ
Раскодировать такое хранение на несколько порядков проще. Ну и кодировать прямо скажем — не занудно.

Для цикла 210 получается 48 значений остатков, т.е. хранить можно 48 бит из 210, это уже 26,6 ГиБ.
Для цикла 2310 получается 480 допустимых значений, это уже 24,19 ГиБ. И это уже лучше вашего результата :)

Ещё замечание (извиняюсь за спам).
Простые числа до 2^32 считаются сейчас вовсе не часы, а секунды или даже доли секунды. Это не отменяет того, что дальше считать всё сложнее и сложнее, но до 2^40 просеять не проблема.
Если эта тема интересует, есть primesieve.org, это опенсорсный проект на гитхабе. Там все разъяснения есть.

Триллион чисел генерируются за чуть больше двух минут на обычном ноутбуке (i7-7500U), что сравнимо со скоростью считывания 24ГБ данных с диска:


$ ./primesieve 1000000000000
Sieve size = 256 kilobytes
Threads = 4
100%
Primes: 37607912018
Seconds: 147.634

На моём ПК 60.91 с. Древнющий комп еще с сокетом 1366, 6 ядер (Xeon W3690). Процессор купил года 4 назад потому что было дёшево, хотя сейчас еще дешевле.

Результаты запуска на хорошем компьютере (E5-2697 v4 x 2)
Sieve size = 256 kilobytes
Threads = 36
100%
Primes: 37607912018
Seconds: 10.011

В пересчете на thread — ноздря в ноздрю :-P
2*3=6 — только остатки 1 и 5

Хочу заметить, что поэтому и появляются промежутки 2 и 4. На следующем шаге убираются числа, кратные 5, и появляются промежутки длиной 6. Потом кратные 7, и добавляются возможные промежутки 8, 10. И т.д.

Если хотите, почитайте ещё статью «Структура и случайность простых чисел».
Насколько я понял, там выявлена закономерность между параллельными рядами простых чисел. А раз есть формула — возможно, удастся повысить сжатие. Удачи!
Можно зайти с другой стороны — для всех простых, кроме 2, 3 и 5, остаток от деления на 30 может принимать одно из 8 значений: 1, 7, 11, 13, 17, 19, 23, 29. Можно с помощью битовой маски и деления на 30 упаковать в один байт информацию о том, являются ли простыми сразу 30 чисел. Чтобы упаковать информацию о всех числах до триллиона, надо чуть больше 4 гигабайт. Поиск ближайшего простого по значению тривиален. А вот по номеру так искать конечно не получится. И асимптотически такой метод проиграет кодированию интервалов.
надо чуть больше 4 гигабайт.

Вы ошибаетесь 1 триллион это 10^12, для 10^12/30 нужно 33_333_333_334 байт, то есть более 33 миллиардов байт. Это примерно 31,044 ГиБ (если поделить на 1024 три раза). Как раз это я и предложил выше.


А вот по номеру так искать конечно не получится.

Поиск по номеру можно легко оптимизировать, сохраняя промежуточные Pi(N) — количество простых чисел не превосходящих данное. Сохранять например одно число на 256 КиБ, то есть на 256102430=7864320 чисел. Это удобно, потому что потребует хранения всего 127157 чисел, а 256 килобайт — отлично ложится в L2 кэш процессора и посчитать биты тм достаточно просто.


И асимптотически такой метод проиграет кодированию интервалов.

Асимптотический проигрыш этой схемы хранения кодированию интервалов совсем не очевиден. На больших значениях интервалы будут расти, а значит будут требовать всё больших значений. При этом "плотность" заполнения битовой маски падает вместе с упомянутым Pi(N), который близок к n/ln(n). То есть очень медленно.

Markdown съел звёздочки.
Должно быть:


256 * 1024 * 30=7864320
Вы хотели сказать «нужно 33_333_333_334 бит»?
БАЙТ.
1_000_000_000_000 бит
каждые 8 бит хранят информацию о 30 числах.
1_000_000_000_000 / 30 = 33_333_333_334 пачек по 8 бит (посделняя 4 на хвостик). Пачка из 8 бит и есть байт
А можно поинтересоваться, для каких задач нужны таблицы простых чисел такого размера?
Я много-много лет назад хранил не сами числа, а просто порядок флагов простое-составное.
Для флага достаточно одного бита, плюс пропускаются четные — итого для 32-битных чисел сжатие в 64 раза. Реализация тривиальная, очень быстрый доступ по значению числа, но относительно медленный по номеру в последовательности простых.
Ничего не выйдет, чтобы хранить триллион чисел, потребуется 500 млрд бит или 58,2 ГБ что более чем в 2 раза больше чем у автора
Зато код тривиальный и очень быстрый. У автора доступ в произвольному числу наверняка гораздо (не в 2 раза явно) медленнее.
Обычное распределение простых 1TPrimo 37607912018
среди нечетных 999999999989/2 (делим на 2 т.к. четные исключаем) сжимается арифметическим кодированием до 24578934869 байт = 22.89 Гб. Если кодировать арифметическим интервалы между простыми можно выиграть еще.
UFO just landed and posted this here
До конца наверно не дочитали. Время доступа почти не отличается от времени доступа к несжатым данным.

Вопрос. Вот мы всячески наизголялись над массивом. А какие методы верификации результата у нас есть? Ну, проверить, что числа, которые получаем, простые — можно. А как проверить что ничего не пропустили?

Берем все числа в промежутке, который вызывает у Вас подозрения. И проверяем все по очереди :)
Вообще-то таблицы так и строят — берут все числа по очереди. Как тут пропустить что-то можно?
Например, для создания конкурентного преимущества. Или дыры в безопасности. Или (вставить дальше)
Гм, хорошая идея :) В голову не пришло.
Отдельные вещи можно проверить у альтернативных источников. Например, последнее простое в использованной мной таблице 999999999989, имеет порядковый номер 37607912018, здесь primes.utm.edu/nthprime этому можно получить подтверждение. Значит, во всяком случае пропусков нет. А вот проверить на предмет перестановок и подмен — тут увы. Только поэлементное сравнение с такой же таблицей, либо поштучная проверка на простоту. Собственно, этим-то простые и замечательны, что другого способа нет.

Сильное уменьшение таблицы может дать использование быстрого вероятностного теста на простоту и хранение тех чисел на которых этот тест "врёт" что оно простое. Например такого:


def fast_test(n):
    for p in [997, 32416190071]:
        if pow(p, n-1, n) != 1:
            return False
    return True

Можно подобрать таких свидетелей простоты (вместо 997 и 32416190071) для которых тест не ошибается если входные числа лежат в заданных пределах.

Вот тест посложнее, должен не врать до 1 трлн. Под pypy3 тестирует около 3 млн чисел в секунду.


код
def miller_rabin(n):
    if n == 2:
        return True

    if n % 2 == 0:
        return False

    A = [2, 13, 23, 1662803]
    if n in A:
        return True

    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for a in A:
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
И как это скажется на размере таблицы?

Он должен уменьшиться. Идея в том, чтобы бежать по числам (как сказали выше, можно рассматривать каждое 4-е число если работать в 30-ричной системе счисления) и проверять каждое из них каким-то быстрым тестом на простоту. Этот тест может давать ложноположительные срабатывания, но чисел на которых он это делает должно быть не так много и их можно сохранить отдельно.
Кроме того, можно строить таблицу на лету, например, с помощью решета эратосфена, что на хорошем компьютере быстрее, чем считать её с диска.

Наверно я чего-то не понял. Это уменьшит таблицу НАТУРАЛЬНЫХ чисел, исключив из них 3/4 и все неподозрительные на простоту. Таблицу ПРОСТЫХ это увеличит, добавив в нее помимо простых еще и подозрительные на простоту.
Построение на лету хорошо для разовых задач, но усложнение программирования ставит под вопрос выполнимость самих таких задач. Прикладные задачи потребуют дополнить построение на лету кэшированием и сложность программирования возрастет в разы.

Те простые числа, для которых быстрый тест на простоту не врёт, можно не включать в таблицу. 3/4 можно исключить, если рассматривать числа в 30-ричной системе и проверять только те, которые заканчиваются цифрами "1", "7", "11", "13", "17", "19", "23", "29".


Чтобы код не усложнялся, можно использовать готовую библиотеку для поиска простых чисел, например primesieve, https://primesieve.org/api/namespaceprimesieve.html. Тогда сложность уйдёт в библиотеку. Кеширование можно реализовать через внешний класс для каждого блока, например, по 10 000 тысяч чисел, что позволит значительно уменьшить потребление памяти программой, насколько я понял, примерно на 23ГБ для первого 1трлн простых. Хотя, таблица будет быстрее при случайном доступе к простым.

В принципе, байтовое представление интервалов в сочетании с блочно-индексной структурой можно использовать, несмотря на наличие интервалов > 512. Для этого надо к числам с таким интервалом принудительно привязать начала блоков. При этом исчезнет необходимость в их представлении — один блок закончился, новый начался с заданного значения.
Точно. За одним минусом — с этого момента восстановление простого по его порядковому номеру становится нетривиальной задачей, что уравнивает метод с более продвинутым.
7zip поддерживает дельта-сжатие:
7z a primes.7z -m0=Delta:4 -m1=LZMA:d19 primes1m.4

Разница на первом миллионе 32 битных простых в три раза (785827 против 258063)
Так, а можете объяснить, почему просто коды Хаффмана для кодировки интервалов хуже?
У Вас есть частотность интервалов, дальше их закодировать Хаффманом. Ну и делать отсечки каждые N элементов для более простой расшифровки.
Вроде должен давать теоретический минимум в хранении.
Арифметическое кодирование — наиболее близкий к теоретическому максимум сжатия вариант. Если речь идёт об исключительно вероятностном бесконтекстном кодировании без каких либо априорных знаний о кодируемом потоке. Если же речь идёт о сжатии именно последовательности простых чисел, то наиболее близким к предельному вариантом будет программа, генерирующая простые числа. Программа из примерно 5 — 25 строк на любом современном ЯП нагенерит бесконечный ряд простых чисел (хоть и долго), что даёт сжатие примерно в ∞ раз.
Попробую. Из графика частотности видно, что решающее значение для общего показателя компрессии имеют лишь несколько первых интервалов: 6, 12 и 2, 4, 8, 10. По сути без разницы, какие коды использовать — лишь бы эти несколько были наиболее короткими. В предложенном варианте они наиболее короткие.

Все простые числа большие 5 принадлежат множеству 6n+{1,5}, больше 29 множеству 5*6n+{1, множество простых чисел от 7 до 29} и так далее, 5*6*7n+{1,множество простых чисел от 11 до 209}. Можно кодировать выпадающие числа битовой матрицей, но если учесть, что выпадать будут произведения этмх простых чисел, например 6*4+1 это квадрат 5, то можно было бы кодировать множества выпадающих чисел как степени простых чисел, для каждого блока выделяя при этом разное число бит для каждого такого числа p1**n1*p2**n2*...

У меня статья есть про мое исследование здесь на хабре про общество ткачей https://habr.com/ru/articles/255527/

множество простых чисел от 11 до 209

а также их произведений. Проверять надо не простые числа, а взаимно простые с циклом колеса.

Sign up to leave a comment.

Articles