Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is it possible to generate every possible combination of a 32 character alpha numeric string? If so, how long would it take on today's fast computers?

My lecturer at university said it's impossible, and I thought "nothing is impossible".

Any ideas on how long it'd take and how it'd be done? We're using Java at the moment. I would like to think I can prove him wrong.

share|improve this question
    
@Jack Wilson hacking much? –  P.Brian.Mackey May 16 '11 at 19:44
3  
"Anyone who says 'nothing is impossible' has obviously never tried to staple jello to a tree" –  Jeffrey May 16 '11 at 19:49
    
2,272,657,884,496,751,500,000,000,000,000,000,000,000,000,000,000,000,000,000 correct number of combinations? –  Ray Britton May 16 '11 at 19:49
    
I generally figure "will take more than the Sun's entire energy output until it goes dark on a minimum-energy non-reversible computer" as "impossible". Things like counting to 2^128, for example. If you're willing to add enough more stars for power, it may become possible, but I'll leave the technical issues for others. –  David Thornley May 16 '11 at 19:55
1  
@Jeffrey Can you freeze it first? Can you wrap it in a balloon? Can the tree be horizontal? And so on... –  Gary Rowe May 16 '11 at 21:42
show 5 more comments

8 Answers

up vote 9 down vote accepted

It boils down to the math, even if you take pretty crazy values.

Let's say you have an instruction that can generate one 32 character combination in one cycle. Also, you're not storing these combinations so there is virtually no memory access. Finally let's assume that your effective clock speed for these instructions is 2.0 petahertz (ten to the fifteenth cycles per second), which doesn't exist yet outside of the fastest supercomputers on the planet.

The number of 32 character combinations that are alphanumeric with repetition is 36 to the 32nd power. So, 10 to the 32nd power is a much smaller lower bound on this value. To compute this smaller group, you will need 10 to the 17th seconds (combinations / clock speed). There's approximately 32 million seconds in a year, but for this example, we'll take 100 million seconds in a year to make the math easy.

So that leaves us with 10 to the 17th seconds being divided by 10 to the 8th seconds. That means it will take more than 1 billion years for this computation to complete. If you do the math exactly, you'll find that this takes longer than the estimated time we have left before our sun becomes a red giant (5 billion years).

share|improve this answer
    
Forgot to add upper and lowercase. But, even from the example you gave it looks like a waste of time attempting it. Thanks. –  Jack Wilson May 16 '11 at 19:45
5  
Of course, if you divided the work between 1 billion computers, it won't be so bad. Assuming that this task can be split into independent parallel chunks of work.... ;) –  FrustratedWithFormsDesigner May 16 '11 at 19:45
2  
Your math is assuming that your combinations are case insensitive and is only the English version of the Western Latin Alphabet is being used. This results in 36^32, IF we make it case sensitive we end up with 62^32 ~ 2.272 x 10^57 permutations. AND if we add in the complete set of Unicode AlphaNumeric characters, Then I would guess that the heat death of the universe will occur before complementation of the routine. –  mangelo May 16 '11 at 19:51
3  
@mangelo: Or... you will just need MORE than a billion computers working in parallel. ;) –  FrustratedWithFormsDesigner May 16 '11 at 19:59
    
@FrustratedWithFormsDesigner The beauty is that this can actually be done but you would need TONS of PCs :) –  Rig Dec 14 '11 at 21:54
add comment

I would suggest trying to generate the first 10000 combinations and measure how long that takes in Java.

Then as a rough estimate compute time needed per combination in your sample size and multiple that times the total number of combinations that are possible. (Maybe even do the math first to determine how many combinations there are because that is the real issue).

share|improve this answer
1  
Oh but everyone knows Java is slow... :-) –  Dan Ray Dec 14 '11 at 20:23
add comment

This kind of question shows a very good way to exercise yourself with estimates and orders of magnitude. In all scientific and technical fields, this is a great asset. In fact, it is the number one thing I expect from the people I hire: being able to make educated guesses when no hard data is available.

So, let's get it started:

  • You have a 4 GHz CPU; this means, it does something  4 109 times per second.
  • Now, this something isn't a simple addition, as the processor might perform more than one operation per cycle (for example, think “vectorization”). So, we'll be very generous (after, we want a lower bound on the execution time), and assume that you can iterate (i.e. generate one permutation from another) in one cycle.
  • With lowercase/uppercase, you have 62 alphanumerical characters, so 6232 combinations. Let's, again, be optimistic and say your teacher was talking about all-uppercase: 3632 = 6.3 1049.
  • You divide this by 4 109, and you get roughly 1.5 1040 seconds, which is 5 1032 years, which is… too much.
share|improve this answer
add comment

Given that there are 62 alphanumeric characters, the amount of possible combinations equals 62^32 = 2.27e+57. Also known as .. huge!

Fun facts: storing this using 8 bits per character would take up 1792810956021776957992730108.0124 Geopbytes

As jzd states, try benchmarking the time it takes to generate a certain amount of them. From this you can calculate an average time per combination, multiply this with the amount of possible combinations and you'll have the time required.

share|improve this answer
add comment

You don't need to generate every possible string - it already exists. If you're searching for a particular string, you don't need to search. It exists. If you want to store it, it's already stored - it takes 0 bytes to store and 0 time to fetch.

In other words, the result already exists and is cached in the fabric of reality, so generating the result is actually the fastest operation possible.

It's a bit like asking someone to write a sort algorithm that sorts all integers from 1 to 1000, given that every one is unique. You don't need to sort at all.

share|improve this answer
    
This is a great comment, but has the unfortunate side effect that I am now looking to use the phrase "the result is cached in the fabric of reality" when trying to explain to someone why I don't need to do any work :) –  nlawalker Dec 14 '11 at 19:22
    
Heh, I suppose I will start to use that more myself! :D –  Kevin Hsu Dec 14 '11 at 19:51
add comment

Of course its possible. Or is your lecturer suggesting there's some letter/number combination that cant be represented in a 32 character string?

is it Feasable... now thats an entirely different question. If you were able to harness most of the machines on the internet, you could probably do it in a time span small enough that the end result was still relevant.

share|improve this answer
add comment

If we think outside the box for a while, this sort of combinatorial explosion is what quantum computers are good at. If you have 64 symbols (6 bits) and a string length of 32, you would need a 6*32=192 bit quantum computer to solve it "instantly", depending on what you actually want to do with the strings - are you searching for one with a hash that matches a given hash value?

Incidentally, starting just a few days ago, you can order a 128-bit quantum computer from D-wave (hotly contested if it really is quantum computation, though). That is still not enough, since you lack 64 bits, which means that you would need to run your algorithm 2**64 times, which is still waaay too much.

192 bits will probably come along sooner or later though. Then you'll be able to show him ;)

share|improve this answer
add comment

I dont know why you guys are focusing on just CPUs.

GPUs + CPUs would be the way to calculate this.

Many brute force wireless cracking algorithms are 100x faster on a GPU.

share|improve this answer
1  
Do you really think a factor 100 or even 1 million matters? –  AProgrammer Dec 14 '11 at 10:40
1  
@Fio - Because its still going to take your entire lifespan to calculate every combination of a 32 character alphanumeric string. Were talking the sun will burn out before you finish type of thing. –  Ramhound Dec 14 '11 at 12:40
1  
Hi Fio, welcome to Programmers! Can you explain a little more about why you believe this is the right answer, for those of us who are't familiar with it? –  user8 Dec 14 '11 at 18:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.