Контрольные суммы больших частей простых чисел? (для проверки)

Question

Существуют ли какие-нибудь умные алгоритмы для вычисления высококачественных контрольных сумм на миллионы или миллиарды простых чисел? То есть с максимальной способностью обнаружения ошибок и, возможно, с возможностью сегментирования?

Мотивация:

Маленьких простые числа - до 64 бит в размерах - может быть просеивают по требованию на сумму миллионов в секунду, с помощью небольшой битовой карты для просеивания потенциальных факторов (до 2^32-1) и вторую растровую карту для просеивания чисел в целевом диапазоне.

Алгоритм и реализация достаточно просты и понятны, но дьявол находится в деталях: значения имеют тенденцию нажимать или превышать пределы встроенных интегральных типов везде, граничные случаи изобилуют (так сказать) и даже различиями в плавающих точная строгость может привести к поломке, если программирование недостаточно защищено. Не говоря уже о хаосе, который оптимизирующий компилятор может нанести, даже на уже скомпилированный, уже проверенный код в статическом lib (если используется генерация кода времени привязки). Не говоря уже о том, что более быстрые алгоритмы, как правило, намного сложнее и, следовательно, еще более хрупкие.

Это имеет два последствия: результаты испытаний в основном бессмысленны, если тесты не выполняются с использованием окончательного исполняемого изображения, и очень желательно проверить правильную работу во время выполнения во время обычного использования.

Проверка на заранее рассчитанные значения даст наивысшую степень уверенности, но требуемые файлы являются большими и неуклюжими. Текстовый файл с 10 миллионами простых чисел имеет порядок 100 МБ несжатого и сжатие более 10 МБ; для хранения байтовых кодировок требуется один байт на штрих-код, а энтропийное кодирование может в лучшем случае уменьшить размер до половины (5 МБ для 10 миллионов простых чисел). Следовательно, даже файл, который покрывает только малые факторы до 2^32, будет весить около 100 МБ, а сложность декодера будет превышать сложность самого оконного решета.

Это означает, что проверка файлов невозможна, за исключением проверки окончательной версии для вновь созданного исполняемого файла. Не говоря уже о том, что надежные файлы нелегко найти. Prime Pages предлагают файлы для первых 50 миллионов простых чисел, и даже удивительные primos.mat.br идут только до 1 000 000 000 000. Это печально, так как многие граничные случаи (== потребность в тестировании) происходят между 2^62 и 2^64-1.

Это оставляет контрольные суммы. Таким образом, требования к пространству будут незначительными и будут только пропорциональны количеству тестовых случаев. Я не хочу требовать наличия приличной контрольной суммы, такой как MD5 или SHA-256, и с целевыми номерами, которые являются основными, должно быть возможно создать высококачественную контрольную сумму с высоким разрешением с некоторыми простыми операциями с номерами самих себя.

Это то, к чему я придумал. Исходный дайджест состоит из четырех 64-битных номеров; в конце его можно сложить до желаемого размера.

for (unsigned i = 0; i < ELEMENTS(primes); ++i) 
    { 
     digest[0] *= primes[i];    // running product (must be initialised to 1) 
     digest[1] += digest[0];    // sum of sequence of running products 
     digest[2] += primes[i];    // running sum 
     digest[3] += digest[2] * primes[i]; // Hornerish sum 
    } 

В двух (не зависимых) мулов в расцвете сил скорость приличная достаточно, и для простой суммы, за исключением каждого из компонентов всегда раскрыли все ошибки я пытался прокрасться мимо дайджеста. Однако я не математик, и эмпирическое тестирование не является гарантией эффективности.

Существуют ли некоторые математические свойства, которые можно использовать для проектирования, а не «повар», как я, - разумная, надежная контрольная сумма?

Возможно ли сконструировать контрольную сумму таким образом, чтобы она была ступенчатой, в том смысле, что поддиапазоны могут обрабатываться отдельно, а затем результаты, объединенные с небольшим количеством арифметических действий, дают такой же результат, как если бы весь диапазон был контрольная сумма за один раз? То же самое, что и все современные реализации CRC, как правило, имеют в настоящее время, чтобы обеспечить параллельную обработку.

EDIT Обоснование текущей схемы заключается в следующем: количество, сумма и произведение не зависят от порядка, в котором простые числа добавляются в дайджест; они могут быть вычислены на отдельных блоках, а затем объединены. Контрольная сумма зависит от порядка; это его смысл. Однако было бы неплохо, если бы две контрольные суммы двух последовательных блоков могли быть объединены так или иначе, чтобы дать контрольную сумму объединенного блока.

Количество и сумма иногда может быть проверена от внешних источников, как некоторые последовательности на oeis.org, или против источников, таких как партии 10 миллионов простых чисел в primos.mat.br (индекс дает первый и последний штрих, число == 10 миллионов подразумевается). Однако такой удачи для продукта и контрольной суммы.

Перед тем, как выбросить большое время и вычислительную мощность при вычислении и проверке дайджестов, охватывающих весь спектр малых факторов до 2^64 Я хотел бы услышать, что думают эксперты об этом ...

