Euclidean Algorithm: GCD Calculation

Description

This lecture introduces the Euclidean algorithm for calculating the greatest common divisor (GCD) of two positive integers. The algorithm is based on the property that the GCD of two numbers is also the GCD of the smaller number and the remainder of their division. Through a series of slides, the instructor explains the termination conditions of the algorithm, the importance of the loop invariant, and the constant nature of the returned GCD value. The lecture also covers the complexity analysis of algorithms, focusing on time measurements and the evaluation criteria based on the size of the input.

Official source

https://mediaspace.epfl.ch/media/0_c8smupfw

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (62)

Related concepts (49)

Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use.

Coprime integers

In number theory, two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides a does not divide b, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also a is prime to b or a is coprime with b. The numbers 8 and 9 are coprime, despite the fact that neither considered individually is a prime number, since 1 is their only common divisor.

Linux kernel

The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally written in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU operating system, which was written to be a free (libre) replacement for Unix. Linux is provided under the GNU General Public License version 2 only, but it contains files under other compatible licenses.

Firefox

Mozilla Firefox, or simply Firefox, is a free and open-source web browser developed by the Mozilla Foundation and its subsidiary, the Mozilla Corporation. It uses the Gecko rendering engine to display web pages, which implements current and anticipated web standards. In November 2017, Firefox began incorporating new technology under the code name "Quantum" to promote parallelism and a more intuitive user interface. Firefox is available for Windows 7 or later versions, macOS, and Linux.

Quadratic integer

In number theory, quadratic integers are a generalization of the usual integers to quadratic fields. Quadratic integers are algebraic integers of degree two, that is, solutions of equations of the form x2 + bx + c = 0 with b and c (usual) integers. When algebraic integers are considered, the usual integers are often called rational integers. Common examples of quadratic integers are the square roots of rational integers, such as , and the complex number i = , which generates the Gaussian integers.