mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-12-03, 19:55   #1
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default 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
davieddy is offline   Reply With Quote
Old 2010-12-03, 20:47   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by davieddy View Post
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.
science_man_88 is offline   Reply With Quote
Old 2010-12-03, 21:05   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22·32·163 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-03, 21:05   #4
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

647410 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
davieddy is offline   Reply With Quote
Old 2010-12-03, 21:09   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
davieddy is offline   Reply With Quote
Old 2010-12-03, 21:11   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×32×163 Posts
Default

Quote:
Originally Posted by davieddy View Post
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!
CRGreathouse is offline   Reply With Quote
Old 2010-12-03, 22:04   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
davieddy is offline   Reply With Quote
Old 2010-12-03, 23:05   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts
Default

Are you satisfied with '_88's and Charles's mathsiness?

Last fiddled with by cheesehead on 2010-12-03 at 23:07
cheesehead is offline   Reply With Quote
Old 2010-12-03, 23:26   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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.
science_man_88 is offline   Reply With Quote
Old 2010-12-03, 23:36   #10
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001010010102 Posts
Default

Quote:
Originally Posted by cheesehead View Post
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
davieddy is offline   Reply With Quote
Old 2010-12-04, 00:36   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

11001010010102 Posts
Default 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
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECM level program henryzz GMP-ECM 8 2012-09-15 17:00
Nvidia GPU driver level Chuck GPU Computing 11 2012-08-17 20:27
any mid -level sequence left? firejuggler Aliquot Sequences 5 2012-02-09 11:02
Probability of TF per bit level James Heinrich PrimeNet 11 2011-01-26 20:07
Changing priority level Unregistered Information & Answers 12 2009-04-13 12:14

All times are UTC. The time now is 18:51.

Tue Aug 11 18:51:33 UTC 2020 up 25 days, 14:38, 2 users, load averages: 1.37, 1.65, 1.66

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.