Register to reply 
(Potential massive searchspace) Is this an exponential problem? 
Share this thread: 
#1
Mar1914, 04:15 PM

P: 5

I'm writing a piece of software, however, my math skills are VERY rusty at the moment.
The problem is as follows:
I'm wondering if my attempt is futile.... As the searchspace may be too huge if this problem is indeed exponential. My specific question is, how many ways are there through this journey? How many combinations of "walk" and "hop"? I'm hoping that I'm wrong and the answer is not 2^256 (or around that area...). Otherwise I will have to abandon my simplistic brute force algorithm :D Thank you! 


#2
Mar1914, 04:25 PM

P: 421

Test it out for smaller steps sizes. 2^1 = 2: 0,1 2^2 = 4: 00,01,10,11 2^3 = 8: 000,001,010,011,100,101,110,111 0 corresponding to walk 1 corresponding to hop If you want to write your algorithm, it's incredibly easy. Just count from 0 to 2^2561 writing out the number in 256 digit binary at each iteration. You'll need storage for 256 bits of precision, so you're not going to be able to rely on the builtin types, but you can handle this easily with nested loops. For 32bit precision, you'll need 8 nested loops, then just write out the counters in 32bit binary, in order. The cool thing about this is that the order that the paths come out in, means that the early ones are valid for smaller step sizes too, so you can see where your computer stops making progress. Was there a particular reason why you needed 256 steps? Also is there a particular reason that you need a list of them? 


Register to reply 
Related Discussions  
Exponential potential for inflation  Cosmology  3  
Wave funtions for a massive particle moving in 1D harmonic oscillating potential  Quantum Physics  2  
Is curved space cancelled between two massive bodies?  Special & General Relativity  6  
Do massive objects in space act as gyroscopes?  Astronomy & Astrophysics  5  
Veil Lifts on Massive Stars' Birth; Space.com  Astronomy & Astrophysics  0 