Develop a block diagram for finding the Euclidean algorithm. Euclidean algorithm

Euclid's algorithm is an algorithm for finding the greatest common divisor (GCD) of a pair of integers.

Greatest Common Divisor (GCD) is a number that divides two numbers without a remainder and is itself divisible without a remainder by any other divisor of the given two numbers. Simply put, this is the largest number by which two numbers for which the gcd is being sought can be divided without a remainder.

Algorithm for finding GCD by division

1. Divide the larger number by the smaller number.
2. If it is divided without a remainder, then the smaller number is GCD (you should exit the cycle).
3. If there is a remainder, then replace the larger number with the remainder of the division.
4. Let's move on to point 1.

Example:
Find gcd for 30 and 18.
30 / 18 = 1 (remainder 12)
18 / 12 = 1 (remainder 6)
12 / 6 = 2 (remainder 0)
End: GCD is a divisor of 6.
GCD(30, 18) = 6

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

In the loop, the remainder of the division is written to the variable a or b. The loop ends when at least one of the variables is zero. This means that the other one contains a gcd. However, we don’t know which one exactly. Therefore, for GCD we find the sum of these variables. Since one of the variables is zero, it has no effect on the result.

Algorithm for finding GCD by subtraction

1. Subtract the smaller number from the larger number.
2. If the result is 0, it means that the numbers are equal to each other and are GCD (you should exit the loop).
3. If the result of subtraction is not equal to 0, then replace the larger number with the result of the subtraction.
4. Let's move on to point 1.

Example:
Find gcd for 30 and 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
End: GCD is a minuend or subtrahend.
GCD(30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

Euclid's algorithm

Greatest common divisor

Consider the following problem: you need to write a program to determine the greatest common divisor (GCD) of two natural numbers.

Let's remember mathematics. The greatest common divisor of two natural numbers is the largest natural number by which they are evenly divisible. For example, the numbers 12 and 18 have common factors: 2, 3, 6. The greatest common factor is the number 6. This is written like this:

GCD(12, 18) = 6.

Let us denote the initial data as M u N. The problem statement is as follows:
Given: M, N
Find: GCD(M, N).

In this case, no additional mathematical formalization is required. The formulation of the problem itself is of a formal mathematical nature. There is no formula for calculating GCD(M, N) from the values ​​of M and N. But quite a long time ago, long before the advent of computers, an algorithmic method for solving this problem was known. It's called Euclidean algorithm .

The idea of ​​the Euclidean algorithm

The idea of ​​this algorithm is based on the property that if M>N, then

GCD(M, N) = GCD(M - N, N).

In other words, the gcd of two natural numbers is equal to the gcd of their positive difference (the modulus of their difference) and the smaller number.

It's easy to prove this property. Let K be the common divisor of M u N (M> N). This means that M = mK, N = nK, where m, n are natural numbers, and m > n. Then M - N = K(m - n), which means that K is a divisor of the number M - N. This means that all common divisors of the numbers M and N are divisors of their difference M - N, including the greatest common divisor.

The second obvious property:

GCD(M, M) = M.

For "manual" counting, the Euclidean algorithm looks like this:

1) if the numbers are equal, then take any of them as the answer, otherwise continue executing the algorithm;

2) replace the larger number with the difference between the larger and smaller numbers;

3) return to step 1.

Let's consider this algorithm using the example of M=32, N=24:

The structure of the algorithm is a while-loop with nested branching. The cycle is repeated until the values ​​of M and N are equal to each other. In branching, the larger of the two values ​​is replaced by their difference.

Now look at the trace table of the algorithm for the initial values ​​M = 32, N = 24.

Step	Operation	M	N	Condition
1	input M	32
2	input N		24
3	M¹N			32 no. 24, yeah
4	M>N			32>24, yes
5	M:=M-N	8
6	M¹N			8¹24, yeah
7	M>N			8>24, no
8	N:=N-M		16
9	M¹N			8¹16, yeah
10	M>N			8>16, no
11	N:=N-M		8
12	M¹N			8¹8, no
13	pin M	8
14	end

In the end, the result was correct.

Program in AY and Pascal

Let's write the algorithm in AY and the program in Pascal.

Questions and tasks

1. Run the Evklid program on your computer. Test it on the values ​​M = 32, N = 24; M = 696, N = 234.

2. Write a program to find the greatest common divisor of three numbers using the following formula:

