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

Мотивация:

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

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

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

Сравнение с предварительно вычисленными значениями даст наивысшую степень достоверности, но требуемые файлы большие и неуклюжие. Текстовый файл с 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, как правило, имеют в настоящее время для обеспечения параллельной обработки.

РЕДАКТИРОВАТЬ Обоснование текущей схемы заключается в следующем: количество, сумма и произведение не зависят от порядка, в котором простые числа добавляются в дайджест; они могут быть рассчитаны на отдельные блоки, а затем объединены. Контрольная сумма зависит от заказа; это его смысл существования. Однако было бы неплохо, если бы две контрольные суммы двух последовательных блоков можно было как-то объединить, чтобы получить контрольную сумму объединенного блока.

Количество и сумма иногда могут быть проверены по внешним источникам, как определенные последовательности на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-разрядную версию дайджеста можно найти в этом простомпрограмма проверки сита @ pastebin, для практических экспериментов. Полный Monty в пересмотренной, шаблонной версии можно найти в новой пасте длясито, которое работает до 2 ^ 64-1.