## 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.

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

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.

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.

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

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

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?

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.

True.

Not catching exceptions is major trouble there...

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.

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.

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

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.

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.

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