Во-первых, спасибо, что поделились своей программой и поработали над корректностью. Я думаю, что важно проводить тестирование, и я потратил время на просеивание вблизи границы размера, работая над своим кодом.
«Везде один и тот же результат: nada, zilch, niente». Вы недостаточно внимательно ищете. Есть много инструментов, которые делают это. Жаль, что Primesieve не доходит до 2 ^ 64-1, но это не значит, что ничего другого не подходит.
«Как тогда можно проверить правильную работу сита, близкого к 2^64?» Одна вещь, которую я сделал, это провел тест на крайний случай, который проходит через все комбинации начальных и конечных точек около 2 ^ 64-1, проверяя, что ряд методов дает одинаковые результаты. Это зависит от наличия списка этих простых чисел для начала, но есть много способов получить их. Это не только проверяет сито в этом диапазоне, но и проверяет условия начала/конца, чтобы убедиться, что там нет проблем.
Некоторые способы сгенерировать миллион простых чисел ниже 2^64:
time perl -Mntheory=:all -E 'forprimes { say } ~0-44347170,~0' | md5sum
Требуется ~ 2 с, чтобы сгенерировать 1 миллион простых чисел. Мы можем принудительно использовать другой код (Perl или GMP), использовать тесты на простоту и т. д. Много способов сделать это, включая, например, просто зацикливание и вызов is_provable_prime($n). Существуют также другие модули Perl, включая Math::Primality, хотя они намного медленнее.
echo 'forprime(i=2^64-44347170,2^64-1,print(i))' | time gp -f -q | md5sum
Требуется ~ 13 с, чтобы сгенерировать 1 миллион простых чисел. Как и в случае с модулем Perl, существует множество альтернативных способов, включая циклический вызов isprime, который представляет собой детерминированную процедуру (при условии, что используется недревняя версия Pari/GP).
#include <stdio.h>
#include <gmp.h>
int main(void) {
mpz_t n;
mpz_init_set_str(n,"18446744073665204445",10);
mpz_nextprime(n, n);
while (mpz_sizeinbase(n,2) < 65) {
/* If you don't trust mpz_nextprime, one could add this:
* if (!mpz_probab_prime_p(n, 100))
* { fprintf(stderr, "Bad nextprime!\n"); return -1; }
*/
gmp_printf("%Zd\n",n);
mpz_nextprime(n, n);
}
mpz_clear(n);
return 0;
}
Занимает около 30 секунд и получает те же результаты. Этот более сомнительный, так как я не доверяю его 25 предварительно случайным базовым тестам MR так же, как BPSW или одному из методов доказательства, но в данном случае это не имеет значения, поскольку мы видим, что результаты совпадают. Добавление дополнительных 100 тестов очень затратно по времени, но крайне маловероятно получение ложных результатов (я подозреваю, что у нас есть перекрывающиеся базы, так что это также расточительно).
from sympy import nextprime
n = 2**64-44347170;
n = nextprime(n)
while n < 2**64:
print n
n = nextprime(n)
Использование Python SymPy. К сожалению, Primerange использует сумасшедшую память при задании 2 ^ 64-1, поэтому ее невозможно использовать. Выполнение простого метода nextprime не идеально — он занимает около 5 минут, но дает те же результаты (текущий SymPy isprime использует 46 простых оснований, что намного больше, чем необходимо для детерминированных результатов до 2^64).
Есть и другие инструменты, например. ФЛИНТ, ГЭП и т.д.
Я понимаю, что поскольку вы работаете в Windows, мир шаткий и многие вещи работают неправильно. Я протестировал ntheory Perl в Windows, и с Cygwin и Strawberry Perl из командной строки я получил те же результаты. Код GMP должен работать так же, при условии, что GMP работает правильно.
Изменить добавление: если ваши результаты не соответствуют одному из методов сравнения, то один из двух (или оба) неверны. Это может быть неправильный код сравнения! Это помогает всем, если вы найдете и сообщите об ошибках. Маловероятно, но возможно, что они оба ошибаются одинаково, поэтому мне нравится сравнивать с как можно большим количеством других источников. Для меня это более надежно, чем выбор одного «золотого» кода для сравнения. Особенно, если вы используете странную платформу, которая, возможно, не была тщательно протестирована.
Для BPSW существует несколько реализаций:
- Пари. AES Lucas в исходном коде Pari, поэтому не уверен, насколько он переносим.
- Т. Р. Красиво. Сильный Лукас, автономный код.
- Дэвид Кливер. Стандартный, сильный или экстрасильный Лукас. Автономная библиотека, очень понятная, очень простая в использовании.
- Мой код без GMP, включая математику Монтгомери на ассемблере для x86_64. Конечно, немного быстрее, чем коды bigint.
- Мой код GMP. Стандартный, сильный, AES или сверхсильный Lucas. Быстрее, чем другие коды bigint. Также есть другие тесты Фробениуса и другие тесты на составность. Можно сделать автономным.
- У меня есть версия, использующая LibTomMath, которую я надеюсь использовать на одной из виртуальных машин Perl6. Только интересно, если вы хотите использовать LTM.
Все проверено по сравнению с данными Фейтсма. Я уверен, что есть и другие реализации. У FLINT есть вариант, который работает довольно быстро, но на самом деле это не BPSW (но он был проверен для чисел до 2^64).
person
DanaJ
schedule
24.11.2014
