mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > And now for something completely different

Reply
 
Thread Tools
Old 2022-06-20, 19:22   #166
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·19·113 Posts
Default

Quote:
Originally Posted by Luminescence View Post
Code:
fft size: 16384
avx: 8
round off 3: 0.000000
round off 2: 0.000000
prp

real	0m9,978s
Nice.

So in short: the latest code works, but the FFT size needs to be increased.
I have just put out (post 148) code that does autoincrement of FFT size on excessive round-off error. Attached is the concept test program.
Attached Files
File Type: c frmky2.c (3.3 KB, 27 views)
paulunderwood is offline   Reply With Quote
Old 2022-06-20, 20:19   #167
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2×11×113 Posts
Default

Code:
*** Maximum error of 0.500000 excessive at iteration 108154. Increasing FFT size.
prp

real    0m41.429s
Being a bit more conservative with a limit of 0.35 gives
Code:
*** Maximum error of 0.375000 excessive at iteration 108660. Increasing FFT size.
prp

real    0m41.536s
which switches a bit more than 500 iterations earlier.
frmky is offline   Reply With Quote
Old 2022-06-20, 23:45   #168
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·19·113 Posts
Default

Attached is a version that uses a quick gwswap() rather than a slow gwcopy(). I have added the corresponding Ver_5 code to post 148.
Attached Files
File Type: c frmky3.c (3.3 KB, 30 views)

Last fiddled with by paulunderwood on 2022-06-20 at 23:46
paulunderwood is offline   Reply With Quote
Old 2022-06-22, 19:19   #169
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10C616 Posts
Default

The ultimate Ver_6 has been uploaded to post 148. It uses functions and a neat piece of code to calculate odd d for n-1=d*2^r thanks to frmky. It might be a little bit quicker. As I state there, comment out the printf(); function messaging about FFT increases if you find them annoying at runtime.

frmky is working on 3-SPRP GMP code to be used above a certain threshold based this UTM page. This is useful for ARM based computers.

Last fiddled with by paulunderwood on 2022-06-22 at 19:27
paulunderwood is offline   Reply With Quote
Old 2022-06-22, 19:42   #170
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2·11·113 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
frmky is working on 3-SPRP GMP code to be used above a certain threshold based this UTM page. This is useful for ARM based computers.
Below is the code I settled on. I thank Paul for his suggestions and comments! I have tested it on many known primes and base-3 strong pseudoprimes.

This code is slower than Paul's version using gwnum but is faster than mpz_probab_prime_p(). It's useful where gwnum is not available.

Code:
int cm_nt_is_prime (mpz_t n)

{
   unsigned long j, r;
   int prime = 0;
   mpz_t d, a, x, n_sub_1;

   if (mpz_sizeinbase(n, 2) < 4096) return (mpz_probab_prime_p(n, 0) > 0);
   if (mpz_even_p(n)) return 0;

   mpz_inits(d, a, x, n_sub_1, NULL);

   mpz_sub_ui(n_sub_1, n, 1);
   r = mpz_scan1(n_sub_1, 0);
   mpz_fdiv_q_2exp(d, n_sub_1, r);

   mpz_set_ui(a, 3);
   mpz_powm(x, a, d, n);

   if ((mpz_cmp_ui(x, 1) == 0) || (mpz_cmp(x, n_sub_1) == 0)) prime = 1;
   else {
      for (j = 1; j < r; j++) {
         mpz_powm_ui(x, x, 2, n);
         if (mpz_cmp(x, n_sub_1) == 0) {
            prime = 1;
            break;
         }
      }
   }
    
   mpz_clears(d, a, x, n_sub_1, NULL);
   return prime;
}
frmky is offline   Reply With Quote
Old 2022-06-30, 07:58   #171
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

edit: running sudo ldconfig solved the issue...


Quote:
I compiled ecpp and when running ecpp I get:

Code:
ecpp: error while loading shared libraries: libcm.so.0: cannot open shared object file: No such file or directory
libcm.so.0 exists:

