mersenneforum.org TF bit level
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-03, 19:55 #1 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts TF bit level Let's try a mathsy puzzle for a change As explained clearly on the Math page, faced with the question(Q) "is it worth TFing to one more bit?" the answer is yes iff (time to TF) < (time for 2 LLtests)*(probability of finding a factor). This gives a definite answer, provided the times involved are in a fixed ratio(R). Now suppose we have two types of processor, for which this ratio(R) is different. Can we formulate a problem s.t. we can find a yes/no answer to the question(Q)? David Last fiddled with by davieddy on 2010-12-03 at 20:02
2010-12-03, 20:47   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by davieddy Let's try a mathsy puzzle for a change As explained clearly on the Math page, faced with the question(Q) "is it worth TFing to one more bit?" the answer is yes iff (time to TF) < (time for 2 LLtests)*(probability of finding a factor). This gives a definite answer, provided the times involved are in a fixed ratio(R). Now suppose we have two types of processor, for which this ratio(R) is different. Can we formulate a problem s.t. we can find a yes/no answer to the question(Q)? David
R2/R1 = ((time to TF) < (time for 2 LLtests))2/((time to TF) < (time for 2 LLtests))1 assuming the probability of finding a factor doesn't change.

 2010-12-03, 21:05 #3 CRGreathouse     Aug 2006 175B16 Posts I suppose that depends on what other work could be done by those processor types. For each block of computers (n = 2 in your case), find the amount of work they can do in a unit of time on LL and how much they can do on trial factoring. (You can choose one block to have unit work for both.) Order the blocks from "best at TF" to "worst at TF" in terms of ratio (TF work)/(LL work), or infinity if TF work > 0 and LL work = 0. Go through each of these scenarios: 1. Assign all blocks except the block best (block 1) at TF to LL work, then set that block to do as much TF as reasonable. 2. Assign block 1 to do all TF and blocks >= 3 to do all LL. Set block 2 to do as much TF as reasonable. ... n. Assign blocks 1 through (n-1) do do TF, then block n to do as much TF as reasonable. In each of these cases the "reasonable" amount is: A. For each block devoted entirely to TF, add up the amount of TF work; call this T. B. For each block devoted entirely to LL work, add up the amount and call it L. C. Call the current block's TF and LL amounts t and l, respectively. D. Find the factoring depth for which t = 2l for the current block. If this depth is feasible (requiring between T and T + t units of time to do L work) then this is the optimal level; otherwise continue. If in your case the "fast at TF" processors are rare, this suggests using the old ration (the one for the "slow at TF" processors) until the "fast at TF" processors can do all the TF.
2010-12-03, 21:05   #4
davieddy

"Lucan"
Dec 2006
England

145128 Posts

Quote:
 Originally Posted by science_man_88 R2/R1 = ((time to TF) < (time for 2 LLtests))2/((time to TF) < (time for 2 LLtests))1 assuming the probability of finding a factor doesn't change.
My initial reaction is "Did you audition for Monty Python?"

David

2010-12-03, 21:09   #5
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by CRGreathouse I suppose that depends on what other work could be done by those processor types. For each block of computers (n = 2 in your case), find the amount of work they can do in a unit of time on LL and how much they can do on trial factoring. (You can choose one block to have unit work for both.) Order the blocks from "best at TF" to "worst at TF" in terms of ratio (TF work)/(LL work), or infinity if TF work > 0 and LL work = 0. Go through each of these scenarios: 1. Assign all blocks except the block best (block 1) at TF to LL work, then set that block to do as much TF as reasonable. 2. Assign block 1 to do all TF and blocks >= 3 to do all LL. Set block 2 to do as much TF as reasonable. ... n. Assign blocks 1 through (n-1) do do TF, then block n to do as much TF as reasonable. In each of these cases the "reasonable" amount is: A. For each block devoted entirely to TF, add up the amount of TF work; call this T. B. For each block devoted entirely to LL work, add up the amount and call it L. C. Call the current block's TF and LL amounts t and l, respectively. D. Find the factoring depth for which t = 2l for the current block. If this depth is feasible (requiring between T and T + t units of time to do L work) then this is the optimal level; otherwise continue. If in your case the "fast at TF" processors are rare, this suggests using the old ration (the one for the "slow at TF" processors) until the "fast at TF" processors can do all the TF.
I'll take that as a "no" Charles

David

2010-12-03, 21:11   #6
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by davieddy I'll take that as a "no" Charles
It's actually a "yes"; see esp. the last line. In general the problem takes N steps if there are N types of processor, I think. Actually, come to think of it, you could do a binary search, so that's lg N + O(1) steps. How about that!

2010-12-03, 22:04   #7
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 Originally Posted by CRGreathouse If in your case the "fast at TF" processors are rare, this suggests using the old ration (the one for the "slow at TF" processors) until the "fast at TF" processors can do all the TF.
Is this "the last line"?

If so it may have to wait until the morning:
"When I'll be sober" (Winston Churchill)

Whale meet again....

David

 2010-12-03, 23:05 #8 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts Are you satisfied with '_88's and Charles's mathsiness? Last fiddled with by cheesehead on 2010-12-03 at 23:07
2010-12-03, 23:26   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by cheesehead Are you satisfied with '_88's and Charles's mathsiness?
what mathiness do I have? I used logic that if probability was constant the others needed to change to change the ratio kinda simple lol.

2010-12-03, 23:36   #10
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by cheesehead Are you satisfied with '_88's and Charles's mathsiness?
Just can't be satified

Last fiddled with by davieddy on 2010-12-03 at 23:36

 2010-12-04, 00:36 #11 davieddy     "Lucan" Dec 2006 England 2·3·13·83 Posts I think what I was getting at was... When everything was done on some x86 or clone/derivative, the answer was simple. The number of complicating questions is now mind-boggling. Perhaps the Indians or Chinese might catch the Mersenne bug? Or would that be like expecting England to host the world cup before 2030? David

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz GMP-ECM 8 2012-09-15 17:00 Chuck GPU Computing 11 2012-08-17 20:27 firejuggler Aliquot Sequences 5 2012-02-09 11:02 James Heinrich PrimeNet 11 2011-01-26 20:07 Unregistered Information & Answers 12 2009-04-13 12:14

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

Wed Jan 19 22:07:33 UTC 2022 up 180 days, 16:36, 0 users, load averages: 1.63, 1.72, 1.69