Expected Time To Complete A Quest Function
 

Greetings fellow primers,

I had a thought recently (always a dangerous proposition!) about "ballparking" how long it might take to find a prime currently being sought as a function of a few variables.

1. Your percentage sieved (or, perhaps better, your percentage of candidates remaining).

2. The number of exponents your hardware is capable of examining per day.

3. The number of unsieved exponents you might have to examine before finding a prime.

Let r = the decimal form of the percentage of remaining candidates.
Let n = the number of exponents the hardware can examine per day.
Let u = the number of unsieved exponents you would need to examine before finding a prime.

Let d = the number of days you will have to search to find a prime

d = u/(n/r) = ur/n.

So if you sieved a range of 1,000,000 exponents to a depth of 93% (70,000 candidates remained) and your hardware can examine 500 of these exponents per day, and the likelihood is that only 1 prime exists among your candidates, then

d = (1000000)(.07)/500 = 140 days to find your prime.

Of course, the value for n will decrease as the exponent increases, this is just an average value.

Other than that, are there any "holes" in this speculation?

I went though all of this to also see what the cost-benefit is for each additional percentage point of sieving.

In the example above, each reduction by 1% saves 20 days of search time. In my case, it will take about 32 days to sieve the next 1%, so it is not worth sieving and time is better spent on working with the resulting set.

But, for each sieving scenario and depth, this will, of course, be different. It's a convenient way to see whether you should spend more time sieving or get searching.

The traditional wisdom is to only start testing when candidates are being removed from the sieve at a slower rate than you can test them.

If you want to work out when this might be then you can make the assumption that the sieve speed remains constant (basically true when you get into the high billions or trillions), and another assumption that the rate of removal from the sieve is proportionate to 1/log(sieve depth).

Here is a completely artificial example which assumes I am correct about the 1/log(sieve depth) thing, I may very well not be so please call me on it if I'm not.

Suppose you're at a sieve depth of 1T, and you have 10 candidates being removed every second. The sieve is progressing at a rate of ~250 million / s and the smallest candidates you want to test take 0.125 seconds.

So you want to calculate, in this case, how long it will take for the sieve to drop to 8 candidates removed / second (0.125 seconds / candidate).

You have two equations here:
k / log(10^12) = 10
k / log(x) = 8

I'll save the algebra, but it's relatively easy to see that:
x = 10^15

So now you know the sieve target is 1Q, and you can work out that it will take 46.3 days to reach it.

Obviously you would then have to calculate the time to run the primality tests on the remaining candidates which for most tests is a relatively simple matter.

Calculation of your variable u could be a trickier proposition though.

[QUOTE=lavalamp;283273]I may very well not be so please call me on it if I'm not.[/quote]
Ok. Consider it done :smile:


[QUOTE=lavalamp;283273]So you want to calculate, in this case, how long it will take for the sieve to drop to 8 candidates removed / second (0.125 seconds / candidate).

You have two equations here:
k / log(10^12) = 10
k / log(x) = 8

I'll save the algebra, but it's relatively easy to see that:
x = 10^15
[/QUOTE]
If you had the same number of candidates left in the sieve file, then the correct calculation is as simple as 10^12 / (8/10) = 1.25*10^12. The reason : a given candidate 'p' divides 1/p of the factors. So number of factors found/sec is likewise proportional to 1/p (not 1/log(p)).

