mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-05-31, 17:56   #144
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×53×61 Posts
Default

Quote:
Originally Posted by Batalov View Post
Incidentally, an interesting entry was added to PRPtop last month.
PIPrime(613373) (613373 digits, ...obviously) -- Adrian Bondrescu 05/2016
Nice. I wonder what kind of sieving he was doing.
rogue is offline   Reply With Quote
Old 2016-06-01, 02:53   #145
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

265016 Posts
Default

Oooo! It pleases me to see Romanian names there! It means some people still do serious things in that country... (assuming he is not already in a western place, like a university or famous company already).

Congratulations mate!
LaurV is offline   Reply With Quote
Old 2016-06-01, 18:31   #146
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Default

Quote:
Originally Posted by Batalov View Post
Incidentally, an interesting entry was added to PRPtop last month.
PIPrime(613373) (613373 digits, ...obviously) -- Adrian Bondrescu 05/2016
On my 4770k, I ran my gwnum-based program against it, to remove some of the doubt about it being a Carmichael, as only Fermat-PRP tests had been run on it. Since a=1 is minimal such that kronecker(a^2-4,n)==-1, I ran the following, which tests (x+2)^(n+1) == 5+1*2 (mod n, x^2-1*x+1):

Code:
time ~/coding/gwnum/s2 Pi_613373 1
Likely prime!

real	600m23.209s
user	392m46.660s
sys	0m4.616s

Last fiddled with by paulunderwood on 2016-06-01 at 18:33
paulunderwood is offline   Reply With Quote
Old 2016-06-01, 19:03   #147
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

145028 Posts
Default

After making some changes to the assembler code to not return data, I have been able to get pixsieve to work on Windows and OS X. You can download the source and Windows executable from here.

The -lmin option now works correctly and restarting from a pre-existing file should work as well, although it requires the -i option for the index file. I'll eventually eliminate that and let it use the pfgw file as the only input.

A few caveats. First, it fails on OS X with -O2, but will run correctly with -O1. I have an idea why, but I haven't investigated yet. Since the vast majority of time is spent in the asm code, there won't be much of a gain between -O1 and -O2. Second, multi-threading does not work on OS X. I suspect this is a problem in the use of semaphores. OS X has deprecated POSIX semaphores and uses what it calls a "dispatch semaphore". It is possible that I did not code that correctly. Third, it still fails to eliminate some composite numbers in the sieve. I don't know how many, but if it fails to eliminate them, then it might also be eliminating prime numbers. Nevertheless even with the caveats it is better than trying to factorize with pfgw and I know that it should eliminate 97% to 98% of the terms for many inputs fairly quickly.

I intend to eventually replace the sieving and threading code, but I don't know when I'm going to do that because that will be a lot more work.

Last fiddled with by rogue on 2016-06-01 at 19:04
rogue is offline   Reply With Quote
Old 2016-06-02, 17:01   #148
J F
 
J F's Avatar
 
Sep 2013

23×7 Posts
Default

Indeed it does not eliminate all composite factor candidates, I still
get lines like
p=13509635, 1.351M p/sec, 187 terms left, 13.5% done
p=35525635, 2.200M p/sec, 178 terms left, 35.5% done

Missing prime FCs: there is probably something going on with how work
is split up multithreaded.
I did some dozen runs with -sPi1M.txt -S110 -l15K -L20K -P1e8
-t1 always returns 135 terms remaining, missing a composite divisible by 14177
-t2, -t3, -t4 return either 134 or 135, sort of random
-t7 returns something between 134 and 193
-t15 always 135
'Always' means, in at least 6 test with this thread number I didn't see anything else.

But, unless it doesnt sort PRPs into the factored file, I dont mind much if
there is a composite slipping through occasionally - still way faster
than PFGW-TF!
Thanks a lot!
J F is offline   Reply With Quote
Old 2016-06-02, 17:33   #149
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,979 Posts
Default

How hard would it be to design a sieve that would sieve any ABC/ABC2 file?
henryzz is online now   Reply With Quote
Old 2016-06-02, 19:03   #150
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×53×61 Posts
Default

Quote:
Originally Posted by J F View Post
Indeed it does not eliminate all composite factor candidates, I still
get lines like
p=13509635, 1.351M p/sec, 187 terms left, 13.5% done
p=35525635, 2.200M p/sec, 178 terms left, 35.5% done

