Brute Force Issue(For password recovery)
hi guys........
i'm working on a brute force program which as u all must be knowing uses massive recursion(without multithreading, lots of painting etc) . i thought that because of the very architechture of java, it might take longer than any native windows programming language and so also developed it in VB. BUT to my sheer surprise i see that to create all possible combinations of 10 letters, java takes 33 secs while VB takes 150 secs(approx). i suppose generating windows executable on the fly should obviously take longer. any ideas how this is vice versa?
also , how much time shld a decent brute force algorithm take to create a unique combination of 10 letters (where a letter doesn't repeat itself again in that word).
Thanks in advance
[776 byte] By [
BCAa] at [2007-9-28 8:44:02]
Assuming monocase, no repetitions, that yields:
26*25*24*23*22*21*20*19*18*17 = 19,275,223,968,000 combinations.
Or roughly 584,097,696,000 per second (if you're done in 33 seconds).
Even if you somehow figured out a way to make 1 word per clock cycle, that would imply you have a 584GHz machine.
Assuming mixed-case, the algorithm should take roughly 5000 times longer.
Let's see your algorithm, cuz I think there's a problem.
all possible combination out of given 10 letters or out of the whole 26 letters in the alphabet?that makes a huge difference
Oh, sorry, did I misread it? Are you pre-selecting 10 letters and then creating all combinations? Or do you mean that you are creating words that are ten characters in length, where each character is a unique letter?
BOTHpre selected 10 letters and then creating all possible combinations of it, where in any combination formed, no letter repeats itself.
BCAa at 2007-7-9 20:34:25 >
> Even if you somehow figured out a way to make 1 word> per clock cycle, that would imply you have a 584GHz> machine.I'll take 2 of those please :-)
Well if you just get the combinations of 10 preselected letters then it's only 3,628,800 Possibilities, which would be 109,964 per second at 33 seconds unless my math is wrong.
this is all getting MESSED up ... all i want to know is answer to a VERY VERY SIMPLE question. how much time would the most efficient algorithm in this world take to create a unique combination of 10 preselected letters ,where ,in any combination no letter occurs more than once.
could u guys be a little precise
BCAa at 2007-7-9 20:34:25 >
how much time would the most efficient algorithm in this world take to create a unique combination of 10 preselected letters
...
could u guys be a little precise
Ok, let's be precise.
This problem can be easily broken into a parallell task, a nice candidate for a quantum computer. Now since we are not acutally computing anything per se, but rather representing a set of states, we are already done. This is because the particles already exist in a state of superposition. All you need to do is define the mappings.
Thus the answer to your question is zero.
> the most efficient algorithm in this world
10 is quite a small case, so you might not want the most efficient algorithm - it could have a large constant hidden in the big-O notation.
I must note, however, that in my experience the simple recursive method for getting all permutations of a set is about half as fast as an algorithm called Plain Bob. Here's an implementation I wrote a couple of years back after spending an afternoon in the library with a book on campanology: public class PlainBob
{
public int[] combo;
public int n;
private boolean flag;
private int lb,ub;
PlainBob(int n)
{
combo = new int[n];
for(int i=0; i<n; i++)
{combo[i]=i;}
flag = false;
this.n = n;
}
public void advance() throws FinishedException
{
if (flag)
{
lb = 2;
ub = 2 *( (n-1) / 2 );
if (combo[0]==0) bob();
}
else
{
lb = 1;
ub = 2 * (n/2) - 1;
}
if (lb==n) throw new FinishedException("Permutation finished");
flag = !flag;
for(int sw=lb; sw><=ub; sw+=2)
{swap(sw,sw+1);}
}
private void bob()
{
for (int a=n; a>0; a--)
{if (combo[a-1]!=(a-1)) lb = a+1;}
ub = n-1;
if ((n-lb)%2 == 0)
{ub--;}
}
private void swap(int x, int y)
{
try
{
int t=combo[x-1];
combo[x-1]=combo[y-1];
combo[y-1]=t;
}
catch (ArrayIndexOutOfBoundsException e)
{
System.err.println("swap ("+x+","+y+")");
System.exit(3);
}
}
}
"10 is quite a small case, so you might not want the most efficient algorithm - it could have a large constant hidden in the big-O notation."
Well then let's make it 15 letters. what i actually want to know is that, Is there any scope for me to make my algorithm better, and i'm dead sure that there must be some benchmarks set for such a process as the effeciency cannot go beyond a certain limit.
i have too little patience to go thru u'r program . can u specify the overall blueprint of u'r algorithm...
Thanks in advance.
BCAa at 2007-7-9 20:34:25 >
> can u specify the overall blueprint of u'r algorithm...
Not really. As I said, it's based on a book on bell-ringing. I generalised the algorithms I found there for ringing changes on 4-8 bells, but I can't explain it. I'm just confident it works (i.e. not even a formal proof - *blush*).
The absolute lower limit would have to be n! You can't go faster than at one iteration per permutation.
Sure. However, you try to get a small multiplicative constant on that n! (And naive implementations of the standard recursive technique will give you n^n instead - complexity theorists may regard that as equivalent to n!, but for practical purposes...)
The best background explanation of your Plain Bob algorithm that I was able to find is http://www.maths.mq.edu.au/~chris/math337/chap02.pdf ...
> Sure. However, you try to get a small multiplicative
> constant on that n!
Of course. I was just answering his question. Your previous response was quite useful but he persisted in asking for the benchmark. You can't hope to do better than n! Now, he may have been looking for something a little more pragmatic but this is a free service.
> (And naive implementations of the
> standard recursive technique will give you n^n instead
> - complexity theorists may regard that as equivalent
> to n!, but for practical purposes...)
Those crazy complexity theorists.
> this is all getting MESSED up ... all i want to know
> is answer to a VERY VERY SIMPLE question. how much
> time would the most efficient algorithm in this world
> take to create a unique combination of 10 preselected
> letters ,where ,in any combination no letter occurs
> more than once.
>
> could u guys be a little precise
You only want one combination?System.out.println("abcdefghij");
What do you mean by a "unique" combination? If this is for password recovery and you want to ensure that you don't issue the same password to two people (although it wouldn't necessarily matter if you did), you could store some strings in a lookup table and take them from there sequentially. Alternatively use a random number generator to get a number n and issue the nth permutation of 10 characters (see http://forum.java.sun.com/thread.jsp?forum=426&thread=312867, reply 18). The first of these would take constant time, and I haven't looked in detail at the algorithm on the link I've given but it looks pretty efficient.
did somebody forget his password ?
jpw35a at 2007-7-18 19:44:43 >
