Band limit increase

Case number:699969-989788
Topic:General
Opened by:cjmarsh
Status:Open
Type:Question
Opened on:Monday, May 30, 2011 - 02:26
Last modified:Friday, December 5, 2014 - 23:04

I generally crash the client when trying to attach bands between all the segments. If you could increase the max band count to get_segment_count!(factorial) that would most likely fix it, thanks.

(Mon, 05/30/2011 - 02:26  |  14 comments)


Joined: 12/27/2010
Groups: None

and then get google to lend you their computers to process it...

cjmarsh's picture
User offline. Last seen 2 years 25 weeks ago. Offline
Joined: 05/21/2011
Groups: Go Science

...or I could just do it on my own? I don't get it.

Joined: 12/27/2010
Groups: None

Sorry, I was just suggesting that if you had a reasonably large puzzle of 200 segments then 200! bands would require more computing power than the average desktop computer by many orders of magnitude. But I may be wrong.

cjmarsh's picture
User offline. Last seen 2 years 25 weeks ago. Offline
Joined: 05/21/2011
Groups: Go Science

10^200 can easily be parsed from bit arrays shorter than these sentences. Using them, we can just wiggle and shake each to find the best score.

Joined: 12/27/2010
Groups: None

I thought 10^200 was more than the number of atoms in the universe!

cjmarsh's picture
User offline. Last seen 2 years 25 weeks ago. Offline
Joined: 05/21/2011
Groups: Go Science

well if you treat each bit in an array as a series of switches (which they are in the processor) then the total number of possibilities is 2^2^2^2^2^2... etc. for the number of bits used

that means the exponent is exponential

jflat06's picture
User offline. Last seen 14 min 55 sec ago. Offline
Joined: 09/29/2010
Groups: Window Group
Status: Open » Closed

I'm not sure I understand the process which you are describing, but at the very least, a limit on the number of bands of segments! is not useful. Once you get to that point, you may as well make it unbounded.

(For example, the following is 200!)
7886578673 6479050355
2363213932 1850622951
3597768717 3263294742
5332443594 4996340334
2920304284 0119846239
0417721213 8919638830
2576427902 4263710506
1926624952 8299311134
6285727076 3317237396
9889439224 4562145166
4240254033 2918641312
2742829485 3277524242
4075739032 4032125740
5579568660 2260319041
7032406235 1700858796
1789222227 8962370389
7374720000 0000000000
0000000000 0000000000
0000000000 00000

This many bands is impossible on any hardware that is, or ever will be available.

If your client is crashing, it is probably because your computer and/or the foldit program isn't capable of handling the number of bands you're trying to throw at it.

The process you're describing sounds suspiciously like a brute-force solution. These solutions generally aren't feasible in most practical situations (i.e., any of the puzzles we are working on). Thus, we aren't really interested in making the client capable of supporting them.

Also, bands between every segments is on the order of (segements)^2, not (segments)!. Is this what you meant?

infjamc's picture
User offline. Last seen 2 years 45 weeks ago. Offline
Joined: 02/20/2009
Groups: Contenders

It would be nice to have the program refuse to proceed if it determines that there isn't enough memory to band between every nth residue (and instead respond with an error message). At the very least, this would prevent the abnormal termination of the program, which comes with the side effect of killing the undo graph.

Joined: 06/17/2010

True.
Not catching exceptions is major trouble there...

cjmarsh's picture
User offline. Last seen 2 years 25 weeks ago. Offline
Joined: 05/21/2011
Groups: Go Science

Well, I have to say there would be problems trying to encode numbers that large in traditional computing methods, however, it most certainly is possible to do so. Basically, the only fallacy in your logic comes from assuming that arbitrarily large is the same as infinite (or large = unbounded). This is provably untrue, hence the p=np 'proof'. As to what was meant about the technique described, allow me to explain further...

Imagine the integer you are working with as a description of one of the numbers in 10^200 (total possibilities). Essentially, every digit is a switch that determines the *direction* of Xeno's paradox within the scope of the total possibilities. To use a simple, concrete example:

Indexing number (i.e. Godel number): 01100010
This means:
switch 0 -> switch 1 -> switch 1 -> switch 0 -> switch 0 -> switch 0 -> switch 1 -> switch 0
which is equivalent to...
0 + log_2(log_2 n ) + log_2(log_2(log_2 n )) + 0 + 0 + 0 + log_2(log_2(log_2(log_2(log_2(log_2(log_2 n ))))))
where n = 2^2^2^2^2^2^2^2 = (about) 1.16 * 10^77
this implies the above 8-bit sequence can represent the number 2^2^2^2^2^2 + 2^2^2^2^2 + 2 = 18446744073709551616 + 4294967296 + 2 = 18446744078004518914 or 1.84 * 10^19

Now take any bit lengths larger than 8 and you can easily store the information about large numbers in such a way. Also, having a discrete limit to the number of bands would certainly be helpful, no matter what it may be, because that exact number can just be processed cyclically throughout the protein and encoded into the information required within a recipe. Hopefully that clears it up a bit, if not let me know.

jflat06's picture
User offline. Last seen 14 min 55 sec ago. Offline
Joined: 09/29/2010
Groups: Window Group

It is trivially true that you can encode numbers as big as

7886578673 6479050355
2363213932 1850622951
3597768717 3263294742
5332443594 4996340334
2920304284 0119846239
0417721213 8919638830
2576427902 4263710506
1926624952 8299311134
6285727076 3317237396
9889439224 4562145166
4240254033 2918641312
2742829485 3277524242
4075739032 4032125740
5579568660 2260319041
7032406235 1700858796
1789222227 8962370389
7374720000 0000000000
0000000000 0000000000
0000000000 00000

In fact, I just did so by writing it. However, there is a big difference between "encoding" and actually instantiating any sort of object that many times.

I never made the argument that arbitrarily large is equal to unbounded. I said that establishing a limit on that order of magnitude is not useful because you will never reach that limit in practicality. You can reason about numbers that large, but computers will never come to the point of being able instantiate anything on that order of magnitude, so it's irrelevant.

cjmarsh's picture
User offline. Last seen 2 years 25 weeks ago. Offline
Joined: 05/21/2011
Groups: Go Science

The idea is you don't have to instantiate the object. The number is a pointer to the object.

Joined: 12/03/2014
Groups: None
Status: Closed » Open
Type: Bug » Question

I know this is an old topic, but I need some clarification because my math must be getting rusty or something. Why exactly would it be factorial again? Why is this different from a number-of-handshakes problem? In that case only 20100 bands would be required for 200 segments. It sounds like you guys know what you're talking about, though, so I'm probably wrong but I'm honestly lost. It still would be great if someone could give me some explanation.

jeff101's picture
User offline. Last seen 1 day 1 hour ago. Offline
Joined: 04/20/2012
Groups: Go Science

I you have N residues/segments/amino-acids and want all possible pairs of alpha-carbons to be banded together, you would need (N^2-N)/2=N(N-1)/2 bands:

For N=200, this gives 200(199)/2=19900 bands.
For N=100, this gives 100(99)/2=4950 bands.
For N=50, this gives 50(49)/2=1225 bands.

It would probably be more effective to use zero-length bands to position each alpha-carbon where you want it. For N residues, this would require just N bands.

See the recipe for bandsome (https://fold.it/portal/recipe/43861) for things you can do with less bands.

Sitemap

Developed by: UW Center for Game Science, UW Institute for Protein Design, Northeastern University, Vanderbilt University Meiler Lab, UC Davis
Supported by: DARPA, NSF, NIH, HHMI, Amazon, Microsoft, Adobe, RosettaCommons