GCD(A, B, C) = GCD(GCD(A, B), C).

3. Write a program to find the least common multiple (LCM) of two numbers using the formula:

A × B = GCD(A, B) × GCD(A, B).

In the preface to his first edition, “In the Kingdom of Ingenuity” (1908), E. I. Ignatiev writes: “... intellectual initiative, quick wit and “ingenuity” cannot be “drilled into” or “put into” anyone’s head. The results are reliable only when the introduction to the field of mathematical knowledge is made in an easy and pleasant way, using objects and examples from ordinary and everyday situations, selected with appropriate wit and entertainment.”

In the preface to the 1911 edition “The Role of Memory in Mathematics” E.I. Ignatiev writes “... in mathematics it is not the formulas that should be remembered, but the process of thinking.”

To extract the square root, there are tables of squares for two-digit numbers; you can factor the number into prime factors and extract the square root of the product. A table of squares is sometimes not enough; extracting the root by factoring is a time-consuming task, which also does not always lead to the desired result. Try taking the square root of 209764? Factoring into prime factors gives the product 2*2*52441. By trial and error, selection - this, of course, can be done if you are sure that this is an integer. The method I want to propose allows you to take the square root in any case.

Once upon a time at the institute (Perm State Pedagogical Institute) we were introduced to this method, which I now want to talk about. I never wondered whether this method had a proof, so now I had to deduce some of the proof myself.

The basis of this method is the composition of the number =.

=&, i.e. & 2 =596334.