Missing prime FCs: there is probably something going on with how work
is split up multithreaded.
I did some dozen runs with -sPi1M.txt -S110 -l15K -L20K -P1e8
-t1 always returns 135 terms remaining, missing a composite divisible by 14177
-t2, -t3, -t4 return either 134 or 135, sort of random
-t7 returns something between 134 and 193
-t15 always 135
'Always' means, in at least 6 test with this thread number I didn't see anything else.

But, unless it doesnt sort PRPs into the factored file, I dont mind much if
there is a composite slipping through occasionally - still way faster
than PFGW-TF!
Thanks a lot!
I know that multi-threaded doesn't work and I know why. That will be fixed in 2.0. 2.0 will be built upon primesieve instead of the sieve originally written by Geoff Reynolds so it will eliminate the composite numbers being tested. It will also provide a factor removal rate.

Last fiddled with by rogue on 2016-06-02 at 19:05
rogue is offline   Reply With Quote
Old 2016-06-02, 19:04   #151
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·53·61 Posts
Default

Quote:
Originally Posted by henryzz View Post
How hard would it be to design a sieve that would sieve any ABC/ABC2 file?
A generic file? Fairly hard if you want any optimizations.
rogue is offline   Reply With Quote
Old 2016-06-02, 20:24   #152
J F
 
J F's Avatar
 
Sep 2013

23×7 Posts
Default

Factor removal rate? *perk up* Sounds interesting - with known PRP-test
runtimes I can probably use that to determine a better TF depth.
J F is offline   Reply With Quote
Old 2016-06-02, 20:30   #153
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

11001010000102 Posts
Default

I have posted 2.0 here. 1.2 is still available, for now. There are a number of differences from 1.2 as this framework for this version is completely different. For example you run with this pixsieve -P1e10 -l2000 -L3000 -C20000 -oterms.out -spi.txt -t4 -S15. -i is now used only for input when continuing a sieve, although I know that isn't working yet. Without -i, it will start a new sieve. -o is the output file that you use with pfgw. -C is new. Use that to tell the program how many chunks of primes each thread will get. The default is 5000, but you will want to play around with it to get optimal performance. The -r option is gone. The reporting time is 30 seconds. -F will output the factors to pixsieve.log The output file (right now) is only written upon ^C or reaching the end of the sieve.

Here is an example with the input and output:

Code:
/pixsieve -P1e8 -l20000 -L30000 -C20000 -oterms.out -spi.txt -t4 -S15
pixsieve v2.0, a CPU program to find factors of substrings of decimal string
Sieve started: (cmdline) 0 <= p < 100000000 with 2770 terms
1028569 | 15926535897932384626 . . . 24874754031617969941 (23005 digits)
2170583 | 15926535897932384626 . . . 79470269232297186832 (20386 digits)
. . . more factors . . .
56660377 | 15926535897932384626 . . . 66461900010350049018 (29467 digits)
  p=53533511, 100.9K p/sec, 2438 factors found at 0 secs/factor, 3.65 CPU cores, 53.5% done. ETA 02 Jun 15:18
64140539 | 15926535897932384626 . . . 89106524570802447493 (26469 digits)
. . .  more factors . . .
85822097 | 15926535897932384626 . . . 07248172987637569816 (20618 digits)
90358069 | 15926535897932384626 . . . 20599850235828918336 (28575 digits)

Sieve complete: 0 <= p < 100000000  6001455 primes tested
Clock time: 57.64 seconds at 104119 p/sec.  Factors found: 2445
Processor time: 210.24 sec. (0.10 init + 210.14 sieve).
CPU utilization: 3.65 (cores)
325 terms written to terms.out
So you can see the CPU utilization and modify the -C parameter to get better utilization. So with 4 threads, I got about 91% utilization of each core. The rate "p/sec" is "primes tested per second". It is not pmax - pmin, which most sieves do (and which makes little sense to me).

BTW, I fixed the issue with optimization not working on OS X. All I can say is that I find x86 assembly confusing and annoying to work with. Not being an expert means that I don't fully understand what some instructions will do.
rogue is offline   Reply With Quote
Old 2016-06-02, 21:09   #154
J F
 
J F's Avatar
 
Sep 2013

708 Posts
Default

Cool toy!

Note: v2.0 complained 3 DLLs missing (libgcc_s_seh-1, libstdc++-6
and libwinpthread-1 - someting MinGW-ish?). I could use the ones
from my SMPlayer (portable, so no DLLs registered system-wide)
Don't know how common these are on a non-programmers machine,
static link might be better for others who want to use this too.
J F is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 10:23.


Wed Dec 1 10:23:59 UTC 2021 up 131 days, 4:52, 1 user, load averages: 1.37, 1.23, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.