Wednesday, February 13, 2013

Basic recursivity for password

Basic recursivity for password

In the previous article, we were able to generate passwords as growing: 0-9, 00-99, 000-999, 0000-9999, 00000-99999, 000000-999999. From a computational point of view, we have produced exactly the same behavior with a series of loops constantly getting bigger.
If you have tested the program of the previous article, you would notice something quite interesting: the number of possibilities is proportional to the processing time. If you eg about 100,000 possible combinations, it can take 15 seconds to process all the results. If you have 1.1 million, you will need 11 * 15 seconds = 165 seconds = 2 minutes 45 seconds.
Although the computer code of the previous article is relatively predictable and effective to a certain extent, we note that the processing time is:


Processing time * delta T = (N ^ n)
Or delta T is the time for an operation
N is the number of possibilities for a draw
"N" is the number of tiny rods consecutive without replacement.

Now, let us ask the question, what is the use of recursivity allows faster processing? Before answering, we must define recursivity and then run some tests.

Firstly, in general, recursivity in computer science is the fact that a function is called or even. The purpose of the recursivity is often used functions of iterations and not mere repetition. To understand the limitations of recursivity in our context generator of passwords: watching the piece of code written specifically for this purpose. Note also that it is encoded in a mind to be closer to the example of the previous section in order to see what added recursivity in a function or a program is.


    Private Function CheckLetter2(Optional checker As String = "", Optional maxlenght As Integer = 3)
        Dim index1 As Integer
        Dim found As Boolean
        Dim date1 As Date
        Dim date2 As Date
        date1 = DateTime.Now
        found = False
        If Len(checker) < maxlenght Then
            'look for numbers
            For index1 = 0 To 9 Step 1 'recherche des chiffres
                CheckLetter2(checker & Microsoft.VisualBasic.ChrW(48 + index1), maxlenght)
                ListBox1.Items.Add(checker & Microsoft.VisualBasic.ChrW(48 + index1))
                If TextBox1.Text = checker Then
                    TextBox2.Text = checker
                End If
            Next
        End If
        date2 = DateTime.Now
        ToolStripStatusLabel1.Text = "Finished. " & date2.Subtract(date1).ToString & " and ListBox1 Count: " & ListBox1.Items.Count
        Return 0
    End Function


Observe how the function and reason out how the computer code is short. Recursivity has the advantage of clarifying the eyes of the programmer function and solving computer problems.

If you run the program and if you call the function, the image that follows will illustrate the result. Look at the picture below.

recursivity

The first thing you would notice is that the processing time is higher. Then, the order of generation of numbers is different. The problem is due to two reasons. The first is that unfortunately is inevitable memory consumption. When you apply the recursive function for the first time, call it for the purposes of Article function1. Your Function1 created large quantities of other recursive functions. When all functions are completed in function1, then function1 can then be completed. Function1 to run, your computer should store a large volume of recursive functions in your calculation. Also, the memory is slower than the processor and it requires several additional steps.
The second problem is that the type of recursivity used in this computer program is called linear recursivity and ordinary. I mean that it is ordinary for an ascending order of operations; the recursive function function1 should go as far iterating back then. It's hard for me to explain because the concept is best explained by an example.

Basic recursivity for password
In the picture, notice how the numbers are ordered. First digit longest is the smallest exited to finally grow naturally. The numbers are generated at shorter intervals with numbers longer. The end result is the same because you get the same number of possible combinations. Probably would have been more or less easy to obtain the same result as the previous article (0-9, 00-99, 000-999, 0000-9999 ...) instead of 0000, 0001, 0002 ... 0009 , 001, 00010, 0011, 0012, ... with recursivity .


Rate inverts the order between the printing of the result in the ListBox and call the recursive function does not change the processing time. It only changes a little presentation of results.
Note that reversing the order of treatment of 9 to 0 instead of 0 to 9 does not change in this case at the time of treatment. It only presents the same results in reverse order.

Read the previous article in the series of this article: The complexity of a password
Read the first series of this item: Password programming for beginners
Download the sample project: PassWordGame.zip




No comments:

Post a Comment