mersenneforum.org (https://www.mersenneforum.org/index.php)
-   XYYXF Project (https://www.mersenneforum.org/forumdisplay.php?f=110)
-   -   Leyland Primes (x^y+y^x primes) (https://www.mersenneforum.org/showthread.php?t=19347)

 Batalov 2014-05-12 21:04

Leyland Primes (x^y+y^x primes)

Placeholder for x[SUP]y[/SUP]+y[SUP]x[/SUP] prime search reservations.

Contact [URL="http://www.mersenneforum.org/member.php?u=1540"]XYYXF[/URL] to [URL="http://www.primefan.ru/xyyxf/primes.html#0"]reserve a range[/URL]. Multisieve is one of the sieve programs capable of sieving this form.

 swellman 2014-05-13 13:09

Yafu can sieve this form too.

 bsquared 2014-05-13 13:45

It can? :ermm:

 LaurV 2014-05-13 14:12

:missingteeth::ick:

Sorry, I don't laugh at any of you. It is just about the situation, I expected all in the world but didn't expect Ben's reply to this, in this way! [edit: if some guest read this, maybe they don't know, Ben is yafu's author].

I can't stop laughing.

 swellman 2014-05-13 14:17

[QUOTE=bsquared;373350]It can? :ermm:[/QUOTE]

You mean it can't? I thought Yafu did everything. :smile:

I stand corrected - Yafu can factor this form via SNFS.

 bsquared 2014-05-13 14:46

[QUOTE=swellman;373354]You mean it can't? I thought Yafu did everything. :smile:

I stand corrected - Yafu can factor this form via SNFS.[/QUOTE]

Err, well, yes, of course it can do everything, except for LaurV's loops and ifs :smile:

Yep, you were probably thinking of SNFS factorization.

 Batalov 2014-05-13 17:54

Well, of course, sieving can be done with almost any program (including your own). But the question is how fast can it sieve. Multisieve is good.

[U]A worked example[/U]:
2. Start, select x^y+-y^x mode, select "+", set up some names for outputs, e.g. "xyyx200.out" and "xyyx200.log"; set up limits above previously searched: e.g. x from 200 to 200, y from 20001 to 30000
3. Sieve, after a while, stop (e.g. at 10-20s per candidate)
4. Run pfgw on the "xyyx200.out" file (with -f0 -l)
5. ...
6. PROFIT! [SPOILER]e.g. 200^20373+20373^200 is a (new) PRP[/SPOILER]

 XYYXF 2014-05-13 19:01

[QUOTE=Batalov;373363]e.g. x from 200 to 200, y from 20001 to 30000[/QUOTE]Conventionally x is always greater than y, and it's also recommended to test all y's for a given x :)

So it's better to take e.g. x from 12501 to 13000, y from 2001 to 12999 :-)

 Batalov 2014-05-13 19:08

Multisieve reversed that order (because x[SUP]y[/SUP] > y[SUP]x[/SUP], for 3<=x<y, and because it sieves for x[SUP]y[/SUP] +/- y[SUP]x[/SUP], so it would be convenient to have a positive number). It was an example of setting up Multisieve. Multisieve will require x<y.

Let's start the fun?
I will run the [20001-40000, 11-200] range. Found six new PRPs so far, while warming up.

 XYYXF 2014-05-13 19:19

OK, [url]http://xyyxf.at.tut.by/primes.html#ranges[/url] is updated. But I still hope someone will decrease the number of steps y>10, y>200, y>1000, y>2000 :-)

E.g. it's possible to take [15001-20000, 1001-2000].

 rogue 2014-05-13 22:28

I haven't touched MultiSieve in years. It's good to know that some people still have use for it. After looking at the code (talk about a blast from the past), I think it would be easy to convert this sieve to OpenCL since it doesn't use a discrete log. An OpenCL version might 100x faster.

 rogue 2014-05-13 23:53

[QUOTE=Batalov;373293]Placeholder for x[SUP]y[/SUP]+y[SUP]x[/SUP] prime search reservations.

Contact [URL="http://www.mersenneforum.org/member.php?u=1540"]XYYXF[/URL] to [URL="http://xyyxf.at.tut.by/primes.html#0"]reserve a range[/URL]. Multisieve is one of the sieve programs capable of sieving this form.[/QUOTE]

Now if Paul would like to take the time to update his [URL="http://www.leyland.vispa.com/numth/primes/xyyx.htm"]webpage[/URL]...

...or someone else could take ownership.

[COLOR="Blue"]EDIT (S.B.): That's exactly what Andrey did a few years ago: [url]http://xyyxf.at.tut.by/primes.html#0[/url][/COLOR]

 Batalov 2014-05-14 00:13

[20001-40000, 11-200] range is done. One PRP I had found two years ago, and now, the rest:
[CODE]11^36442+36442^11, 37951(decimal digits) (2012)
33^21262+21262^33, 32287
63^20018+20018^63, 36020
76^24787+24787^76, 46620
92^32907+32907^92, 64623
98^27819+27819^98, 55394
105^34684+34684^105, 70103
117^26870+26870^117, 55573
128^29007+29007^128, 61124
128^32001+32001^128, 67433
129^28468+28468^129, 60085
131^31870+31870^131, 67478
143^39070+39070^143, 84209
157^29934+29934^157, 65733
163^26530+26530^163, 58690
181^22300+22300^181, 50347
200^20373+20373^200, 46879
[/CODE]
Submitted to PRP top, they will show up in a few days.

 Batalov 2014-05-14 08:31

[QUOTE=XYYXF;373379]E.g. it's possible to take [15001-20000, 1001-2000].[/QUOTE]
Ok. Consider this range done, too. ;-)

 Mini-Geek 2014-05-14 12:16

FWIW, the result of sieving the range [12501-15000, 2001-15000] to 1657571 (which took a few hours on a core)

[url]https://www.dropbox.com/s/5plhnqg5hwqtbn8/xyyx.7z[/url]

As a rough estimate: 700,000 candidates (guess of how many will remain after sieving; currently 720,880 remaining) at 40 seconds (timings for PFGW tests ranged from 26 to 58 seconds) per candidate per core makes this range an 80 day job for a quad core Haswell. I don't want to make that much of a commitment right now, but someone can use my sieve file as a starting point. :smile:

 Batalov 2014-05-14 17:22

[QUOTE=XYYXF;373379]OK, [url]http://xyyxf.at.tut.by/primes.html#ranges[/url] is updated. But I still hope someone will decrease the number of steps y>10, y>200, y>1000, y>2000 :-)

E.g. it's possible to take [15001-20000, 1001-2000].[/QUOTE]
Done.
[CODE]1033^16254+16254^1033, 48992
1263^19898+19898^1263, 61712
1265^19732+19732^1265, 61211
1271^17368+17368^1271, 53913
1338^15377+15377^1338, 48076
1417^15754+15754^1417, 49647
1456^19909+19909^1456, 62976
1508^17691+17691^1508, 56230
1537^18832+18832^1537, 60012
1576^19021+19021^1576, 60821
1638^15437+15437^1638, 49620
1684^16495+16495^1684, 53219
1741^19546+19546^1741, 63345
1828^16589+16589^1828, 54113
1839^17156+17156^1839, 56008
1845^16636+16636^1845, 54334
1850^18879+18879^1850, 61681
1897^16710+16710^1897, 54777
1908^17605+17605^1908, 57755
1943^15222+15222^1943, 50058
[/CODE]

 Batalov 2014-05-15 15:49

And one PRP to rule them all:
15^328574+328574^15 (386434 digits) :smile:

 Batalov 2014-05-15 16:38

Reserving [40001-330000, 11-17]

 XYYXF 2014-05-15 19:54

Why not ...20]?

 Batalov 2014-05-15 20:36

