mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > XYYXF Project

Reply
 
Thread Tools
Old 2014-05-16, 21:30   #23
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

237816 Posts
Default

Reserving [330001-400000, 11-17]
Batalov is offline   Reply With Quote
Old 2014-05-16, 22:40   #24
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·32·52·13 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
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.
rogue is online now   Reply With Quote
Old 2014-05-16, 22:54   #25
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×227 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2014-05-17, 17:34   #26
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

585010 Posts
Default

Quote:
Originally Posted by Batalov View Post
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.
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 this page 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.
rogue is online now   Reply With Quote
Old 2014-05-17, 18:44   #27
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×227 Posts
Default

Quote:
Originally Posted by Batalov View Post
For values one less than a prime, the candidate list shrinks dramatically immediately after starting.
Lemma (the obvious) 1. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

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

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 is offline   Reply With Quote
Old 2014-05-17, 19:02   #28
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×227 Posts
Default

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

Reserving [400001-500000, 11-17] - one less step in the stepwise function, as you asked, Andrey!
Batalov is offline   Reply With Quote
Old 2014-05-17, 21:23   #29
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·32·52·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
Lemma (the obvious) 1. For an odd prime p and x=p-1, x^y+y^x is composite for all y>1 coprime with p.

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

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
Hadn't thought of that. It would certainly reduce the initial memory size considerably for certain x or y
rogue is online now   Reply With Quote
Old 2014-05-17, 22:57   #30
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24·52 Posts
Default

Quote:
Originally Posted by rogue View Post
I also have the opinion that x and y should be swapped in those tables for clarification.
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? :-)
XYYXF is offline   Reply With Quote
Old 2014-05-18, 02:42   #31
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×32×52×13 Posts
Default

Quote:
Originally Posted by XYYXF View Post
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? :-)
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.
rogue is online now   Reply With Quote
Old 2014-05-18, 03:07   #32
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011011110002 Posts
Smile

It is a classic case of little- vs. big-endians war.
But it's not new! Swift already described it:
Quote:
Originally Posted by 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.
Let's not loose sleep over it. C'est tout de même.
Batalov is offline   Reply With Quote
Old 2014-05-19, 06:25   #33
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×227 Posts
Default

[400001-500000, 11-17] is done, no primes. (ME~=0.2)
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Leyland Primes: ECPP proofs Batalov XYYXF Project 16 2019-08-04 00:32
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
On Leyland Primes davar55 Puzzles 9 2016-03-15 20:55
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 17:19.

Sat Aug 8 17:19:08 UTC 2020 up 22 days, 13:05, 1 user, load averages: 2.46, 1.98, 1.81

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