But, the number of candidates left in the sieve file won't be the same either. It'll be about 1-log(p1)/log(p2)=0.8% less. (which in this case is small enough that we can ignore it -- but if the ration of p2:p1 is much larger, then that'll add a small but significant reduction in the number of factors found).

Hm, is that true even though the sieve does not eliminate all composite potential factors?

Apologies if this is obvious but it's a bit late here and there are soft cats, so I'm finding it a bit hard to brain.

[QUOTE=lavalamp;283288]Hm, is that true even though the sieve does not eliminate all composite potential factors?[/QUOTE]
Yes. Mostly. You can do a minor correction for that using log(p). You can see [URL="http://www.mersenneforum.org/showthread.php?t=6153"]this[/URL] thread for some more info

[QUOTE=lavalamp;283273]The traditional wisdom is to only start testing when candidates are being removed from the sieve at a slower rate than you can test them.
[/QUOTE]

Ah, yes, but I am also prime-hunting [B]while [/B]the sieving is taking place, call it "live sieving" if you want.

Consider, in your example, how many primes you could have tested in those 40+ days. That complicates things a bit.

My sieve ranges are arbitrarily large, so that whatever I am prime-hunting is only a small subset of the total. That way, I can "start looking", and when I see the siever has reached a certain depth, I stop both processes, and re-hunt on the better-sieved file(s). Then I resume sieving, etc.

But no matter how deeply sieved and how many primes I find, there comes a point where the sun would burn out before I find the next one. :smile:

I am looking for "reasonable lengths of time" to be returned by my function, so that I don't waste CPU months hunting what won't be found.

[QUOTE=SaneMur;283325]Ah, yes, but I am also prime-hunting [B]while [/B]the sieving is taking place, call it "live sieving" if you want.

Consider, in your example, how many primes you could have tested in those 40+ days. That complicates things a bit.[/QUOTE]Unless you have a machine that is better at testing than sieving, and another machine that is better at sieving than testing, then this approach is sub-optimal. Even if you do have two such machines, there's still only a narrow range in which it's better to have one sieving and one testing at the same time.

If you can remove candidates faster by sieving, then any cycles you spend on testing are slowing you down.

The only reason to run a few tests on numbers that aren't optimally sieved is so that you can figure out how long the tests take so you can optimally sieve the rest of the candidates.

axn, I will read through that thread you linked and meditate on the matter.

[QUOTE=lavalamp;283334]Unless you have a machine that is better at testing than sieving, and another machine that is better at sieving than testing, then this approach is sub-optimal. Even if you do have two such machines, there's still only a narrow range in which it's better to have one sieving and one testing at the same time.[/QUOTE]

There is another scenario where [B]live sieving[/B] makes sense.

I am using bases > 2, and exponent ranges up to 10,000,000.

Of course, there is no way for me to get through all of them in time periods less than years, but I did this for a reason.

I sieve to some arbitrary depth, let's call it 1T.

No reason to carry on much further for the first 100,000 exponents in the list, I am sure we can both agree.

So, I split the prime testing up on 5 cores, and core 6 sieves while these others churn away.

I usually reach a sieve depth of 10T on one core by the time the other 5 cores finish. Now I have what is a "great baseline" to use for the parallel sieving operation.

I use all 6 cores of machine #2 to do the prime testing for 100,000 < n < 500,000. And, again, recall my exponent base is >2, so the tests take longer than for base 2.

On machine #1 I engage 5 cores for parallel sieving and one core for the prime testing.

When this parallel sieving completes, I have sieved to a depth of 100T and searched all prime candidates up to 500,000. The very deep sieve usually means > 48 hours would be required to sieve just a single exponent if I were to use just one core, so there is no real need to sieve any longer.

At this point I have 12 cores at 5.0 GHz work on all of the parceled exponents n > 500,000 until "the sun burns out."

Should I have waited to reach 100T from the start and do no prime searching during that time, I would not have optimized the use of time best to my advantage.

At the risk of getting RDS to yell at me, can you supply me with an example of the problem you are working on?

And, by the way, we *do* have machines that are better at TF than at sieving...they are called GPUs.

[QUOTE=Christenson;283447]And, by the way, we *do* have machines that are better at TF than at sieving...they are called GPUs.[/QUOTE]

TF and sieving are (roughly) the same. I assume you meant "better at TF/sieving than testing". This is true, but the software to efficiently use GPUs does not currently exist for as wide a range of sieving problems as for CPUs. E.g. CPUs are still the best (AFAIK) for sieving [URL="http://www.mersenneforum.org/forumdisplay.php?f=81"]CRUS[/URL] work.

[QUOTE=Christenson;283447]At the risk of getting RDS to yell at me, can you supply me with an example of the problem you are working on?

And, by the way, we *do* have machines that are better at TF than at sieving...they are called GPUs.[/QUOTE]

Since you mention RDS, forget it. I want nothing to do with that arrogant SOB.

[QUOTE=SaneMur;283479]Since you mention RDS, forget it. I want nothing to do with that arrogant SOB.[/QUOTE]

I apologise...what I was trying to say was that I needed some help understanding *exactly* what you were asking...and wanted a simple example problem to help me. You are by no means alone in disliking RDS.

Mini-geek's comment tells me we have some work to do on the software front.

[QUOTE=SaneMur;283479]Since you mention RDS, forget it. I want nothing to do with that arrogant SOB.[/QUOTE]

It's better than being a total imbecile such as yourself.

I thought you didn't like throwing insults around...
but lets get this thread back on track. Math. Unfortunately, I am not well enough informed to be of any use there, but from now on, only those who can and [u]will[/u] help should be posting. I shall take my leave.

[QUOTE=Dubslow;283703]I thought you didn't like throwing insults around...
.[/QUOTE]

Consider what I did not do. I could have shredded the superficial effort
in post #1 in this thread. Instead, I said nothing. It was only after the
"arrogant SOB" comment that I responded.

And I notice that you said nothing about that insult. Yet another instance
of "double standard" in this forum. You only commented on [i]my response to an insult thrown at me[/i], rather than the [b]initial[/b] insult.

And of course, the moderators said nothing either. I suppose that calling
someone an SOB does not upset the harmony of the group as long as it
isn't me saying it.

[QUOTE=R.D. Silverman;283758]Consider what I did not do. I could have shredded the superficial effort
in post #1 in this thread. Instead, I said nothing. It was only after the
"arrogant SOB" comment that I responded.

And I notice that you said nothing about that insult. Yet another instance
of "double standard" in this forum. You only commented on [I]my response to an insult thrown at me[/I], rather than the [B]initial[/B] insult.

And of course, the moderators said nothing either. I suppose that calling
someone an SOB does not upset the harmony of the group as long as it
isn't me saying it.[/QUOTE]

Gee, I thought that was a compliment...

I, for one, simply had not seen SaneMur's posting containing the "SOB" remark. It easily qualifies as a personal insult so would have been subject to a moderator comment, if I had not banned SaneMur for spamming already. The "imbecile" likewise qualifies, but in this case the defense of having been provoked works in my book.

Spamming? Where?

SaneMur is an alt account of LiquidNitrogen. He kept posting links to his business and pictures of his products in spite of being asked repeatedly to stop. It was more plugs that outright ads, but spam just the same.

[QUOTE=R.D. Silverman;283687]It's better than being a total imbecile such as yourself.[/QUOTE]

Mr Silverman, I re-iterate my challenge to you to call no one a bad name, even if it is fully earned.

Is there a moderator willing to escrow the book, or do I need to raise the ante with a better book?

[QUOTE=Christenson;284315]Mr Silverman, I re-iterate my challenge to you to call no one a bad name, even if it is fully earned.

Is there a moderator willing to escrow the book, or do I need to raise the ante with a better book?[/QUOTE]

Allow me to quote cheesehead: [from the other thread]

"(That was no insult; that was an evaluation.) "

If it is OK for others to characterize their insults as "evaluations",
why should I not do the same? Why should there be a double standard?

Happy New Year
 

Can't say this thread has made for especially enjoyable seasonal reading.
Wish I could share a couple of agreeable and appropriate PMs with Richard, but by definition I won't. OTOH, @Richard: feel free to Carry On:smile:

David

Who's Richard?

[QUOTE=Dubslow;284330]Who's Richard?[/QUOTE]
[URL="http://www.youtube.com/watch?v=vG2O5dPEomA"]Hoped you'd ask that one[/URL]

David

Hint: I think his Mally number is two less than mine.

Hint 2): a process of elimination might help.