схема Я в настоящее время тест-драйв в 32-битном и 64-битном варианте выглядит следующим образом:

template<typename word_t> 
struct digest_t 
{ 
    word_t count; 
    word_t sum; 
    word_t product; 
    word_t checksum; 

    // ... 

    void add_prime (word_t n) 
    { 
     count += 1; 
     sum  += n; 
     product *= n; 
     checksum += n * sum + product; 
    } 
}; 

Это имеет то преимущество, что 32-разрядные переваривать компоненты равны нижней половинах соответствующего 64 что означает, что только 64-битные дайджесты должны быть вычислены, даже если требуется быстрая 32-битная проверка. 32-битную версию дайджеста можно найти в этом простом sieve test program @ pastebin для практических экспериментов. Полный Monty в пересмотренной, шаблонизированной версии можно найти в новой пасте для a sieve that works up to 2^64-1.

Answer 1

Я проделал большую работу по параллелизации операций над архитектурами Cell. Это похоже.

В этом случае, я хотел бы использовать хэш-функцию, которая быстро и, возможно, дополнительные (например, xxHash или MurmurHash3) и hash list (который является менее гибкой специализацией в Merkle Tree).

Эти хеши чрезвычайно быстры. Удивительно трудно поправиться с каким-то простым набором операций. Список хешей обеспечивает параллелизм - разные блоки списка могут обрабатываться разными потоками, а затем хешировать хеши. Вы также можете использовать Merkle Tree, но я подозреваю, что это было бы просто сложнее без особых преимуществ.

• Практически разделите свой диапазон на выровненные блоки - мы будем называть эти микроблоки. (Например, microblock это диапазон, такой как [п < < 15, (п + 1) < < 15))
• Для того, чтобы обрабатывать microblock, вычислить, что нужно вычислить, добавить его в буфер, хэш-буфер. (Инкрементная хеш-функция будет предоставлять меньший буфер. Буфер не должен заполняться с одинаковой длиной данных каждый раз.)
• Каждый хэш-метка будет размещен в .
• Разделите круговой буфер на хешируемые блоки («макроблоки»).Постепенно хэшируйте эти макроблоки в правильном порядке по мере их появления или если больше нет микроблоков.
• Получившийся хэш - это тот, который вы хотите.

Некоторых дополнительные примечания:

• Я рекомендую дизайн, где нити Оставляют ряд незавершенных микроблоков, что кольцевой буфер имеет пространство для, процесса их, сбросить значения в кольцевом буфере, и повторите.
• Это дополнительное преимущество, которое вы можете решить, сколько потоков вы хотите использовать «на лету». например при запросе нового диапазона микроблоков, каждый поток может обнаружить, что слишком много/мало потоков работает и настраивается.
• У меня лично был бы поток, добавляющий последний хэширование микроблока в макроблок, очищающий этот макроблок. Меньше параметров для настройки таким образом.
• Поддержание кругового буфера не так сложно, как кажется - макроблок самого низкого порядка, все еще необработанный, определяет, какая часть «пространства макроблоков» представляет собой круговой буфер. Все, что вам нужно, это простой счетчик, который при необходимости увеличивает, чтобы выразить это.
• Еще одно преимущество заключается в том, что, поскольку потоки регулярно проходят резервный/рабочий/резервный/рабочий цикл, поток, который неожиданно медленный, не будет препятствовать времени работы почти так же плохо.
• Если вы хотите сделать что-то менее надежное, но более легкое, вы можете отказаться от работы с помощью «полосатого» шаблона - выбрать максимальное количество потоков (N) и обработать каждый поток каждый N-й микроблок (смещается по его «идентификатору» потока) и хеширует результирующие макроблоки на поток. Затем, в конце, хеш макроблока хэши из N потоков. Если у вас меньше N потоков, вы можете разделить работу на количество требуемых потоков. (например, 64 макс потока, но три реальных потока, поток 0 обрабатывает 21 виртуальный поток, поток 1 обрабатывает 21 виртуальный поток, а поток 2 обрабатывает 22 виртуальных потока - не идеально, но не страшно). Это по сути мелкое дерево Меркель вместо хэш-список.

Answer 2

Я отвечаю на этот вопрос еще раз во втором ответе, так как это очень разные, и мы надеемся, лучше лавировать:

Мне пришло в голову, что вы делаете, в основном ищет контрольную сумму, не над списком простых чисел, но в диапазоне битового поля, где число является простым (бит установлен в 1), или нет (бит установлен в 0). У вас будет намного больше 0, чем у 1 для любого интересного диапазона, поэтому вы, надеюсь, должны сделать только операцию для 1-го.

Обычно проблема с использованием тривиального хэша в любом порядке заключается в том, что они плохо обрабатывают множественность и не обращают внимания на порядок. Но вы не заботитесь обо всех этих проблемах - каждый бит может быть установлен или отменен только один раз.

С этой точки зрения побитовое исключение или добавление должно быть просто прекрасным, если оно сочетается с хорошей функцией хэширования индекса бита - то есть найденного штриха. (Если ваши простые числа являются 64-битными, вы можете воспользоваться некоторыми функциями here.)

