Register to reply

(Potential massive search-space) Is this an exponential problem?

by htyj6g9jv1ev6
Tags: exponent, exponential, massive, potential, searchspace
Share this thread:
htyj6g9jv1ev6
#1
Mar19-14, 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:
  1. There is a journey consisting of 256 steps
  2. The person, can either i) walk, or ii) hop
  3. The person can choose what to do at each step
  4. I want to compute a list of all possible journey

I'm wondering if my attempt is futile.... As the search-space 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!
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
craigi
#2
Mar19-14, 04:25 PM
P: 421
Quote Quote by htyj6g9jv1ev6 View Post
I'm writing a piece of software, however, my math skills are VERY rusty at the moment.

The problem is as follows:
  1. There is a journey consisting of 256 steps
  2. The person, can either i) walk, or ii) hop
  3. The person can choose what to do at each step
  4. I want to compute a list of all possible journey

I'm wondering if my attempt is futile.... As the search-space 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!
The answer is simply 2^256.

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^256-1 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 built-in types, but you can handle this easily with nested loops. For 32-bit precision, you'll need 8 nested loops, then just write out the counters in 32-bit 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