mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > 15k Search

 
 
Thread Tools
Old 2005-01-31, 02:12   #1
Tumo
 
Jan 2005

19 Posts
Default Possible loophole/bug in NPG 2.82 ???

Please forgive my being a novice, but i stumbled onto either a user error
(which i suspect is most likely) or a possible problem with NPG (hard to believe one could exist).

NPG, Dec 2004 version...

try k.b^n-1 with k fixed

enter b=2, k=7 nmin=2, nmax=65536 and run (with or w/o verify)

@P= 2G, stop the sieve... examine the output file.. you will find something
like:
2256610126:M:0:2:258
7 29
7 45
7 101
7 177

now start again, and notice the Nmin window has updated from 2 to 29.

At some point above 4G (I stopped closer to 6G)... stop the sieve again.

examine the output files.

I find this:
6426074968:M:0:2:258
7 45
7 101
7 177
I have verified this condition on both AMD64 FX and Intel P4b (both are SSE2 machines)... both on Win/XP.. AMD on SP1, P4 on SP2.

7*2^29-1 is valid from everything I've seen, listed in the forums and shows
up valid by LLR 3.3.

Also, i believe other values lower than 29 are missing, true?



I tripped over this after the recommended 24+ hours of sieving for an LLR run. I had crossed well over 250G at that point... When I ran the numbers, NOTHING came up prime. According to the period/frequency of the prime, I should have had several hits.

I went to the 'Riesel < 300' page, selected a test range for others and did it again, and again... then went back to basics which brings me here.



May I ask what it is I am tripping over? I am stumped.

I thank you for your time and tolerance.

I also thank you in advance for your assistance.



Chuck

Last fiddled with by Tumo on 2005-01-31 at 02:17
Tumo is offline  
Old 2005-01-31, 09:01   #2
Jean Penné
 
Jean Penné's Avatar
 
May 2004
FRANCE

2×5×59 Posts
Default Don't worry about tiny exponents values !

Quote:
Originally Posted by Tumo
Please forgive my being a novice, but i stumbled onto either a user error
(which i suspect is most likely) or a possible problem with NPG (hard to believe one could exist).

NPG, Dec 2004 version...

try k.b^n-1 with k fixed

enter b=2, k=7 nmin=2, nmax=65536 and run (with or w/o verify)

@P= 2G, stop the sieve... examine the output file.. you will find something
like:
2256610126:M:0:2:258
7 29
7 45
7 101
7 177

now start again, and notice the Nmin window has updated from 2 to 29.

At some point above 4G (I stopped closer to 6G)... stop the sieve again.

examine the output files.

I find this:
6426074968:M:0:2:258
7 45
7 101
7 177
I have verified this condition on both AMD64 FX and Intel P4b (both are SSE2 machines)... both on Win/XP.. AMD on SP1, P4 on SP2.

7*2^29-1 is valid from everything I've seen, listed in the forums and shows
up valid by LLR 3.3.

Also, i believe other values lower than 29 are missing, true?



I tripped over this after the recommended 24+ hours of sieving for an LLR run. I had crossed well over 250G at that point... When I ran the numbers, NOTHING came up prime. According to the period/frequency of the prime, I should have had several hits.

I went to the 'Riesel < 300' page, selected a test range for others and did it again, and again... then went back to basics which brings me here.



May I ask what it is I am tripping over? I am stumped.

I thank you for your time and tolerance.

I also thank you in advance for your assistance.



Chuck
When sieving in fixed k mode, Newpgen eliminates a value when it finds itself
as a divisor !

For example :

7*2^29-1 = 3758096383 is prime, but is eliminated when the sieve reaches
this prime value and tries it as a divisor, etc...
This drawback only occurs for tiny values of n, less than 64, so the best
thing to do is starting the sieve for n = 64 and test the primality for all
n values below, which is very fast !

I hope this can help you...

Regards,

Jean
Jean Penné is offline  
Old 2005-01-31, 10:16   #3
Keller
 
May 2004

22·7 Posts
Default

But this is a serious bug and might have caused lots of problems ...
For example Rieselsieve, PSP or SoB ...
Maybe values of n have been missed that are smaller than n=64 and maybe they are wasting lots of work because a tiny number has been missed ... Who knows ;)

Last fiddled with by Keller on 2005-01-31 at 10:17
Keller is offline  
Old 2005-01-31, 10:52   #4
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

1011000011102 Posts
Default

Hello,

Yesterday I noticed that too. I wanted to reserve a Sierpinsksibase4k=63411 but I first run newpgen 2.82 to see the size of the outputfile.

k=63411; base=4; nmin=10000, nmax=100000
The first run gave me this:

16738300:P:0:4:257
63411 10000
63411 10016
63411 10076
63411 10140
63411 10196
63411 10212
63411 10256
63411 10292
63411 10302
63411 10307
63411 10308
63411 10313
63411 10317
63411 10320
63411 10322
63411 10326
63411 10331
63411 10337
63411 10338
63411 10352
63411 10353
63411 10361
63411 10362
63411 10365
63411 10370
63411 10377
63411 10380
63411 10385
63411 10388
63411 10395

And the second one this:

