In the third class, we introduce the iterative method.

The first two sections of the notes:

  • Math Notes for programmers 1- Base conversion
  • Programmer’s Math Note 2– remainder

03 iteration method

What is iterative method

The iterative method, in simple terms, is the continuous use of the old variable value, recursive calculation of the new variable value.

Here a story to introduce what is iterative method is used, the story is about a king to recompense a great contribution to a servant, let the courtiers suggested he wanted a reward, the clever officials said he wanted a reward – full of wheat on board, but the demand is the grain number of every grid is a grid of two times. The king thought this reward could be easily satisfied, but when he began to harvest the wheat, he found that the reward could not be satisfied even with the whole country’s grain.

Here we can use F (n) to represent the current wheat quantity, and the wheat quantity of the previous grid is F (n-1), so the request of the minister can be expressed as follows:

f(n) = f(n-1) * 2
f(1) = 1
Copy the code

This is the iterative method, and if implemented programmatically, is actually the implementation of a cycle of operations.

The code for calculating wheat in Python looks like this:

def get_number_of_wheat(grid):
    ' 'Param grid: param grid: return: '' '
    # f(1) = 1
    wheat_numbers = 1

    sums = wheat_numbers
    for i in range(2, grid+1):
        wheat_numbers *= 2
        sums += wheat_numbers

    print('when grid = %d, wheats numbers = %d' % (grid, sums))

    return sums
Copy the code

Simple test example:

if __name__ == '__main__':
    print('compute numbers of wheat! ')
    numbers_grid = 63
    get_number_of_wheat(numbers_grid)
    print('finish')
Copy the code

Given 63 cells, the output is as follows:

compute numbers of wheat!
when grid = 63, wheats numbers = 9223372036854775807
finish
Copy the code

So this astronomical number is 19 digits -9223372036854775807, really is very much! Assuming that a bag of 50 jin is estimated to contain 1.3 million grains of wheat, this calculation is equivalent to 7,094.9 billion bags of 50 jin of wheat!

Application of iterative method

After reading the above examples, I believe I should have a better understanding of the basic concepts of iterative method, and the basic steps of iterative method are also very simple, which can be divided into three steps:

  • Determine the variables to be used for iteration. In the example above, the iteration variable isf(n)andf(n-1)
  • Establish a recursive relationship between the iterated variables. In the example above, the recurrence isf(n)=f(n-1)*2
  • Control the iterative process. Here we need to determine the initial and termination conditions of the iteration. In the example above, the initial conditions aref(1)=1And the termination condition is to reach a given number of cells.

So what are the applications of iterative methods?

In fact, it has a wide range of applications in mathematics and computer fields, such as:

  • To find an exact or approximate solution to a numerical value. Typical methods include Bisection method and Newton’s iteration method.
  • Finds the target value in a range. Typical methods include binary search, in fact, is the application of binary search;
  • Iteration in machine learning algorithms. For example, Kmeans clustering algorithm (continuously iterating to cluster data), Markov chain, Gradient Descent, etc. Iterative method is widely used in machine learning because the process of machine learning is to obtain a local optimal solution according to known data and certain assumptions. Iterative methods help the learning algorithm search step by step until it finds such a solution.

We’ll focus on finding numerical solutions and finding matching records, both of which are implemented using dichotomy.

Find the exact or approximate solution of the equation

In addition to calculating large numbers, iterative methods can also help us make infinite approximations to get exact or approximate solutions to equations.

For example, if we want to calculate the square root of a given positive integer n (n>1), and we can’t use any of the programming language’s native functions, how do we do that?

So the first thing that we can make clear is that for a given positive integer n, the square root of it is definitely less than it, but greater than 1, which means that the square root of this number is between 1 and n, where the square of a number is equal to n.

And you can do that by applying that dichotomy. Each time you look at the median value within the range, check that it meets the criteria.

The first intermediate value is (1+10)/2=11/2=5.5. The square of 5.5 is 30.25, which is significantly larger than 10, so the search interval becomes [1, 5.5], which is to the left of 5.5. The median value is 3.25, but the square of 3.25 is 10.5625, still greater than 10. The searching interval becomes [1, 3.25], the median value becomes 2.125, the square of 2.125 is 4.515625, less than 10, so the interval is [2.125, 3.25]. Continue to find and compute the square of the median until you find a number whose square is exactly 10.

The specific steps are shown below:

This is achieved by code, as shown in the figure below:

