Reserving [330001400000, 1117]

[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. 
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 34 times larger. 
[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 34 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. 
[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=p1, 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] p1 (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 
Done with [330001400000, 1117], no primes.
Reserving [400001500000, 1117]  one less step in the stepwise function, as you asked, Andrey! 
[QUOTE=Batalov;373704][B]Lemma (the obvious) 1[/B]. For an odd prime p and x=p1, 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] p1 (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 
[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? :) 
[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^yy^x and for that to be > 0, x must be less than y. 
It is a classic case of little vs. bigendians war.
But it's not new! Swift already described it: [QUOTE=Wiki]The novel further describes an intraLilliputian 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 greatgrandfather, 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 BigEndians (those who broke their eggs at the larger end) and LittleEndians 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 BigEndians gained favour in Blefuscu.[/QUOTE] Let's not loose sleep over it. C'est tout de même. 
[400001500000, 1117] is done, no primes. (ME~=0.2)

All times are UTC. The time now is 19:46. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.