1. Divide the number (5963364) into pairs from right to left (5`96`33`64)

2. Extract the square root of the first group on the left ( - number 2). This is how we get the first digit of &.

3. Find the square of the first digit (2 2 =4).

4. Find the difference between the first group and the square of the first digit (5-4=1).

5. We take down the next two digits (we get the number 196).

6. Double the first digit we found and write it on the left behind the line (2*2=4).

7. Now we need to find the second digit of the number &: double the first digit we found becomes the tens digit of the number, which when multiplied by the number of units, you need to get a number less than 196 (this is the number 4, 44*4=176). 4 is the second digit of &.

8. Find the difference (196-176=20).

9. We demolish the next group (we get the number 2033).

10. Double the number 24, we get 48.

There are 11.48 tens in a number, when multiplied by the number of ones, we should get a number less than 2033 (484*4=1936). The ones digit we found (4) is the third digit of the number &.

I have given the proof for the following cases:

1. Extracting the square root of a three-digit number;

2. Extracting the square root of a four-digit number.

Approximate methods for extracting square roots (without using a calculator).

1. The ancient Babylonians used the following method to find the approximate value of the square root of their number x. They represented the number x as the sum a 2 + b, where a 2 is the exact square of the natural number a (a 2 ? x) closest to the number x, and used the formula . (1)

Using formula (1), we extract the square root, for example, from the number 28:

The result of extracting the root of 28 using MK is 5.2915026.

As you can see, the Babylonian method gives a good approximation to the exact value of the root.

2. Isaac Newton developed a method for taking square roots that dates back to Heron of Alexandria (circa 100 AD). This method (known as Newton's method) is as follows.

Let a 1- the first approximation of a number (as a 1 you can take the values ​​of the square root of a natural number - an exact square not exceeding X) .

Next, more accurate approximation a 2 numbers found by the formula .

The circle showed how you can extract square roots in a column. You can calculate the root with arbitrary precision, find any number of digits in its decimal notation, even if it turns out to be irrational. The algorithm was remembered, but questions remained. It was not clear where the method came from and why it gave the correct result. It wasn’t in the books, or maybe I was just looking in the wrong books. In the end, like much of what I know and can do today, I came up with it myself. I share my knowledge here. By the way, I still don’t know where the rationale for the algorithm is given)))

So, first I tell you “how the system works” with an example, and then I explain why it actually works.

Let’s take a number (the number was taken “out of thin air”, it just came to mind).

1. We divide its numbers into pairs: those to the left of the decimal point are grouped two from right to left, and those to the right are grouped two from left to right. We get.

2. We extract the square root from the first group of numbers on the left - in our case this is (it is clear that the exact root may not be extracted, we take a number whose square is as close as possible to our number formed by the first group of numbers, but does not exceed it). In our case this will be a number. We write down the answer - this is the most significant digit of the root.

3. We square the number that is already in the answer - this - and subtract it from the first group of numbers on the left - from the number. In our case it remains .

4. We assign the following group of two numbers to the right: . We multiply the number that is already in the answer by , and we get .

5. Now watch carefully. We need to assign one digit to the number on the right, and multiply the number by, that is, by the same assigned digit. The result should be as close as possible to, but again no more than this number. In our case, this will be the number, we write it in the answer next to, on the right. This is the next digit in the decimal notation of our square root.

6. From subtract the product , we get .

7. Next, we repeat the familiar operations: we assign the following group of digits to the right, multiply by , to the resulting number > we assign one digit to the right, such that when multiplied by it we get a number smaller than , but closest to it - this is the next digit in decimal root notation.

The calculations will be written as follows:

And now the promised explanation. The algorithm is based on the formula

Comments: 51

1. 2 Anton:

   Too chaotic and confusing. Arrange everything point by point and number them. Plus: explain where we substitute the required values ​​in each action. I’ve never calculated a root root before; I had a hard time figuring it out.

2. 5 Julia:

3. 6 :

   Yulia, 23 is currently written on the right; these are the first two (on the left) digits of the root already received in the answer. Multiply by 2 according to the algorithm. We repeat the steps described in point 4.

4. 7 zzz:

   error in “6. From 167 we subtract the product 43 * 3 = 123 (129 nada), we get 38.”
   I don’t understand how it turned out to be 08 after the decimal point...

5. 9 Fedotov Alexander:

   And even in the pre-calculator era, we were taught at school not only the square root, but also the cube root in a column, but this was more tedious and painstaking work. It was easier to use Bradis tables or a slide rule, which we already studied in high school.

6. 10 :

   Alexander, you are right, you can extract roots of large powers into a column. I'm going to write just about how to find the cube root.

7. 12 Sergei Valentinovich:

   Dear Elizaveta Alexandrovna! In the late 70s, I developed a scheme for automatic (i.e., not by selection) calculation of quadra. root on the Felix adding machine. If you are interested, I can send you a description.

8. 14 Vlad aus Engelsstadt:

   (((Extracting the square root of the column)))
   The algorithm is simplified if you use the 2nd number system, which is studied in computer science, but is also useful in mathematics. A.N. Kolmogorov presented this algorithm in popular lectures for schoolchildren. His article can be found in the “Chebyshev Collection” (Mathematical Journal, look for a link to it on the Internet)
   By the way, say:
   G. Leibniz at one time toyed with the idea of ​​​​transitioning from the 10th number system to the binary one because of its simplicity and accessibility for beginners (primary schoolchildren). But breaking established traditions is like breaking a fortress gate with your forehead: it’s possible, but it’s useless. So it turns out, as according to the most quoted bearded philosopher in the old days: the traditions of all dead generations suppress the consciousness of the living.

   Until next time.

9. 15 Vlad aus Engelsstadt:

   ))Sergey Valentinovich, yes, I’m interested...((

   I bet that this is a variation on the “Felix” of the Babylonian method of extracting the square knight using the method of successive approximations. This algorithm was covered by Newton's method (tangent method)

   I wonder if I was wrong in my forecast?

10. 18 :

    2Vlad aus Engelsstadt

    Yes, the algorithm in binary should be simpler, that's pretty obvious.

    About Newton's method. Maybe that's true, but it's still interesting

11. 20 Kirill:

    Thanks a lot. But there is still no algorithm, no one knows where it came from, but the result is correct. THANKS A LOT! I've been looking for this for a long time)

12. 21 Alexander:

    How will you extract the root from a number where the second group from left to right is very small? for example, everyone's favorite number is 4,398,046,511,104. After the first subtraction, it is not possible to continue everything according to the algorithm. Can you explain please.

13. 22 Alexey:

    Yes, I know this method. I remember reading it in the book “Algebra” of some old edition. Then, by analogy, he himself deduced how to extract the cube root in a column. But there it’s already more complicated: each digit is determined not by one (as for a square), but by two subtractions, and even there you have to multiply long numbers every time.

14. 23 Artem:

    There are typos in the example of extracting the square root of 56789.321. The group of numbers 32 is assigned twice to the numbers 145 and 243, in the number 2388025 the second 8 must be replaced by 3. Then the last subtraction should be written as follows: 2431000 – 2383025 = 47975.
    Additionally, when dividing the remainder by the doubled value of the answer (without taking into account the comma), we obtain an additional number of significant digits (47975/(2*238305) = 0.100658819...), which should be added to the answer (√56789.321 = 238.305... = 238.305100659).

15. 24 Sergey:

    Apparently the algorithm came from Isaac Newton’s book “General Arithmetic or a book on arithmetic synthesis and analysis.” Here is an excerpt from it:

    ABOUT EXTRACTING ROOTS

    To extract the square root of a number, you must first place a dot above its digits, starting from the ones. Then you should write in the quotient or radical the number whose square is equal to or closest in disadvantage to the numbers or number preceding the first point. After subtracting this square, the remaining digits of the root will be sequentially found by dividing the remainder by twice the value of the already extracted part of the root and subtracting each time from the remainder of the square the last found digit and its tenfold product by the named divisor.

16. 25 Sergey:

    Please also correct the title of the book “General Arithmetic or a book about arithmetic synthesis and analysis”

17. 26 Alexander:

    Thanks for the interesting material. But this method seems to me somewhat more complicated than what is needed, for example, for a schoolchild. I use a simpler method based on expanding a quadratic function using the first two derivatives. Its formula is:
    sqrt(x)= A1+A2-A3, where
    A1 is the integer whose square is closest to x;
    A2 is a fraction, the numerator is x-A1, the denominator is 2*A1.
    For most numbers encountered in a school course, this is enough to get the result accurate to the hundredth.
    If you need a more accurate result, take
    A3 is a fraction, the numerator is A2 squared, the denominator is 2*A1+1.
    Of course, to use it you need a table of squares of integers, but this is not a problem at school. Remembering this formula is quite simple.
    However, it confuses me that I obtained A3 empirically as a result of experiments with a spreadsheet and I do not quite understand why this member has this appearance. Maybe you can give me some advice?

18. 27 Alexander:

    Yes, I've considered these considerations too, but the devil is in the details. You write:
    “since a2 and b differ quite little.” The question is exactly how little.
    This formula works well on numbers in the second ten and much worse (not up to hundredths, only up to tenths) on numbers in the first ten. Why this happens is difficult to understand without the use of derivatives.

19. 28 Alexander:

    I will clarify what I see as the advantage of the formula I propose. It does not require the not entirely natural division of numbers into pairs of digits, which, as experience shows, is often performed with errors. Its meaning is obvious, but for a person familiar with analysis, it is trivial. Works well on numbers from 100 to 1000, which are the most common numbers encountered in school.

20. 29 Alexander:

    By the way, I did some digging and found the exact expression for A3 in my formula:
    A3= A22 /2(A1+A2)

21. 30 vasil stryzhak:

    In our time, with the widespread use of computer technology, the question of extracting the square knight from a number is not worth it from a practical point of view. But for mathematics lovers, various options for solving this problem will undoubtedly be of interest. In the school curriculum, the method of this calculation without the use of additional funds should take place on a par with multiplication and long division. The calculation algorithm must not only be memorized, but also understandable. The classical method, presented in this material for discussion with disclosure of the essence, fully complies with the above criteria.
    A significant drawback of the method proposed by Alexander is the use of a table of squares of integers. The author is silent about the majority of numbers encountered in the school course. As for the formula, in general I like it due to the relatively high accuracy of the calculation.

22. 31 Alexander:

    for 30 vasil stryzhak
    I didn't keep anything quiet. The table of squares is supposed to be up to 1000. In my time at school they simply learned it by heart and it was in all mathematics textbooks. I explicitly named this interval.
    As for computer technology, it is not used mainly in mathematics lessons, unless the topic of using a calculator is specifically discussed. Calculators are now built into devices that are prohibited for use on the Unified State Exam.

23. 32 vasil stryzhak:

    Alexander, thank you for the clarification! I thought that for the proposed method it is theoretically necessary to remember or use a table of squares of all two-digit numbers. Then for radical numbers not included in the interval from 100 to 10000, you can use the technique of increasing or decreasing them by the required number of orders of magnitude by moving the decimal point.

24. 33 vasil stryzhak:

25. 39 ALEXANDER:

    MY FIRST PROGRAM IN IAMB LANGUAGE ON THE SOVIET MACHINE “ISKRA 555″ WAS WRITTEN TO EXTRACT THE SQUARE ROOT OF A NUMBER USING THE COLUMN EXTRACTION ALGORITHM! and now I forgot how to extract it manually!