Because it is [I]more[/I] work? ;-)
Maybe later.

(19 and 20 are particularly heavy and 20^330000 >> 17^330000)
Someone can relatively easily do the y=18. Free idea! Anyone?

 fivemack 2014-05-15 23:50

I am running Y=18, should make it to 300k by the end of the month unless I've screwed up my calculations somewhere.

 Batalov 2014-05-16 17:34

[40001-330000, 11-17] is done. Three PRPs:
11^255426+255426^11
12^47489+47489^12 (previously known)
15^328574+328574^15

 Batalov 2014-05-16 21:30

Reserving [330001-400000, 11-17]

 rogue 2014-05-16 22:40

[QUOTE=rogue;373401]I haven't touched MultiSieve in years. It's good to know that some people still have use for it. After looking at the code (talk about a blast from the past), I think it would be easy to convert this sieve to OpenCL since it doesn't use a discrete log. An OpenCL version might 100x faster.[/QUOTE]

So I started to work on this and discovered it will be a little more work than I expected. That's okay because I found an optimization that will help it be even faster.

My question to those who are searching, what % of candidates remain after searching a range? That might impact how I code certain parts of the program.

 Batalov 2014-05-16 22:54

For values one less than a prime, the candidate list shrinks dramatically immediately after starting. If the sieve is written similar to newpgen then at some point the list representation is changed to a more compact one. (Is it?) Anyway, if you take X=12, Y from 40001 to 400000, then after a few seconds of running the number of candidates shrinks from 360000 to ~2,200, then under 2000 and then goes at a not such dramatic rate.
(You would definitely want to pack this list to only multiples of the prime X+1, and probably even tighter based on some additional modular restrictions.)

For values not one less than a prime, the candidate list is 3-4 times larger.

 rogue 2014-05-17 17:34

[QUOTE=Batalov;373674]For values one less than a prime, the candidate list shrinks dramatically immediately after starting. If the sieve is written similar to newpgen then at some point the list representation is changed to a more compact one. (Is it?) Anyway, if you take X=12, Y from 40001 to 400000, then after a few seconds of running the number of candidates shrinks from 360000 to ~2,200, then under 2000 and then goes at a not such dramatic rate.
(You would definitely want to pack this list to only multiples of the prime X+1, and probably even tighter based on some additional modular restrictions.)