Таким образом, для максимальной простоты, которая даст вам одинаковое значение для любого набора диапазонов входных сигналов, да, придерживайтесь хэширования и сочетая его с простой операцией, такой как вы. Но переход на традиционную хеш-функцию, которая кажется «случайной» с учетом ее ввода - hash64shift на связанной странице, скорее всего, то, что вы ищете. Вероятность значимого столкновения является отдаленной. Однако большинство хеш-функций воняют - убедитесь, что вы выбрали тот, который, как известно, обладает хорошими свойствами. (Лавины хорошо и т. Д.). Томас Ванг обычно не так уж плох.(Боб Дженкин - фантастический, но он придерживается в основном 32-битных функций. Хотя его функция смешивания на связанной странице очень хороша, но, вероятно, может быть переполнена.)

Распараллеливание проверки, очевидно, тривиально, размер и усилие кода значительно сокращенно от моего другого ответа, и гораздо меньше синхронизации и почти нет буферизации, которая должна произойти.

Answer 3

Отличный ответ Каганара демонстрирует, как заставить все работать, даже если дайджесты смежных блоков не могут быть объединены математически, чтобы дать тот же результат, что и комбинированный блок был переварен.

Единственный недостаток его решения состоит в том, что результирующая структурная структура по необходимости является довольно жесткой, а скорее PKI с ее официальной всеохватывающей иерархией сертификатов против «партизанского стиля» PGP, сеть доверия которой охватывает только несколько субъектов которые представляют интерес. Другими словами, для этого требуется создание глобальной структуры/иерархии адресации.

Это дайджест в его нынешнем виде; изменение в том, что порядок-зависимая часть была упрощена до его необходимого минимума:

void add_prime (word_t n) 
{ 
    count += 1; 
    sum  += n; 
    product *= n; 
    checksum += n * count; 
} 

Вот уроки, извлеченные из практической работы с этим переваривать:

• count, sum и product (т.е. частичный примерный размер шрифта по модулю) оказалось чрезвычайно полезным из-за того, что они относятся к вещам, найденным в других частях мира, например, определенным спискам в OEIS
• count и sum были очень полезны, потому что первый имеет тенденцию быть естественно доступным при манипулировании (генерировании, использовании, сравнении) партий простых чисел, и сумма легко вычисляется «на лету» с нулевым усилием; это позволяет частично проверять существующие результаты, не пропуская весь процесс создания и обновления дайджеста, и без накладных расходов двух - сравнительно медленных умножений
• count также чрезвычайно полезен, поскольку он по необходимости должен быть частью любой встроенной надстрочной надстройки на системах дайджеста, и, наоборот, он может направлять поиск прямо к блоку (диапазону), содержащему n-мерное простое, или к блокам, перекрываемым n-м через (n + k) -го числа
• зависимость заказа четвертого компонента (checksum) оказались менее медлительными, чем предполагалось, поскольку небольшие штрихи имеют тенденцию «встречаться» (создаваться или использоваться) в порядке, в ситуациях, когда может потребоваться проверка.
• зависимость порядка контрольной суммы - и отсутствие сочетаемости - сделала ее совершенно бесполезной вне конкретного блока, для которого она была создана
• Структуры вспомогательной программы фиксированного размера - как и вездесущие малые коэффициенты - лучше всего проверить как необработанную память для запуск самоконтроля, вместо того, чтобы запускать на них сводку простых чисел; это значительно снижает сложность и ускоряет вещи на несколько порядков

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

Для проверки фиксированных диапазонов (например, при самотестировании) компонент контрольной суммы по-прежнему полезен. Любая другая контрольная сумма - моральный эквивалент CRC - была бы столь же полезна для этого и, вероятно, быстрее.Было бы еще более полезно, если бы можно было найти независимый от заказа способ (комбинационный) способ дополнения разрешения первых трех компонентов. Расширение разрешения за пределами первых трех компонентов наиболее важно для больших вычислительных усилий, таких как просеивание, проверка и переваривание триллионов простых чисел для потомков.

Одним из таких кандидатов для независимого от заказа интегрированного четвертого компонента является сумма квадратов.

В целом дайджест оказался весьма полезным, как есть, несмотря на недостатки, связанные с компонентом контрольной суммы. Лучший способ взглянуть на дайджест, вероятно, состоит из «характерной» части (первые три компонента, комбинируемой) и части контрольной суммы, которая применима только для конкретного блока. Последнему можно было бы также заменить хеш любой желаемой резолюции. Решение Kaganar показывает, как эта контрольная сумма/хэш может быть интегрирована в систему, которая выходит за пределы одного блока, несмотря на присущую ему неразличимость.

резюме первоисточников количество, кажется, упал на обочину, так вот она:

• до 1,000,000,000,000 доступны в виде файлов с сайтов, как primos.mat.br
• до 2^64- 10 * 2^64 в супер-быстрого налив через primesieve.org консольной программы (трубы)
• до 2^64-1 - и за его пределами - с помощью программы gp/PARI (труб, около 1 млн штрихов/мин)