Последовательность Петрова - вероятность распределения п. ч.

[Someone]

Dmitriy40 в сообщении #1530863 писал(а):

Почему такая огромная разница в скорости непонятно, у меня Core i5 3.5ГГц и Win7, ну не может же у Вас процессор работать медленнее 1ГГц (если только не ноут в режиме экономии энергии).

Ну, у Вас, видимо, нормальный "IBM-совместимый", а у меня моноблок с надкушенным яблоком, который младший сын почти три года назад подарил (списанный на той фирме, где сын тогда работал системным администратором; фирма вскорости совсем разорилась и задолжала своим работникам зарплату за несколько месяцев, так что он теперь в другом месте работает, и с большей зарплатой). Процессор Intel(R) Core(TM)2 Duo T7700 @ 2.40GHz 2.40 GHz. Сын поставил на него Windows 7, как он объяснил, после долгих плясок с бубном; работает она с самого начала кое-как, время от времени выскакивает "синий экран". Сначала скорость работы была нормальная, но постепенно система стала тормозить. Надо бы переустановить систему, но сын по естественной причине отказывается (к тому же, он живёт в другом городе, и специально приезжать для новых плясок с бубном с неясным результатом ему вряд ли интересно). Тем более, что нормальный компьютер у меня тоже есть (четырёхъядерный процессор Intel(R) Xeon(R) CPU E5450 @ 3.00Ghz), но он к интернету не подключён, поэтому я его редко включаю.

Однако существенной разницы я не обнаружил. Я на обоих компьютерах запустил программу с командной строкой

pfgw64.exe -f -q19999^^19999-19999-1

"Рабочий" компьютер выдал результат

PFGW Version 4.0.1.64BIT.20191203.Win_Dev [GWNUM 29.8]

19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (387.2026s+66.3499s)

а "старый" —

PFGW Version 4.0.1.64BIT.20191203.Win_Dev [GWNUM 29.8]

19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (303.9212s+52.6152s)

Легко убедиться, что время счёта практически обратно пропорционально тактовой частоте:

$$\frac{387{,}2026+66{,}3499}{303{,}9212+52{,}6152}:\frac 3{2{,}4}\approx 1{,}018.$$

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

Так что скорость работы программы на вашем компьютере меня заинтересовала. У Вас какая версия PFGW?

[Dmitriy40]

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

Так что скорость работы программы на вашем компьютере меня заинтересовала. У Вас какая версия PFGW?

Вчера скачанная с родного сайта по Вашей ссылке, та же что и у Вас:

Используется синтаксис Text

T:\PFGW>pfgw64.exe -i -Bspec,maxf=100000
PFGW Version 4.0.1.64BIT.20191203.Win_Dev [GWNUM 29.8]

CPU Information (From Woltman v26 library code)
Intel(R) Core(TM) i5-4690 CPU @ 3.50GHz
CPU speed: 3249.91 MHz, 4 cores
CPU features: RDTSC, CMOV, Prefetch, MMX, SSE, SSE2, SSE4.1, SSE4.2
L1 cache size: 32 KB
L2 cache size: 256 KB, L3 cache size: 6 MB
L1 cache line size: 64 bytes
L2 cache line size: 64 bytes
TLBS: 64

Benchmarking!  This may take several minutes.

Benchmarking generic modular reduction for f!-1!
[appx max f]   [num bits]   [iter time]  [PRP time]  [FFT used]
--------------------------------------------------------------------------------
       100          524       2805 ns     1470 us     generic reduction FMA3 FFT length 64
       400         2886       2140 ns     6178 us     generic reduction FMA3 FFT length 64
       700         5612       6897 ns       38 ms     generic reduction FMA3 FFT length 320
      1000         8529       9708 ns       82 ms     generic reduction FMA3 FFT length 512
      4000        42099         39 us     1660 ms     generic reduction FMA3 FFT length 1K
      7000        79320         96 us     7615 ms     generic reduction FMA3 FFT length 4K
     10000       118458        143 us       17 s      generic reduction FMA3 FFT length 8K, Pass1=128, Pass2=64, clm=2
     40000       553809        865 us      479 s      generic reduction FMA3 FFT length 12K, Pass1=256, Pass2=48, clm=1
     70000      1025675       1526 us       26 mi     generic reduction FMA3 FFT length 60K, Pass1=768, Pass2=80, clm=2
    100000      1516704       2508 us       63 mi     generic reduction FMA3 FFT length 100K, Pass1=320, Pass2=320, clm=4