For values not one less than a prime, the candidate list is 3-4 times larger.[/QUOTE]

When both x and y are even, it is obvious that x^y+y^x is even, so you are really starting with 180,000 candidates.

That creates some challenges. In the current code it starts as a bitmap, but is then changed to a vector when it determines that a vector would take less memory. With OpenCL I cannot use a vector, although I can use an array.

In the new version I'm thinking about eliminating the bitmap and vector completely and forcing the user to bite off only as much as they have memory available (i.e. storing in an array). I can't imagine someone reserving a range with a billion candidates for example. The largest reservation in the past didn't even have that many candidates in it.

Of note, I think that [URL="http://xyyxf.at.tut.by/primes.html#ranges"]this page[/URL] should be split so that reservations are on one page and primes/PRPs on another. The reservations should list the ymin and ymax for each reservation. The primes/PRPs should have a "when found" in addition to "when proven", but that is just an opinion.

I also have the opinion that x and y should be swapped in those tables for clarification. The reason is because of how MultiSieve (and the pending xyyxsieve) work. In these programs x is always less than y, but on this webpage, it has y always less than x. I also see that the page was updated last week, but it doesn't have any reservations that have been added to this thread.

 Batalov 2014-05-17 18:44

[QUOTE=Batalov;373674]For values one less than a prime, the candidate list shrinks dramatically immediately after starting.[/QUOTE]
[B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

[B]Proof.[/B] x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x [TEX]\eq[/TEX] 1 (mod p) (little Fermat Thm.) and x^y [TEX]\eq[/TEX] p-1 (mod p), so x^y+y^x has a factor p. [TEX]\qed[/TEX]

Because of that, for x=12, the sieve should only consider 1/26th of the initial values, for x=18, 1/36th; for x=1600, 1/3202th, etc

 Batalov 2014-05-17 19:02

Done with [330001-400000, 11-17], no primes.

Reserving [400001-500000, 11-17] - one less step in the stepwise function, as you asked, Andrey!

 rogue 2014-05-17 21:23

[QUOTE=Batalov;373704][B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

[B]Proof.[/B] x is even, so x^y+y^x is composite (even) for even y. For odd y>1 coprime with p, y^x [TEX]\eq[/TEX] 1 (mod p) (little Fermat Thm.) and x^y [TEX]\eq[/TEX] p-1 (mod p), so x^y+y^x has a factor p. [TEX]\qed[/TEX]

Because of that, for x=12, the sieve should only consider 1/26th of the initial values, for x=18, 1/36th; for x=1600, 1/3202th, etc[/QUOTE]

Hadn't thought of that. It would certainly reduce the initial memory size considerably for certain x or y

 XYYXF 2014-05-17 22:57

[QUOTE=rogue;373702]I also have the opinion that x and y should be swapped in those tables for clarification.[/QUOTE]They won't be, because Paul Leyland originally stated x > y. He also insisted that PRPs should be searched in order or increasing x.

Why not to rename x and y variables in Multisieve? :-)

 rogue 2014-05-18 02:42

[QUOTE=XYYXF;373728]They won't be, because Paul Leyland originally stated x > y. He also insisted that PRPs should be searched in order or increasing x.

Why not to rename x and y variables in Multisieve? :-)[/QUOTE]

I have two reasons. First, I haven't touched Multisieve in years and am not interested in updating it. Second, Multisieve also supports x^y-y^x and for that to be > 0, x must be less than y.

 Batalov 2014-05-18 03:07

It is a classic case of little- vs. big-endians war.
But it's not new! Swift already described it:
[QUOTE=Wiki]The novel further describes an intra-Lilliputian quarrel over the practice of breaking eggs. Traditionally, Lilliputians broke boiled eggs on the larger end; a few generations ago, an Emperor of Lilliput, the Present Emperor's great-grandfather, had decreed that all eggs be broken on the smaller end after he cut himself breaking the egg on the larger end. The differences between Big-Endians (those who broke their eggs at the larger end) and Little-Endians had given rise to "six rebellions... wherein one Emperor lost his life, and another his crown". The Lilliputian religion says an egg should be broken on the convenient end, which is now interpreted by the Lilliputians as the smaller end. The Big-Endians gained favour in Blefuscu.[/QUOTE]
Let's not loose sleep over it. C'est tout de même.

 Batalov 2014-05-19 06:25

[400001-500000, 11-17] is done, no primes. (ME~=0.2)

 XYYXF 2014-06-03 09:12

[QUOTE=rogue;373744]Multisieve also supports x^y-y^x and for that to be > 0, x must be less than y.[/QUOTE]I've always used version 5.5 which requires x > y :)

[url]http://www.primefan.ru/stuff/soft/ms.zip[/url]

 rogue 2014-06-03 11:53

[QUOTE=XYYXF;374917]I've always used version 5.5 which requires x > y :)

[url]http://www.primefan.ru/stuff/soft/ms.zip[/url][/QUOTE]

