Биоматематические числа

[lel0lel]

(Оффтоп)

Aritaborian, пристрастие к встроенным функциям это не самое лучшее, что можно посоветовать. Для выкладывания кода на форуме или в OEIS его, конечно, разумнее по-возможности сделать компактным. А вот для желающих попробовать свои силы в написании чего-нибудь своего - нужно избегать использования всего более сложного чем цикл Do. Встроенные возможности со временем будут изучены. Кроме того, они как правило не делают программу быстрее. Я это написал, поскольку сам сейчас пишу кое-что в Wolfram, и от большого количества на первый взгляд удобного кода приходится отказываться ради эффективности.

[Aritaborian]

lel0lel, ну и ахинею вы несёте. Такой подход к использованию Wolfram Language глубоко ущербен.

[Someone]

Aritaborian в сообщении #1329019 писал(а):

Уважаемый Someone, действия, производимые вами над Wolfram Mathematica, справедливо описать лишь одним словом: изнасилование. Код, который вы пишете, ужасен настолько, насколько это вообще возможно. Это просто образец забивания гвоздей микроскопом.

Совершенно с Вами согласен. Но, к великому моему сожалению, я Wolfram Language никогда не изучал и пользуюсь привычками, приобретёнными в программировании на языках процедурного типа. А некоторые образцы вашего кода я даже и не понимаю, поскольку используемый в них синтаксис для меня сильно необычен. Уж простите старого невежду.

Конечно, я попробовал ваш код, заменив $4000$ на $5000$ и добавив команду Timing[…], и обнаружил, что ваш код выполняется $2784{,}321448\text{ с}$, а мой — $2956{,}000549\text{ с}$, то есть, почти на $3$ минуты дольше. Кроме того, в свой код я добавил ещё некоторые команды контроля времени и выяснил, сколько времени обрабатываются различные интервалы. Как добавить соответствующие команды в ваш код, не разбивая область изменения переменной на части, я уж и не знаю.

\begin{tabular}{|r|r||r|r|} \hline Интервал & Время (с) & Интервал & Время (с) \\ \hline $1-1000$ & $10{,}2920145$ & $1-1000$ & $10{,}2920145$ \\ \hline $1001-2000$ & $93{,}3902942$ & $1-2000$ & $103{,}6823087$ \\ \hline $2001-3000$ & $255{,}7169017$ & $1-3000$ & $359{,}3992104$ \\ \hline $3001-4000$ & $802{,}3210886$ & $1-4000$ & $1161{,}7202990$ \\ \hline $4001-5000$ & $1803{,}8541923$ & $1-5000$ & $2965{,}5744913$ \\ \hline \end{tabular}

[Dmitriy40]

Добавлю, в результате попыток оптимизировать PARI/GP код я обнаружил что для $n>1500$ больше всего времени тратится на проверку простоты, т.к. оптимизация прочих операций даёт заметный эффект (до двух раз для $n<300$) лишь для $n<1500$. Думаю этот вывод верен и для Вольфрама. Так что и тут известная банальность: не всё и не всегда надо оптимизировать.

[mihaild]

Это такое железо или mathematica сразу использует тяжелую проверку на простоту без запуска Миллера-Рабина?

$$\begin{tabular}{|c|c|} \hline 1-1000 & 2.50 \\ \hline 1001-2000 & 34.08 \\ \hline 2001-3000 & 90.74 \\ \hline 3001-4000 & 323.85 \\ \hline 4001-5000 & 779.90 \\ \hline \end{tabular}$$

[Someone]

mihaild в сообщении #1329058 писал(а):

Это такое железо

Вложение:

Processors.gif [ 4.44 Кб | Просмотров: 1217 ]

mihaild в сообщении #1329058 писал(а):

или mathematica сразу использует тяжелую проверку на простоту без запуска Миллера-Рабина?

Не знаю (вроде бы, описание алгоритма функции PrimeQ где-то мне встречалось, но сейчас не нашёл), но не думаю, что так. Естественная последовательность: проверить малые делители, вычислить хотя бы $3^{p-1}\pmod{p}$, а потом уже думать, что дальше делать.

[Dmitriy40]

Это можно проверить экспериментально: сравнить время определения простоты двух близких больших чисел, одно из которых простое, второе не простое и с минимальным делителем больше миллиарда. Мне например понравились простое $2^{44497}-1$ и близкое к нему не простое равное произведению степеней двух простых $(10^{1000}+453)^{13}(10^{100}+267)^4$ (PARI/GP):

? x=2^44497-1;y=(10^1000+453)^13*(10^100+267)^4;gettime();ispseudoprime(x);x=gettime();ispseudoprime(y);y=gettime();printf("%0.1fs vs %0.1fs",x/1000,y/1000)
16.7s vs 10.9s

[Someone]

Wolfram Mathematica:
$2^{44497}-1$: $104{,}739071\text{ с}$.
$(10^{1000}+453)^{13}(10^{100}+267)^4$: $31{,}028599\text{ с}$.
Доказать простоту первого числа Wolfram Mathematica за разумное время не сможет (не знаю, можно ли ей указать, каким методом следует пользоваться; в этом случае результат мог бы измениться).

Однако специализированная программа pfgw64.exe делает это без труда.
Командная строка:

..\pfgw64.exe  -tp -lLog.txt -q2^^44497-1
..\pfgw64.exe  -tp -lLog.txt -q(10^^1000+453)^^13*(10^^100+267)^^4

Двойные знаки возведения в степень связаны с особенностями операционной системы.
Содержимое файла Log.txt:

Primality testing 2^44497-1 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 3, base 1+sqrt(3)
Calling Brillhart-Lehmer-Selfridge with factored part 100.00%
2^44497-1 is prime! (4.0359s+0.0030s)
Primality testing (10^1000+453)^13*(10^100+267)^4 [N+1, Brillhart-Lehmer-Selfridge]
Running N+1 test using discriminant 2, base 2+sqrt(2)
(10^1000+453)^13*(10^100+267)^4 is composite (34.2262s+0.0028s)

[Aritaborian]

(Оффтоп)

Someone в сообщении #1329048 писал(а):

Уж простите старого невежду.

Конкретно этого старого невежду я простил бы и за большее. Сам должен просить прощения за некоторое нахальство.