[QUOTE=R.D. Silverman;284321]Allow me to quote cheesehead: [from the other thread]

"(That was no insult; that was an evaluation.) "
[/QUOTE]

This is just a guess, but he (Richard) may have been referring to my "That's no lady, that's my wife" WC Fields(?) quote the other week. Or else he was simply agreeing with your assessment of SM88's undoubted mathematical talent.

[url=http://www.youtube.com/watch?v=f5M_Ttstbgs]Paranoia strikes deep[/url]

David

Brief Encounter
 

[QUOTE=Dubslow;284330]Who's Richard?[/QUOTE]
(Doing the Times crossword)
"It was Richard III who said "My Kingdom for a horse" wasn't it?"
"Yes Dear".
"Well I wish to blazes he hadn't. It spoils everything."

David

[QUOTE=Dubslow;284330]Who's Richard?[/QUOTE]My first name is Richard, and davieddy was referring to me.

There are several other Richards who post in this forum. At least three of them are professional mathematicians, so I (an amateur in that field) decided not to use my name prominently, in order to avoid confusion.

[QUOTE=R.D. Silverman;284321]Allow me to quote cheesehead: [from the other thread]

"(That was no insult; that was an evaluation.) "[/QUOTE]In the "RDS's unique pedagogic ways" thread, my "(That was no insult; that was an evaluation.)" post was intended as a humorous fiction.

As I have now explained on that thread,
[QUOTE=cheesehead;284428]To avert further misunderstanding:

That post of mine was intended as a humorous, fictitious [I]fake-attribution of thought to Mr. Silverman[/I]. (Yes, it's also an homage to W.C.Fields's "That was no lady; that was my wife'".)

In that context, "insult" referred to Mr. Silverman's statements that other posters characterized as insults, and "evaluation" was intended to be a fictitious correction/substitution for "insult" by Mr. Silverman.[/QUOTE]So, it is not correct to cite that as a sincere example of characterizing an insult as an evaluation.

[quote]If it is OK for others to characterize their insults as "evaluations",[/quote]No, Mr. Silverman, your misunderstanding (which may be due to my inadequate presentation) of my joke does NOT constitute any justification for you to say that it is OK for others to characterize their insults as "evaluations".

[quote]why should I not do the same? Why should there be a double standard?[/quote]Do you commonly base your standards on misunderstood jokes? You've cited no REAL instance of someone's characterizing an insult as an evaluation.

[QUOTE=cheesehead;284426]There are several other Richards who post in this forum. At least three of them are professional mathematicians[/QUOTE]
Who?

[QUOTE=Christenson]
Mr Silverman, I re-iterate my challenge to you to call no one a bad name, even if it is fully earned.

Is there a moderator willing to escrow the book, or do I need to raise the ante with a better book?
[/QUOTE]

[QUOTE=R.D. Silverman;284321]Allow me to quote cheesehead: [from the other thread]

"(That was no insult; that was an evaluation.) "

If it is OK for others to characterize their insults as "evaluations",
why should I not do the same? Why should there be a double standard?[/QUOTE]

My CHALLENGE to you (pull the heat out of your language and teach someone some math they wouldn't learn any other way) is not a double standard...it is intended as a prize (my copy of "Counterexamples in Topology") for YOU doing BETTER than you have done before, and certainly better than you have to do to stay on the forum. The moderator is simply intended as an independent judge, to hold my bond of sincerity and keep me honest.

You have unique capabilities, I want see you to rise to the occasion and put your past and its injustices behind you.

*******
So much for my example in detail...OP has got himself banned, all by himself.
[url]http://mersenneforum.org/showpost.php?p=283842&postcount=3[/url]

[QUOTE=axn;284435]Who?[/QUOTE]
Dunno.
But when I was teaching at St Paul's, there were always 3 and latterly 4 "Davids" in a department of six. It helped clarifying the one you were referring to if you were one of them. I think there were nine in total on the staff. Only one of us was "Dave". That was Rollit (England rugby player).
Frequently met him in the changing room. I was talking about changing my first son's nappies.
"Wait till he's about 8 months - that's when the shit starts to smell."

David

Name confusion.
 

My best friend at Oxford was Paul (Seymour).
My younger son is Tom. (Known universally at Oundle as Teddy)
When I told my good teacher/musico friend Russ we proposed to call our first boy "Mark Angwin Eddy" he simply said Hmm. Think of the initials.
Should be OK as long as he doesn't go around saying "Is that a gun in your pocket or are you just pleased to see me?"

Witty or what?

David

Fats Domino
 

[QUOTE=Christenson;284436]OP has got himself banned, all by himself.
[/QUOTE]

How come I can't find his version of "All By Myself" on U-tube ATM?
Is everybody at it?

David

[url=http://www.youtube.com/watch?v=Lj35qMRz9rU&feature=related]I guess we'll settle for this[/url]
30+ years since I last heard it.
Blows my mind.