Extrapolation: How long until the minimum megaprime?

[KEP]

Originally Posted by axn

Hmmm. Don't forget to look up & down that list -- there may be more than one b^n+k.



Dang. Does it crash as soon as it starts (that's been my problem)? Good luck with the quad core.

Anyway, if you don't have any further luck with NewPGen, I'll try to put something together.

PS:- Try contacting bsquared. He's written most of the basic low-level routines, and has implemented kick ass SoE. So it'd be a trivial thing for him to put together a state-of-the-art sieve for this problem.

Well if there is more than those b^n+k functions, it is hiding good , to be honest I expect no more luck on my Quad than I have had an my previous systems, I actually think there may be a programming error in NewPGen, because it isn't crashing for all k-values, in b^n+k, but for those is crashes on, it crashes immediately.

I'll try and send bsquared the same PM I has just sent to Rogue and Ken_g6, so he can get a chance to put something together for me. So let's put it this way for now: If none of the three has the commitment to put together such a siever that I need, I'll come back and ask you to put a siever together for me, but for now let's wait and see what they come back with.

Thanks for your help.

Kenneth

[bsquared]

Hi Kenneth - I saw your PM and thought I'd respond here.

I just had a few questions, since I'm not very familiar with the terminology over here. Can you or someone explain the metrics being used? e.g., 100G/day, 1M p/sec, etc. What exactly are these measuring?

Also, just wanted to make sure I understood the problem precisely. You want to look at a range of integers between two points (where the two points are large, on the order of 10^6 digits) and, through sieving, remove as many composites as possible, correct? Presumably then you'd take the surviving candidates and do PRP testing on them, but that would be someone else's problem, right, or is that also a desirement of this code? Finally, what is the upper bound on sieve primes you'd like to use?

[KEP]

Originally Posted by bsquared

Hi Kenneth - I saw your PM and thought I'd respond here.

I just had a few questions, since I'm not very familiar with the terminology over here. Can you or someone explain the metrics being used? e.g., 100G/day, 1M p/sec, etc. What exactly are these measuring?

Also, just wanted to make sure I understood the problem precisely. You want to look at a range of integers between two points (where the two points are large, on the order of 10^6 digits) and, through sieving, remove as many composites as possible, correct? Presumably then you'd take the surviving candidates and do PRP testing on them, but that would be someone else's problem, right, or is that also a desirement of this code? Finally, what is the upper bound on sieve primes you'd like to use?

Thanks for your reply bsquared. I'm understanding it as you are willing to wanna help out in making a new siever for me. Now to your range of questions:

p= the primefactors, 3, 5, 7, 11 (in this case p is 3 to 11), so p 100G/day means that if I on day one sieves from 1 to 100e9, then on day 2 I'll sieve range 100e9 to 200e9 and remove all factors found in that range.

Yes I want to test a group of integers between two points, i.e. 10e9 to 11e9 and upward, where all composites with a factor in that range of integers is removed, to save a later LLR test. The program only has to be able to sieve and leave the PRP testing for other programs to handle.

It would be nice if there could be "no upper boundry" on the primefactors or that if the siever at least could test all primefactors up to 2^62 like srsieve can. Also the program has to be userfriendly and able to run under windows.

Hope I got it all.

Take care

Kenneth

Ps. 1 M/sec means "1 million p per second"

[bsquared]

Originally Posted by KEP

Thanks for your reply bsquared. I'm understanding it as you are willing to wanna help out in making a new siever for me. Now to your range of questions:

I can't commit to helping out until I figure out how much work it would be. I have several of the pieces, but I don't know yet how close that puts me to a solution that is fast.

Originally Posted by KEP

p= the primefactors, 3, 5, 7, 11 (in this case p is 3 to 11), so p 100G/day means that if I on day one sieves from 1 to 100e9, then on day 2 I'll sieve range 100e9 to 200e9 and remove all factors found in that range.
Yes I want to test a group of integers between two points, i.e. 10e9 to 11e9 and upward, where all composites with a factor in that range of integers is removed, to save a later LLR test. The program only has to be able to sieve and leave the PRP testing for other programs to handle.

Well... I'm afraid this hasn't helped my confusion much. You are using "range" with a couple different meanings. There is a "range" of sieve primes, i.e., 0 to 100e9, and there is a "range" of integers to be tested for compositude. In your PM you said the second meaning of range was the set of integers between 10^999999 and 10^999999 + 5e6, correct? So is p/sec measuring the rate at which you are progressing through the first meaning of range or the second? I think it is the first, but want to be sure.

My roadblock is that it doesn't seem like this should be called a sieve, since with a tiny range of integers like 5e6, you are not really sieving much. Almost every prime one "sieves" with will only hit that range once, so it is more like trial division. The stuff I've written is tailored toward efficient sieving, not trial division, which is why I'm not sure yet if I can readily help you. I'll have to get back to you.

- ben.

[R.D. Silverman]

Originally Posted by bsquared

Hi Kenneth - I saw your PM and thought I'd respond here.

I just had a few questions, since I'm not very familiar with the terminology over here. Can you or someone explain the metrics being used? e.g., 100G/day, 1M p/sec, etc. What exactly are these measuring?

Also, just wanted to make sure I understood the problem precisely. You want to look at a range of integers between two points (where the two points are large, on the order of 10^6 digits) and, through sieving, remove as many composites as possible, correct? Presumably then you'd take the surviving candidates and do PRP testing on them, but that would be someone else's problem, right, or is that also a desirement of this code? Finally, what is the upper bound on sieve primes you'd like to use?

Allow me to point out that we ALREADY know primes with more than
one million digits.

[bsquared]

Originally Posted by R.D. Silverman

Allow me to point out that we ALREADY know primes with more than
one million digits.

True, but I don't believe that's the point of this thread.

[axn]

Originally Posted by bsquared

Also, just wanted to make sure I understood the problem precisely. You want to look at a range of integers between two points (where the two points are large, on the order of 10^6 digits) and, through sieving, remove as many composites as possible, correct? Presumably then you'd take the surviving candidates and do PRP testing on them, but that would be someone else's problem, right, or is that also a desirement of this code? Finally, what is the upper bound on sieve primes you'd like to use?

Answering second part first. The objective of this thread is to find the smallest million digit prime. i.e. Find k such that 10^999999+k is a PRP and no other smaller k is a PRP.
KEP will do (or coordinate the PRP). But he needs a custom sieve.

Originally Posted by bsquared

I just had a few questions, since I'm not very familiar with the terminology over here. Can you or someone explain the metrics being used? e.g., 100G/day, 1M p/sec, etc. What exactly are these measuring?

Speed at which we'd be making progress thru the sieve. A good speed is if we can go thru a p-range of 10^13 in a day

Logic.
Input: start-p, end-p

1. Read all the candidate k's from a file and populate bitmap.
2. For all primes between start-p and end-p
Compute k = p - 10^999999 mod p. If k is within bitmap, clear it and print factor.

Like GIMPS TF, you can include some quasi-primes also in the sieve

[axn]

Originally Posted by KEP

Well if there is more than those b^n+k functions, it is hiding good

Yep. It is called "AP: b^n+2k-1 (-2 if b is odd)". That's what you need.

EDIT:- Woohoo! Managed to get NewPGen to work. You need to add a DEP exception to NewPGen.exe in windows.

EDIT2:- Currently at 11.6 billion, after 6 minutes of sieving. 13k's per second.

[KEP]

Originally Posted by bsquared

I can't commit to helping out until I figure out how much work it would be. I have several of the pieces, but I don't know yet how close that puts me to a solution that is fast.



Well... I'm afraid this hasn't helped my confusion much. You are using "range" with a couple different meanings. There is a "range" of sieve primes, i.e., 0 to 100e9, and there is a "range" of integers to be tested for compositude. In your PM you said the second meaning of range was the set of integers between 10^999999 and 10^999999 + 5e6, correct? So is p/sec measuring the rate at which you are progressing through the first meaning of range or the second? I think it is the first, but want to be sure.

My roadblock is that it doesn't seem like this should be called a sieve, since with a tiny range of integers like 5e6, you are not really sieving much. Almost every prime one "sieves" with will only hit that range once, so it is more like trial division. The stuff I've written is tailored toward efficient sieving, not trial division, which is why I'm not sure yet if I can readily help you. I'll have to get back to you.

- ben.

Hope this helps:

The siever or trial divisioner, should test all candidates from, 10^999999+1 to 10^999999+4999999, for factors, with factors being allowed to have a length up to at least 2^62-1 (wich is the sievelimit in srsieve). You are correct, that each factor will only hit the search area once for every factor, since all factors is above 4999999. Neither Mark or Ken had the time to help make such a siever though both agreed that it wouldn't be very difficult since the math should be fairly simple. Please read this quotation from Ken, maybe it helps clear up what I exactly is looking for:

"The math is straightforward:

10^999999+x = 0 (mod p)
x = -10^999999 (mod p)

You just need a fast mulmod (base 10) for each p; then negate it and see if it falls in your range."

Within the quotation marks, is both the math descriped, and the search area is in my case: x from 1 to 4,999,999.

Hope this helps, else try and PM me and let's see if with with short questions and short answer can come to a sort of understanding. Please forgive me in advance, english (even though I'm pretty comprehensive and skilled in it) is not my native language, so sometimes I have thoughts where I don't know how to explain it in a way that people can actually understand what I think of. But most often patience on both sides can solve the problems that may cause