Benchmarking special modular reduction for 3*2^n+1!
[appx max n]   [num bits]   [iter time]  [PRP time]  [FFT used]
--------------------------------------------------------------------------------
       100          101       1198 ns      121 us     generic reduction FMA3 FFT length 160K, Pass1=640, Pass2=256, clm=2
       400          401        618 ns      247 us     generic reduction FMA3 FFT length 160K, Pass1=640, Pass2=256, clm=2
       700          701         61 ns       43 us     generic reduction FMA3 FFT length 32
      1000         1001           ---         ---     all-complex FMA3 FFT length 32
      4000         4001        452 ns     1809 us     all-complex FMA3 FFT length 32
      7000         7001       1044 ns     7309 us     all-complex FMA3 FFT length 64
     10000        10001       1245 ns       12 ms     all-complex FMA3 FFT length 192
     40000        40001       5330 ns      213 ms     all-complex FMA3 FFT length 384
     70000        70001         11 us      777 ms     all-complex FMA3 FFT length 512
    100000       100001         15 us     1523 ms     all-complex FMA3 FFT length 2K
    400000       400001         78 us       31 s      all-complex FMA3 FFT length 4K
    700000       700001        153 us      107 s      all-complex FMA3 FFT length 5K
   1000000      1000001        222 us      222 s      all-complex FMA3 FFT length 20K, Pass1=256, Pass2=80, clm=2
   4000000      4000001       1162 us       77 mi     all-complex FMA3 FFT length 36K, Pass1=768, Pass2=48, clm=2
   7000000      7000001       1823 us        3 hr     all-complex FMA3 FFT length 50K, Pass1=640, Pass2=80, clm=4
  10000000     10000001       2856 us        7 hr     all-complex FMA3 FFT length 240K, Pass1=1280, Pass2=192, clm=2

Про 3.25ГГц чуть врёт, реально она 3.5ГГц (контролировал монитором). Бенчмарк занял 4 минуты (с maxf=100000), памяти хапнул менее 60М, выполнялся в один поток (не знаю что он Вам полезного покажет, но вдруг).

[Dmitriy40]

Единственное что приходит в голову - AVX, у меня есть, у Вас в обоих нету. Возможно FMA3 в колонке [FFT used] указывает на оптимизацию именно под AVX с командой FMA, хотя в списке CPU features оно не указано, и тогда разница скорости объяснима. Если FFT это Фурье, то вполне может быть, там умножений полно.

[Someone]

Dmitriy40 в сообщении #1530895 писал(а):

не знаю что он Вам полезного покажет, но вдруг

Показал: у Вас есть SSE4.1 и SSE4.2, а у меня нет. Этим, скорее всего, и объясняется разница в скорости счёта.

Dmitriy40 в сообщении #1530922 писал(а):

Единственное что приходит в голову - AVX, у меня есть, у Вас в обоих нету. Возможно FMA3 в колонке [FFT used] указывает на оптимизацию именно под AVX с командой FMA, хотя в списке CPU features оно не указано, и тогда разница скорости объяснима.

И это тоже.

Кстати, у меня тест завершается с сообщением

Error opening file helper.txt

которого, естественно, нет. По идее, он должен содержать вспомогательные потенциальные простые делители проверяемого числа, которые программа, может быть, сама найти не сможет (там не обязаны содержаться реальные делители, но программа проверит, являются ли они делителями). Но они могут понадобиться только при доказательстве простоты. И имя этому файлу можно задать любое, только в командной строке его нужно указать (в ключе -h).

…

О! Создал этот файл, в который записал единственное число $2$. Получил в конце теста сообщение

2 is trivially prime!: 2

Похоже, предлагается проверить какое-нибудь число (возможно, не одно) на простоту. Надо попробовать. В документации я этого не увидел.

…

Запустил с числом

12283*370590000^7002+1

в файле helper.txt.

…

Протестировал:

12283*370590000^7002+1 is 3PRP! (136.6733s+0,0052s)

на "старом" компьютере и

12283*370590000^7002+1 is 3-PRP! (176.9845s+0.0259s)

на "рабочем".