def get_square_root(n, threshold, max_try):
    ' ''Calculate the square root of positive integers greater than 1 :param n: given positive integers :param threshold: error threshold: param max_try: maximum number of attempts :return:'' '
    if n <= 1:
        return1.0# interval boundary Indicates the left and right boundary of the intervalLeft = 1.0 right =float(n)
    for idx in range(max_try):
        # Prevent overflow
        middle = left + (right - left) / 2
        square = middle * middle
        # error
        delta = abs(square / n - 1)
        if delta <= threshold:
            return middle
        else:
            if square > n:
                right = middle
            else:
                left = middle

    return2.0Copy the code

Simple test example:

Square_root = get_square_root(10, 0.000001, 10000)ifSquare_root = = 1.0:print('please input a number > 1')
elifSquare_root = = 2.0:print('cannot find the square root')
else:
    print('square root==', square_root)
Copy the code

The output is:

Square root = = 3.1622767448425293Copy the code

In this code, two parameters are set to control the end of the iteration:

  1. threshold: Error threshold, used to control the accuracy of the solution. Theoretically, the dichotomy method can obtain the exact solution through infinite iterations, but the practical application still needs to consider time and computing resources, so generally we only need an approximate solution, but do not need completely accurate data.
  2. max_try: Controls the number of iterations. This parameter is also set to avoid usewhile TrueLoops can lead to endless loops, of course theoretically setthresholdIt is possible to avoid dead loops, but it is good programming practice to actively avoid the possibilities that arise.
Finding a match

Through iterative approximation, dichotomy can not only obtain the approximate solution of the equation, but also help to find the matching record.

The example given by the teacher here is in natural language processing, dealing with the extension of synonyms or synonyms. In this case, you will have a dictionary to record the synonyms and synonyms of each word. For a word to be searched, we need to find the word in the dictionary, along with all its synonyms and synonyms, and then expand. For example, for the word “tomato,” synonyms include tomato and tomato.

The dictionary is shown in the following table:

entry A synonym for 1 A synonym for 2 A synonym for 3
tomatoes tomato tomato .
. . . .

When you come across the word “tomato”, look it up in the dictionary, return synonyms or synonyms for” tomato” and “tomato”, and add them to the article as a synonym/synonym extension.

The problem to be solved here is how to query for matching words in the dictionary. One way to do that is to hash tables. And if you don’t use hash tables, you can use binary lookup. The idea of binary search method for dictionary query is as follows:

  1. Sort the entire dictionary first (presumably from smallest to largest). One of the key prerequisites for dichotomy is that the interval you’re looking for has to be ordered, so that every time you cut it in half, you know whether you’re going to go left or right.
  2. Use dichotomy to progressively locate the word being looked up. Similarly, the middle value of the search interval is selected each time to judge whether it is consistent with the word to be searched, and if so, return; If it is inconsistent, the size is judged. If it is smaller than the word to be searched, it needs to search to the right of the middle value. Otherwise, look in the left-hand interval.
  3. Repeat step 2 and search iteratively until the word is found or not found.

As opposed to using binary method to find the solution of the equation, binary search must require the data to be ordered!

The code is as follows:

def search_word(dictionary, word):
    ' ''Param dictionary: param word: search word: return:'' '
    if dictionary is None:
        return False
    if len(dictionary) < 1:
        return False

    left = 0
    right = len(dictionary) - 1
    while left <= right:
        middle = int(left + (right - left) / 2)
        if dictionary[middle] == word:
            return True
        else:
            if dictionary[middle] > word:
                right = middle - 1
            else:
                left = middle + 1

    return False

Copy the code

Simple test code:

print('find word in dictionary')
dict_list = ['i'.'am'.'coder']
dict_list = sorted(dict_list)
print('sorted dict:', dict_list)
word_to_find = 'am'
found = search_word(dict_list, word_to_find)
if found:
    print('word "%s" found in dictionary--%s! ' % (word_to_find, dict_list))
else:
    print('cannot find the word "%s"' % word_to_find)
Copy the code

Output result:

find word in dictionary
sorted dict: ['am'.'coder'.'i']
word "am" found in dictionary--['am'.'coder'.'i']!
finish
Copy the code

So much for the introduction to iterative methods! Above source code address:

Github.com/ccc013/Code…

Welcome to follow my wechat official account – Machine Learning and Computer Vision, or scan the qr code below, we can communicate, learn and progress together!