Let me know what you think and feel.

Take care

Kenneth

[bsquared]

Originally Posted by axn

Answering second part first. The objective of this thread is to find the smallest million digit prime. i.e. Find k such that 10^999999+k is a PRP and no other smaller k is a PRP.
KEP will do (or coordinate the PRP). But he needs a custom sieve.


Speed at which we'd be making progress thru the sieve. A good speed is if we can go thru a p-range of 10^13.

Logic.
Input: start-p, end-p

1. Read all the candidate k's from a file and populate bitmap.
2. For all primes between start-p and end-p
Compute k = p - 10^999999 mod p. If k is within bitmap, clear it and print factor.

Like GIMPS TF, you can include some quasi-primes also in the sieve

Ok, thanks.

I've got something already implemented that goes at about 15kp/sec. It simply uses gmp for the large modp operation. It is also threadable, so 4 threads goes at about 60kp/sec. I very much doubt the current input and output are what are desired, though, but that would be easy to change. It is also limited to an upper p bound of 2^32 (~ 4e9). It's less clear how easy that is to change, but is probably doable.

Point of clarification: does the p/sec measure the number of primes sieved per second, or the range of primes sieved per second? In other words, if I set start-p = 0 and end-p = 100e6, then there are 5761455 primes in that range. My p/sec figures above measured actual p per unit time. If instead you're measuring range speed, then it currently runs at about 268kp/sec (100e6 / 372 seconds vs. 5761455 / 372 sec), single threaded.

[KEP]

Originally Posted by axn

Yep. It is called "AP: b^n+2k-1 (-2 if b is odd)". That's what you need.

EDIT:- Woohoo! Managed to get NewPGen to work. You need to add a DEP exception to NewPGen.exe in windows.

EDIT2:- Currently at 11.6 billion, after 6 minutes of sieving. 13k's per second.

What kind of digits do you get? When I use that function, it tells me that I'm sieving numbers with digits from 1000000 to 1000006, and that is not what I'm looking for. Maybe it is a bug in NewPGen or maybe the function is mallocly descriped.

If your NewPGen with the exception is actually working correct, could you send me that NewPGen version? Because my version seems to be doing something wrong and I'm no programmer, so I can't do anything about it.

EDIT2: I just tested, and the AP function actually does the same as k*b^n-1, maybe your DEF exception accounts for that, else you're just waisting time, sorry!

Kenneth