Существуют ли умные алгоритмы для вычисления качественных контрольных сумм для миллионов или миллиардов простых чисел? т.е. с максимальной способностью обнаружения ошибок и, возможно, сегментируемой?
Мотивация:
Небольшие простые числа — размером до 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 для практических экспериментов. . Полный Монти в исправленной, шаблонной версии можно найти в более новой пасте для решета, которое работает до 2^64-1< /а>.
