6

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.

Jack Wilson
  • 71
  • 1
  • 1
  • 3
  • @Jack Wilson hacking much? – P.Brian.Mackey May 16 '11 at 19:44
  • 8
    "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
  • 2
    @Jeffrey Can you freeze it first? Can you wrap it in a balloon? Can the tree be horizontal? And so on... – Gary May 16 '11 at 21:42
  • Your professor was indeed correct. It currently is not possible or at least not feasable ( I often treat that description the same ). If something take an unreasonable amount of time to calculate then its either the wrong approach or its not feasable to do. – Ramhound May 17 '11 at 11:51
  • Hmm. Supposing this is feasible/possible, the real Q is: would it be feasible/possible to write a program to take this giant data set and verify that it was correct (all unique, all there)? :-p – James May 17 '11 at 11:56
  • 1
    @James: First, you sort the list, then you traverse it. It's a mere `O(n log n)` issue, where n (according to raybritton's comment) is about 2.2E57. It might be possible to do it, using the entire resources of a large cluster of galaxies. – David Thornley May 17 '11 at 16:59
  • It would take 0 time and 0 storage. Every possible combination already exists. If I tell you I already succeeded, how would you prove me wrong? – Kevin Hsu May 17 '11 at 18:41
  • 1
    Just use threads. Everyone knows that threads speed stuff up ;-) – Karl Bielefeldt Dec 15 '11 at 06:55

7 Answers7

12

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, so for this example, we'll take 100 million seconds as 3 years to make the math easy.

So that leaves us with 10 to the 17th seconds being divided by 10 to the 8th seconds per 3 years. That means it will take more than 3 billion years for this computation to complete. Check that against the estimated time we have left before our sun becomes a red giant, that's just 5 billion years....

Community
  • 1
Peter Smith
  • 2,587
  • 19
  • 21
  • 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
  • 6
    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
  • 3
    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
  • 5
    @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
5

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

jzd
  • 4,166
  • 25
  • 28
4

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.
F'x
  • 269
  • 2
  • 9
3

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.

Kevin Hsu
  • 1,613
  • 10
  • 11
  • 2
    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
  • Right. Generating the sequence as an Iterator is fast. Iterating thru the sequence up to the end, THAT is slow. And ... well ... stupid. – Florian F Sep 22 '14 at 15:24
2

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.

Steven Jeuris
  • 5,804
  • 1
  • 30
  • 52
0

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.

GrandmasterB
  • 37,990
  • 7
  • 78
  • 131
-2

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 ;)

Gurgeh
  • 97