That was before I was asked to modify MultiSieve to support x^y - y^x.

 rogue 2014-06-12 17:31

With both MultiSieve and its replacement for x^y+/-y^x, the more squarelike the search area, the more efficient the software will be. The new software will be even more efficient based upon squareness of the search area. By "squareness" I mean xmax - xmin is close to ymax - ymin. This is because the software has to calculate both x^y mod p and y^x mod p. The software gets its efficiency by computing x^miny mod p for each x and y^minx mod p for each y then multiplying to get the next term. The software won't prohibit a flat rectangle, i.e. minx = maxx or miny = maxy, but it won't be very fast.

 rogue 2014-06-13 12:04

Nevermind my previous post.

I was looking at what I was working on and realized that it couldn't easily be done in a GPU because of the memory requirements. As I turned the problem over in my head (more than a few times) I realized that my approach to the sieve was inefficient. Although more efficient than MultiSieve, there was an obvious optimization that I completely missed.

The good thing is that this optimization also simplifies the code (code I haven't written yet) quite a bit.

 rogue 2014-06-13 19:09

And due to that simplification the code is now written. Now I have the fun of testing it...

 Batalov 2014-06-13 19:29

As you can see from my interest for these (which is predating the creation of this forum) that I have a soft spot for these PRPs (as, undoubtedly, also does Selevich). The real burden of course is the PRP testing, but an improved sieve could lift maybe 1/3 of that weight - then, that's great!

 rogue 2014-06-15 13:36

[QUOTE=rogue;375713]Nevermind my previous post.

I was looking at what I was working on and realized that it couldn't easily be done in a GPU because of the memory requirements. As I turned the problem over in my head (more than a few times) I realized that my approach to the sieve was inefficient. Although more efficient than MultiSieve, there was an obvious optimization that I completely missed.

The good thing is that this optimization also simplifies the code (code I haven't written yet) quite a bit.[/QUOTE]

That optimization was a fail (and I know why). So I'm focused on getting the code at least equivalent to MultiSieve and then focus on optimizations later. That being said it shouldn't be too difficult to make that happen.

 rogue 2014-06-30 12:42

Almost ready for release. I have to do some more testing. On my laptop (which has a slow GPU), it is only about 2x as fast as MultiSieve. I would expect a desktop with a bigger GPU to be much faster.

 rogue 2014-07-07 14:00

1 Attachment(s)
Here is a 64-bit beta (Windows). I have good news and bad news about this beta. First the bad. It appears that MultiSieve removes terms for which it does not have a factor. I've looked at the code and have not been able to figure out where that is occurring. This means that ranges sieved in the past should be sieved again presuming I can't track down why it is doing it, which I have little desire to do.

Now the good. The attached program is about 4x faster than MultiSieve on my laptop (for the range below), which has an NVIDIA NVS 5200M. The performance is somewhat based upon the range of y. The larger the range of y, the better the performance.

Here are the runtime options:

[code]
E:\stuff\sieves\xyyxsieve_1.0.0\visualstudio>xyyxsievecl64 -h
-h --help Print this help
-v --verbose Verbose output (memory usage)
-q --quiet Quiet output (no banner or stats)
-p --pmin=P0 Sieve start: 3 <= P0 <= p (default P0=3)
-P --pmax=P1 Sieve end: p < P1 <= 2^62 (default P1=P0+10^9)
-l --list List available platforms and devices
-b --blocks=B Force B blocks per device
-f --platform=F Use platform F instead of 0
-d --device=D Use device D instead of 0
-x --min_x=x Minimum x to search
-X --max_x=X Maximum x to search
-y --min_y=y Minimum y to search
-Y --max_y=Y Maximum y to search
-s --step=s steps iterated per call to GPU
-f --factorsinrate=f Number of factors to use when computing removal rate (default 50)
-m --minimum X Do not report factors smaller than X (default 100000)
-i --inputfile=i PFGW file in ABC format
-o --outputfile=o PFGW file of remaining candidates in ABC format
-S --sign=+/-/b sign to sieve for
[/code]

Here is an command line example: xyyxsievecl64 -x100 -X200 -y3000 -Y4000 -P2e6 -t2 -s3000 -S+ -b32 -oxyyx.pfgw

You will want to vary options t, s, and b to maximize the performance of your machine.

I'll provide source later as this can be built for Linux and OS X.

 wombatman 2014-07-07 14:41

Runs great on a GTX570, but I did encounter an error as documented below:
[CODE]\$ xyyxsievecl64.exe -x100 -X200 -y3000 -Y10000 -P2e6 -t2 -s3000 -S+ -oxyyx.pfgw

xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x
Sieve started: (cmdline) 0 <= p < 2000000 with 287349 terms
OpenCL Error: Out of resources
argument: counter[/CODE]

My GPU has ~1.2GB of RAM and usually about 1GB actually available.

 Batalov 2014-07-07 15:05

Option -f (platform and factorsinrate) is used twice, and doesn't seem to come through (as --platform=1)
[CODE]\$ ./xyyxsievecl64.exe --platform=1 -d0 -x100 -X200 -y3000 -Y4000 -P2e6 -t2 -s3000 -S+ -b32 -oxyyx.pfgw
xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x
List of available platforms and devices
Platform 0 has no available devices.
Here is a list of platforms and devices:
Platform 0 is a Advanced Micro Devices, Inc. AMD Accelerated Parallel Processing, version OpenCL 1.2 AMD-APP (938.2)
No devices
Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.1 CUDA 6.0.1
Device 0 is a NVIDIA Corporation GeForce GTX 570
[/CODE]

 rogue 2014-07-07 15:17

[QUOTE=wombatman;377574]Runs great on a GTX570, but I did encounter an error as documented below:
[CODE]\$ xyyxsievecl64.exe -x100 -X200 -y3000 -Y10000 -P2e6 -t2 -s3000 -S+ -oxyyx.pfgw

xyyxsievecl v1.0.0, a GPU program to find factors numbers of the form x^y+y^x
Sieve started: (cmdline) 0 <= p < 2000000 with 287349 terms
OpenCL Error: Out of resources
argument: counter[/CODE]

My GPU has ~1.2GB of RAM and usually about 1GB actually available.[/QUOTE]

I have seen that as well. I haven't figured it out yet. The program doesn't use that much global GPU memory so I suspect it is a problem with local GPU memory. I have a table of powers for each kernel. I'll reduce the size of that table as it has too many zeros in it. Hopefully that will help. One other issue is that the number of factors returned might be causing problems. It could be overflowing in the GPU. I'm not certain how to avoid that without losing useful information.

As for two "-f" options, I modified factorsinrate to use -F.

If anyone can provide some speed comparisons with MultiSieve that would be nice.

I'm also working on a change to pfgw so that the factors output from sieving programs can be easily verified. I though I had done something like that already, but maybe I never released that code.

 rogue 2014-07-07 17:38

The "Out of resources" seems to have been caused by having too many small factors. I'll do two things to address that. First, I'll increase the buffer size so that more factors can be collected. (I've also added a check so the program can tell you if you missed factors due to too many being found.) Second, I've added a "small primes" check to eliminate all terms that are factored by p < 100 before I start the GPU sieve. That can eliminate 75% of the terms up front.

 wombatman 2014-07-07 18:36

Excellent!

 rogue 2014-07-07 19:55

1 Attachment(s)
[QUOTE=wombatman;377594]Excellent![/QUOTE]

By "Excellent!", do you mean this:

 rogue 2014-07-07 19:56

1 Attachment(s)
[QUOTE=wombatman;377594]Excellent![/QUOTE]

or this?

 wombatman 2014-07-07 20:12

Why not both? :tu:

 rogue 2014-07-07 20:47

1 Attachment(s)
Attached is the latest code. Here is what the output looks like now. This is a rather extreme range to do. It still fails if the range gets larger. I know why, but fixing is a bigger challenge. It is probably better to take smaller ranges and paste together one file and restart from there, although I haven't test the ability to restart the sieve from the output file.

[code]
xyyxsievecl64.exe -x2 -X2500 -y3 -Y7500 -P1e6 -t2 -s2000 -S+ -oxyyx.pfgw
xyyxsievecl v1.0.1, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
7807501 because the term is even
1478788 because x and y have a common divisor
4472597 because the term is divisible by a prime < 100
Sieve started: (cmdline) 0 <= p < 1000000 with 1857365 terms
Thread 2 has completed 1818380 of 1862363 iterations
CTRL-C accepted. Please wait for threads to completed.s/factor, 0.15 CPU cores, 25.6% done. ETA 07 Jul 15:53

Thread 2 has completed 383059 of 390048 iterations
Sieve interrupted: 3 <= p < 1000000 26624 primes tested
Clock time: 539.27 seconds at at 49 p/sec. Factors found: 1472315
Processor time: 92.09 sec. (8.53 init + 83.55 sieve).
Seconds spent in CPU and GPU: 65.70 (cpu), 1044.80 (gpu)
Percent of time spent in CPU vs. GPU: 5.92 (cpu), 94.08 (gpu)
CPU/GPU utilization: 0.17 (cores), 1.00 (devices)
Percent of GPU time waiting for GPU: 46.87
Started with 1857365 terms and sieved to 281719. 385050 remaining terms written to xyyx.pfgw
[/code]

 rogue 2014-07-07 20:56

I think I just found another "Out of resources" trigger. Working on it.

 rogue 2014-07-07 22:05

I fixed that one, but I still have a problem elsewhere. It is only an issue when trying to do obscenely large search spaces. I tried to implement different logic to collect factors, but my video card does not support the OpenCL functcion atom_min.

 wombatman 2014-07-07 23:44

No problem. Like you said, smaller ranges work fine. I just wanted to point it out in case it was a larger issue than that. Very impressive work!

 rogue 2014-07-08 12:04

Thanks. This was a very difficult program to optimize. If the range of x is large you think of optimizing in one direction. If the range of y is large, then you think of optimizing in a different direction. If both are large, then you think of a way to get the best of both worlds. Unfortunately memory and latency quickly get in the way of most potential optimizations.

Due to the bug in MultiSieve, I'm going to sieve x^y+y^x for x and y < 10000. I will also update PRPNet to support an x^y+y^x search. I don't know if I'll be able to run every term (as there will probably be close to a million after sieving), but since all of them are small it might be doable.

 Batalov 2014-07-08 16:16

The --platform=1 option is still ignored.
(and additionally, the existence of -f and -F options is denied by the program)
[CODE]\$ ./xyyxsievecl64.exe --platform=1 -x2 -X2500 -y7000 -Y7500 -P1e6 -t1 -s2000 -S+ -oxyyx.pfgw -f1 -F1
xyyxsievecl v1.0.1, a GPU program to find factors numbers of the form x^y+y^x
Quick elimination of terms info (in order of check):
626000 because the term is even
118610 because x and y have a common divisor
357496 because the term is divisible by a prime < 100
List of available platforms and devices
C:\Users\Serge\Desktop\XYYXsieve\xyyxsievecl64.exe: invalid option -- F
C:\Users\Serge\Desktop\XYYXsieve\xyyxsievecl64.exe: invalid option -- 1
[U]Platform 0 has no available devices.[/U] Here is a list of platforms and devices:
Platform 0 is a Advanced Micro Devices, Inc. AMD Accelerated Parallel Processing, version OpenCL 1.2 AMD-APP (938.2)
No devices
Platform 1 is a NVIDIA Corporation NVIDIA CUDA, version OpenCL 1.1 CUDA 6.0.1
Device 0 is a NVIDIA Corporation GeForce GTX 570[/CODE]Says: "[U]Platform 0 has no available devices[/U]", does not switch to platform 1 (even though instructed) and quits.

Also, minor: there is no line break after "Here is a list of platforms and devices:" message.

 rogue 2014-07-08 17:46

1 Attachment(s)
I didn't change the version number, but this should be 1.0.2.

I finally tracked down and fixed the main "Out of resources" issue. I'm referring to the one that impacts large search ranges. I wasn't reinitializing a variable in a loop.

I fixed some issues with continuing from a previous output file.

I don't know why --platform doesn't work so I need to investigate that, but -f should now work to change the platform (although I haven't tested it).

 rogue 2014-07-08 18:08

I spoke too soon on the "Out of resources" issue. I thought I had nailed it, but I just one with the latest build. :censored:

 Batalov 2014-07-08 19:17

[QUOTE=rogue;377570]It appears that MultiSieve removes terms for which it does not have a factor. [/QUOTE]
Just curious if this was only for xy+-yx?
Was it by any chance a problem for GC/GW sieves?

 rogue 2014-07-08 19:26

[QUOTE=Batalov;377684]Just curious if this was only for xy+-yx?
Was it by any chance a problem for GC/GW sieves?[/QUOTE]

I don't understand your question. This program is specific for x^y+/-y^x. MultiSieve is more generic. Almost every component of MultiSieve is now done much faster by other software. For example, gcwsieve is the preferred siever for Generalized Cullens and Generalized Woodalls.

n*b^n+/-1 uses a discrete log. x^y+/-y^x does not use a discrete log.

 Batalov 2014-07-08 23:43

[QUOTE=rogue;377570]It appears that MultiSieve removes terms for which it does not have a factor. I've looked at the code and have not been able to figure out where that is occurring. This means that ranges sieved in the past should be sieved again presuming I can't track down why it is doing it, which I have little desire to do.[/QUOTE]
My question was about good old MultiSieve (because you wrote about MultiSieve's behavior). I quoted specifically the statement for which I had a followup question.

gcwsieve is (of course) faster, but some legacy GC/GW projects may have been done with MultiSieve (some bases were done more than ten years ago). But if under-reporting behavior was limited to the xyyx branch of MultiSieve only, then there shouldn't be any problem.

 rogue 2014-07-08 23:53

[QUOTE=Batalov;377715]My question was about good old MultiSieve (because you wrote about MultiSieve's behavior). I quoted specifically the statement for which I had a followup question.

gcwsieve is (of course) faster, but some legacy GC/GW projects may have been done with MultiSieve (some bases were done more than ten years ago). But if under-reporting behavior was limited to the xyyx branch of MultiSieve only, then there shouldn't be any problem.[/QUOTE]

Yes, they use completely different logic. They do share some lower level code, but that code is not where the bug is. If it were, then it would have manifested itself when comparing MultiSieve output to gcwsieve output.

 Batalov 2014-07-09 00:00

Right!

I think multisieve ("start new sieve" option) is still faster than the setup accessory sieve gcwsieve-1.3.5-smallp.zip (or Pari ad hoc) ... but then (after p>N) one should switch to gcwsieve.

 XYYXF 2014-07-09 19:14

The interval 20,001<=x<=40,000, 201<=y<=400 is reserved by Norbert Schneider.

 rogue 2014-07-09 19:27

Please ensure that he is not using MultiSieve due to the undiagnosed bug described earlier in this thread.

As I stated above I am sieving all y for all x < 10000 (using your nomenclature) and intend to retest to determine if any PRPs were missed.

 rogue 2014-07-11 02:00

I just checked in changes for PRPNet into sourceforge. It now supports x^y+y^x and x^y-y^x searches.

 rogue 2014-07-11 17:44

1 Attachment(s)
Here is v1.0.3. I fixed a calculation error in the stats that I inadvertently added in the previous build. I also made the following changes:

1) Delete the .ckpt file when done.
2) Write to the output file whenever the .ckpt file is written.
3) Apply factors from xyyxsieve.log to the input file before processing it.

These were designed to make it safer to stop and restart without losing factors.

 NorbSchneider 2014-07-12 20:03

I tested the program with command line:
xyyxsievecl64.exe -v --platform=1 -x4000 -X8020 -y8001 -Y8020 -P100000 -t8 -s2000 -S+ -oxyyx_8020p.out -f1 -F1

When i use -S+ then only the x^y+y^x numbers were sieved,
when -S- then x^y+y^x and x^y-y^x numbers were sieved,
when -Sb then error: Fatal Error: sign must be specified.

In the help file is: -S --sign=+/-/b sign to sieve for

I would like to use xyyxsievecl64.exe for only x^y-y^x numbers sieve.

 rogue 2014-07-19 00:30

My double-check for all x/y has yielded this:

1467^4076+4076^1467 is 3-PRP!

The range containing this PRP was searched prior to the creation of MultiSieve.

I'm still double-checking the range where both x and y are <= 10000. I'm about 50% complete.

 rogue 2014-07-19 00:34

1 Attachment(s)
[QUOTE=NorbSchneider;377975]I tested the program with command line:
xyyxsievecl64.exe -v --platform=1 -x4000 -X8020 -y8001 -Y8020 -P100000 -t8 -s2000 -S+ -oxyyx_8020p.out -f1 -F1

When i use -S+ then only the x^y+y^x numbers were sieved,
when -S- then x^y+y^x and x^y-y^x numbers were sieved,
when -Sb then error: Fatal Error: sign must be specified.

In the help file is: -S --sign=+/-/b sign to sieve for

I would like to use xyyxsievecl64.exe for only x^y-y^x numbers sieve.[/QUOTE]

Sorry that I missed your post. It is fixed in the attached. BTW you can use scientific notation for most parameters. In other words you can use -P1e5 instead of -P100000.

You're probably just testing, but I recommend using a larger range for y due to optimizations in the code. You might also want to increase -s and decrease -t to improve performance, but I'll leave that for you to figure out what works best on your machine.

 NorbSchneider 2014-07-21 12:31

[QUOTE=rogue;378542]Sorry that I missed your post. It is fixed in the attached. BTW you can use scientific notation for most parameters. In other words you can use -P1e5 instead of -P100000.
[/QUOTE]

Thank You!
[SIZE=2]It works perfect. I can now sieve only XY+, only XY- PRPs and the two simultaneously.[/SIZE]

 rogue 2014-07-24 12:59

[QUOTE=rogue;378541]My double-check for all x/y has yielded this:

1467^4076+4076^1467 is 3-PRP!

The range containing this PRP was searched prior to the creation of MultiSieve.

I'm still double-checking the range where both x and y are <= 10000. I'm about 50% complete.[/QUOTE]

I completed a double-check of the range. That was the only missing PRP. I'm continuing to double-check for x and y <= 12500. Unfortunately I didn't sieve as deeply as I would have liked because I took a Windows patch and now none of my OpenCL applications works on it. I have other computers, but most have a slower GPU. The one with the fastest GPU (a Mac) broke earlier this year when I installed Mavericks. I don't know what is going on with that, but I suspect that I need to re-install the OS to fix the problem and since it is my main computer I don't want to take it down for an extended period of time to fix the problem. Eventually I will or I'll talk my wife into an upgrade (of the computer, not her :grin:).

 rogue 2014-07-27 21:21

Here are two more PRPS that were missed. These were probably missed due to the bug in MultiSieve.

1490^11487+11487^1490
2239^12462+12462^2239

I've finished the double check where y <= 2500 and x <= 12500. I have a ways to go before finishing the rest of y <= 12500.

 Batalov 2014-07-27 21:31

Intriguingly, the second one is in factordb since July 11, 2014

P.S. EDIT: And in prptop (Norbert Schneider, 07/2014)

 rogue 2014-07-28 02:18

[QUOTE=Batalov;379175]Intriguingly, the second one is in factordb since July 11, 2014

P.S. EDIT: And in prptop (Norbert Schneider, 07/2014)[/QUOTE]

I wonder why they are missing on xyyxf's website.

 NorbSchneider 2014-07-28 06:22

I'm Norbert Schneider.

On July 26, 2014 have I finished my search in the interval
12,051<=x<=12,500, 2001<=y<=x-1.

My last new PRPs have i sent to Andrey Kulsha, but he has
so far the website not updated.

The last PRPs:
6330^12421+12421^6330, 47218 digits,
4569^12448+12448^4569, 45558 digits,
8602^12451+12451^8602, 48990 digits,
2239^12462+12462^2239, 41749 digits.

 XYYXF 2014-08-01 23:11

[QUOTE=NorbSchneider;379199]but he has so far the website not updated.[/QUOTE]I'm waiting for two C168 GNFS tasks, just a few days :)

 NorbSchneider 2014-08-02 22:31

I search now in the interval
20,001<=x<=40,000, 201<=y<=400.

I reached x=21,000 and found two new PRPs:
283^20956+20956^283, 51380 digits,
359^20992+20992^359, 53637 digits.

 rogue 2014-08-03 13:16

Two more PRPs:

2869^11736+11736^2869
3834^11473+11473^3834

Double-checking is now complete for y <= 5000 and x <= 12500 and 10000 < y <= 125000 and x <= 12500. I'm still working on 5000 < y <= 10000 and x <= 12500.

 rogue 2014-08-07 00:50

[QUOTE=rogue;379608]Two more PRPs:

2869^11736+11736^2869
3834^11473+11473^3834

Double-checking is now complete for y <= 5000 and x <= 12500 and 10000 < y <= 125000 and x <= 12500. I'm still working on 5000 < y <= 10000 and x <= 12500.[/QUOTE]

Verified list for y <= 7000 and x <= 12500.

I'm going on vacation for 17 days starting tomorrow. This will complete while I'm gone so expect an update when I return.

 NorbSchneider 2014-08-09 19:28

I reached x=22,000 and found one new PRP:
387^21694+21694^387, 56138 digits.

 XYYXF 2014-08-13 13:28

The page is finally updated: [url]http://xyyxf.at.tut.by/primes.html#0[/url]

 rogue 2014-08-28 01:56

The double-check has been completed for all x and y <= 12500. Nothing new to report.

 NorbSchneider 2014-08-28 06:30

I reached x=24,000 and found one new PRP:
247^23412+23412^247, 56018 digits.

 NorbSchneider 2014-09-21 18:48

I reached x=26,000 and found one new PRP:
291^25742+25742^291, 63426 digits.

 NorbSchneider 2014-10-05 00:33

I reached x=27,000 and found one new PRP:
267^26336+26336^267, 63905 digits.

 NorbSchneider 2014-11-01 07:59

I reached x=30,000 and found one new PRP:
257^29356+29356^257, 70746 digits.

 firejuggler 2014-11-04 23:13

reserving x=2501=> 3000 and y=12501=>15000
2696^14313+14313^2696 is a 3-PRP (49104 digits)

 NorbSchneider 2014-11-08 13:52

I reached x=31,000 and found two new PRPs:
300^30247+30247^300, 74926 digits,
241^30280+30280^241, 72128 digits.

 firejuggler 2014-11-14 17:45

range x=2500->3000 and y=12500->15000 done, 6 primes found

2844^13855+13855^2844
2858^14763+14763^2858
2880^12617+12617^2880
2950^13563+13563^2950
2975^12664+12664^2975

Edit : those are PRP, not prime.

 paulunderwood 2014-11-14 17:47

[QUOTE=firejuggler;387631]range x=2500->3000 and y=12500->15000 done, 6 primes found

2844^13855+13855^2844
2858^14763+14763^2858
2880^12617+12617^2880
2950^13563+13563^2950
2975^12664+12664^2975[/QUOTE]

PRPs only?

 firejuggler 2014-11-14 17:54

 Batalov 2014-11-14 17:55

Of course. None of us has access to CIDE, and even with CIDE the current record is 30,008 digit size.

 XYYXF 2014-11-14 21:30

[QUOTE=firejuggler;387631]range x=2500->3000 and y=12500->15000 done, 6 primes found [/QUOTE]Thanks a lot :-)

Now it would be nice to fill the gap 2000 < x <= 2500 for 12500 < y <= 15000 :-)

 firejuggler 2014-11-14 23:32

I was pretty sure It was already reserved. If no one volonteer before I come back from my trip ( mid december) ten i'll do it.

 XYYXF 2014-12-02 00:49

[QUOTE=firejuggler;387667]I was pretty sure It was already reserved. If no one volonteer before I come back from my trip ( mid december) ten i'll do it.[/QUOTE]Thanks a lot. BTW, could you please specify your name to put it there?
[url]http://xyyxf.at.tut.by/primes.html#0[/url]

 XYYXF 2014-12-02 00:56

[QUOTE=fivemack;373604]I am running Y=18, should make it to 300k by the end of the month unless I've screwed up my calculations somewhere.[/QUOTE]Meanwhile I got y=18 for 300k < x < 500k:
[url]http://www.primefan.ru/stuff/primes/xyyx/18.txt[/url]

All times are UTC. The time now is 19:56.