Code:
$ ls /usr/local/lib/libcm* -l
-rw-r--r-- 1 root root 892160 Jun 30 07:56 /usr/local/lib/libcm.a
-rwxr-xr-x 1 root root    967 Jun 30 07:56 /usr/local/lib/libcm.la
-rw-r--r-- 1 root root 980172 Jun 30 07:56 /usr/local/lib/libcm_mpi.a
-rwxr-xr-x 1 root root   1041 Jun 30 07:56 /usr/local/lib/libcm_mpi.la
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so -> libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0 -> libcm_mpi.so.0.0.0
-rwxr-xr-x 1 root root 553384 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so -> libcm.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so.0 -> libcm.so.0.0.0
-rwxr-xr-x 1 root root 502448 Jun 30 07:56 /usr/local/lib/libcm.so.0.0.0
The only problem I ran into during compiling/installing was that make install complained about a permission error, so I ran sudo make install which went fine. Is that the issue? Same thing happened when installing mpfrx, permissions error and I did sudo make install.

Last fiddled with by bur on 2022-06-30 at 08:12
bur is offline   Reply With Quote
Old 2022-06-30, 08:06   #172
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

24×719 Posts
Default

Quote:
Originally Posted by bur View Post
I compiled ecpp and when running ecpp I get:

Code:
ecpp: error while loading shared libraries: libcm.so.0: cannot open shared object file: No such file or directory
libcm.so.0 exists:

Code:
$ ls /usr/local/lib/libcm* -l
-rw-r--r-- 1 root root 892160 Jun 30 07:56 /usr/local/lib/libcm.a
-rwxr-xr-x 1 root root    967 Jun 30 07:56 /usr/local/lib/libcm.la
-rw-r--r-- 1 root root 980172 Jun 30 07:56 /usr/local/lib/libcm_mpi.a
-rwxr-xr-x 1 root root   1041 Jun 30 07:56 /usr/local/lib/libcm_mpi.la
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so -> libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0 -> libcm_mpi.so.0.0.0
-rwxr-xr-x 1 root root 553384 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so -> libcm.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so.0 -> libcm.so.0.0.0
-rwxr-xr-x 1 root root 502448 Jun 30 07:56 /usr/local/lib/libcm.so.0.0.0
The only problem I ran into during compiling/installing was that make install complained about a permission error, so I ran sudo make install which went fine. Is that the issue? Same thing happened when installing mpfrx, permissions error and I did sudo make install.
Do you have /usr/local/lib in your ${LD_LIBRARY_PATH}? I ran into the exact same problem, which was fixed by putting the line
Code:
export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
into my .bashrc
xilman is offline   Reply With Quote
Old 2022-06-30, 08:13   #173
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

601 Posts
Default

Thanks, I did ldconfig which fixed it.
bur is offline   Reply With Quote
Old 2022-06-30, 11:22   #174
bur
 
bur's Avatar
 
Aug 2020
79*6581e-4;3*2539e-3

25916 Posts
Default

A question regarding the progress with the -v switch, I noticed values like qroot, Cornacchia and trial div increase over time, are those the values to look out for? If so, up to which value will they increase?
bur is offline   Reply With Quote
Old 2022-06-30, 12:24   #175
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×19×113 Posts
Default

Quote:
Originally Posted by bur View Post
A question regarding the progress with the -v switch, I noticed values like qroot, Cornacchia and trial div increase over time, are those the values to look out for? If so, up to which value will they increase?
Those are accumulative times. Each step is quicker than the last. It runs at O(log(n)^4) meaning a number twice in length takes 16 times as long to compute. So as each of the two stages finish it will look like it is speeding up.

I suggest that you start with some small test cases like (10^1031-1)/9.
paulunderwood is offline   Reply With Quote
Old 2022-06-30, 17:35   #176
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

72·73 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Those are accumulative times. Each step is quicker than the last. It runs at O(log(n)^4) meaning a number twice in length takes 16 times as long to compute. So as each of the two stages finish it will look like it is speeding up.

I suggest that you start with some small test cases like (10^1031-1)/9.
For (10^1031-1)/9, N-1 can be easily >= 1/3 factored, and N-1 primality proving can be used, I think 10^1000+453 (which is the next prime after 10^1000) may be better.
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For which types of primes is GPU primality test software available? bur GPU Computing 6 2020-08-28 06:20
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
APR-CL as primality proof f1pokerspeed FactorDB 14 2014-01-09 21:06
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37

All times are UTC. The time now is 03:29.


Fri Oct 7 03:29:14 UTC 2022 up 50 days, 57 mins, 0 users, load averages: 1.13, 1.09, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”