20101203, 19:55  #1 
"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 20101203 at 20:02 
20101203, 20:47  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20101203, 21:05  #3 
Aug 2006
1011011100110_{2} 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 (n1) 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. 
20101203, 21:05  #4 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 

20101203, 21:09  #5  
"Lucan"
Dec 2006
England
14512_{8} Posts 
Quote:
David 

20101203, 21:11  #6 
Aug 2006
2×3×977 Posts 
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!

20101203, 22:04  #7  
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Quote:
If so it may have to wait until the morning: "When I'll be sober" (Winston Churchill) Whale meet again.... David 

20101203, 23:05  #8 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Are you satisfied with '_88's and Charles's mathsiness?
Last fiddled with by cheesehead on 20101203 at 23:07 
20101203, 23:26  #9 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20101203, 23:36  #10 
"Lucan"
Dec 2006
England
6474_{10} Posts 
Last fiddled with by davieddy on 20101203 at 23:36 
20101204, 00:36  #11 
"Lucan"
Dec 2006
England
194A_{16} 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 mindboggling. 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
ECM level program  henryzz  GMPECM  8  20120915 17:00 
Nvidia GPU driver level  Chuck  GPU Computing  11  20120817 20:27 
any mid level sequence left?  firejuggler  Aliquot Sequences  5  20120209 11:02 
Probability of TF per bit level  James Heinrich  PrimeNet  11  20110126 20:07 
Changing priority level  Unregistered  Information & Answers  12  20090413 12:14 