36278740:P:0:4:257
63411 10016
63411 10076
63411 10140
63411 10196
63411 10212
63411 10256
63411 10292
63411 10320
63411 10400


I still have both files.

Cheers,

Carlos

Last fiddled with by em99010pepe on 2005-01-31 at 10:54
em99010pepe is offline  
Old 2005-01-31, 12:11   #5
thommy
 

110008 Posts
Default

Quote:
Originally Posted by Keller
But this is a serious bug and might have caused lots of problems ...
For example Rieselsieve, PSP or SoB ...
Maybe values of n have been missed that are smaller than n=64 and maybe they are wasting lots of work because a tiny number has been missed ... Who knows ;)

LOL, you really think noone has tested n values less than 64 until now. Man, i bet this was done hundreds of times, with many software. And most of that can even be done by hand! there really are no primes for sob, riesel, psp and so on...
 
Old 2005-02-01, 00:56   #6
Tumo
 
Jan 2005

19 Posts
Default

I can understand the low value situation easily and accept that.

I present to you this:

K=237, Base=2, Nmin=524288, Nmax=1048576, k.b^n-1 with fixed k.


The same 'collapse' occurs. Understanding that it's a recursive condition of not eliminating an N (aka K/N pair).. and then having that same N (K/N pair) be removed by a higher value P. It is easy for me to sieve up to P = 1 Tera in 24 hours or so.

Given this to make perfect sense, at what 'P' value does one stop sieving?

I sieve for 24 hours , as commonly recommended, and this usually puts me in the High-'G' range. Is it common and reasonable to expect that only the largest N of that sieve, regardless of P,K, or N ranges set at the start, will be left? It seems this is a recursive factorization issue and I see now that I should probably rephrase my initial question to be:

"for a given K, sieving in a particular range of Nmin->Nmax, at what point do you tell a novice when to stop the sieve and simply 'bite the bullet', running PRP/LLR on all remaining N in the file (including the N that would have been removed if P were to run higher)?"


Sorry if I am being thick (slow to learn) about this, I am just trying to understand the relationships that you all have had great experience with. I can sieve at a very fast speed, but my LLR time is embarassingly slow, hence my desire to remove as many N as possible and reasonable.


Thanks for all the advice.
Thanks in advance for your patience.

T.

Last fiddled with by Tumo on 2005-02-01 at 00:59
Tumo is offline  
Old 2005-02-01, 01:52   #7
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

E2616 Posts
Default

Quote:
Originally Posted by Tumo
I present to you this:
K=237, Base=2, Nmin=524288, Nmax=1048576, k.b^n-1 with fixed k.
The same 'collapse' occurs.
Can you be more specific? What do you mean by 'collapse'. Sorry, but I don't have time to try it right now.

For one possible decision of when to stop sieving check the "Expert Users" section here although, fankly speaking I don't use it. It depends on the weight of k, i.e., the survival rate, how many machines do you have, do you PRP/LLR on all machines or you have some for sieving only. Use P3's only to sieve, Athlons both to sieve and LLR and P4's only to LLR. For medium weight k's in the n=200-500k range sieving to 1E12 (1T) is enough. For larger n's to 1M sieve at least to 2T.

Also, please note that we have an informal reservation system in this thread for small k<300 where you can declare k's and the ranges of n you are currently working on. So that we don't duplicate our efforts. In case of high-weight 15k's you can just reserve one or more k's and test them as much as you want.

For more details on project currently running please read all posts in this thread and check the links mentioned there.

Last fiddled with by Kosmaj on 2005-02-01 at 01:56
Kosmaj is offline  
Old 2005-02-01, 15:33   #8
TTn
 

1D2316 Posts
Wink sieve time

Quote:
"for a given K, sieving in a particular range of Nmin->Nmax, at what point do you tell a novice when to stop the sieve and simply 'bite the bullet', running PRP/LLR on all remaining N in the file (including the N that would have been removed if P were to run higher)?"
The answer for a novice windows user is,
"Use RMA's automation option."

You can do "fixed k" sieving, without the preference for
"RMA enable" checked, to sieve and test at the same time.

It's still in a beta stage, but it works ok for most.
I'm just gearing up for multi-base implementation of the algorithm.

Last fiddled with by TTn on 2005-02-01 at 15:34
 
Old 2005-02-01, 16:09   #9
TTn
 

22·557 Posts
Default broken

RMA BETA 2.9 does not do that option right now.
I made some changes and forgot to update the "other options".
Soon this will be fixed...(tonight).


I should explain that:
RMA's Full Auto, follows Paul Jobling's statement:

In the Help/contents tab of Newpgen it states:
"In general, you ought to sieve until the rate at which NewPGen is
throwing out composites is equal to the rate at which Proth/PRP/PFGW/LLR
can perform a primality test on the numbers. Actually, you should stop a little sooner -
the idea is to find primes, after all."(Paul Jobling)


This is precisely what the Full Auto option does.

Last fiddled with by TTn on 2005-02-01 at 16:12
 
 

Thread Tools


All times are UTC. The time now is 22:41.


Wed Jun 29 22:41:59 UTC 2022 up 76 days, 20:43, 0 users, load averages: 1.36, 1.35, 1.47

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