Extended euclidean algorithm python

Реализации алгоритмов/Расширенный алгоритм Евклида

Расширенный алгоритм Евклида вычисляет НОД двух заданных целых чисел и их коэффициенты Безу.

На языке Си [ править ]

#include int main() int a, b, p=1, q=0, r=0, s=1, x, y; scanf("%d %d",&a,&b); while (a && b)  if (a>=b)  a = a - b; p = p - r; q = q - s; > else  b = b - a; r = r - p; s = s - q; > > if (a)  x = p; y = q; >else  x = r; y = s; > printf("%d %d\n",x,y); return 0; > 

На языке Python, итерационная версия [ править ]

def bezout(a, b): '''An implementation of extended Euclidean algorithm. Returns integer x, y and gcd(a, b) for Bezout equation: ax + by = gcd(a, b). ''' x, xx, y, yy = 1, 0, 0, 1 while b: q = a // b a, b = b, a % b x, xx = xx, x - xx*q y, yy = yy, y - yy*q return (x, y, a) 

На языке Python, рекурсивная версия [ править ]

def bezout_recursive(a, b): '''A recursive implementation of extended Euclidean algorithm. Returns integer x, y and gcd(a, b) for Bezout equation: ax + by = gcd(a, b). ''' if not b: return (1, 0, a) y, x, g = bezout_recursive(b, a % b) return (x, y - (a // b) * x, g) 

На языке Racket, итеративная версия [ править ]

(define (bezout-gcd a b) ; Переменные на каждом шаге алгоритма: ; r-1 - r_ = a * s + b * t; ; r-2 - r_ = a * u + b * v. (define (step r-2 s t r-1 u v) (if (zero? r-1) ; Если r-1 = 0, то НОД(a, b) = r-2 и его коэффициенты Безу (КБ) найдены, ; возврат этой тройки (values r-2 s t) ; Иначе, нужно вычислить: ; - следующий остаток r = r-1 - r-2 * q (1); ; - и КБ для r, по выражению (1) и известным КБ для r-1, r-2. ; На следующем шаге: ; - r-2 ← r-1 (с коэффициентами u и v), ; - и r-1 ← r с новыми коэффициентами. (let-values (((q r) (quotient/remainder r-2 r-1))) (step r-1 u v r (- s (* q u)) (- t (* q v)))))) ; На первом шаге алгоритма остатками являются a и b с очевидными начальными ; КБ. (step a 1 0 b 0 1)) 

Источник

egcd 0.5.0

Easy-to-import library with a basic, efficient, pure-Python implementation of the extended Euclidean algorithm.

Навигация

Ссылки проекта

Статистика

Метаданные

Лицензия: MIT

Требует: Python >=3.7

Сопровождающие

Описание проекта

Easy-to-import library with a basic, efficient, pure-Python implementation of the extended Euclidean algorithm.

Installation and Usage

This library is available as a package on PyPI:

python -m pip install egcd

The library can be imported in the usual way:

Examples

The function egcd is an efficient implementation of the extended Euclidean algorithm. It accepts two integer inputs b and n , returning a tuple of the form (gcd(b, n), a, m) where the three integers in the tuple satisfy the identity (a * b) + (n * m) == gcd(b, n) :

Development

All installation and development dependencies are fully specified in pyproject.toml . The project.optional-dependencies object is used to specify optional requirements for various development tasks. This makes it possible to specify additional options (such as docs , lint , and so on) when performing installation using pip:

Documentation

The documentation can be generated automatically from the source files using Sphinx:

python -m pip install . docs -f -E --templatedir -o _source ..  make html

Testing and Conventions

All unit tests are executed and their coverage is measured when using pytest (see the pyproject.toml file for configuration details):

python -m pip install . -m pytest

Alternatively, all unit tests are included in the module itself and can be executed using doctest:

Style conventions are enforced using Pylint:

python -m pip install . -m pylint src/egcd

Contributions

In order to contribute to the source code, open an issue or submit a pull request on the GitHub page for this library.

Versioning

Beginning with version 0.1.0, the version number format for this library and the changes to the library associated with version number increments conform with Semantic Versioning 2.0.0.

Publishing

This library can be published as a package on PyPI by a package maintainer. First, install the dependencies required for packaging and publishing:

python -m pip install .Ensure that the correct version number appears in pyproject.toml , and that any links in this README document to the Read the Docs documentation of this package (or its dependencies) have appropriate version numbers. Also ensure that the Read the Docs project for this library has an automation rule that activates and sets as the default all tagged versions. Create and push a tag for this version (replacing . with the version number):

Remove any old build/distribution files. Then, package the source into a distribution archive:

rm -rf build dist src/*.egg-info -m build --sdist --wheel .

Finally, upload the package distribution archive to PyPI:

python -m twine upload dist/*

Источник

Euclidean Algorithm and Extended Euclidean Algorithm in Python

The Euclidean Algorithm is a method for calculating the greatest common divisor (GCD) of two integers. With Python, we can use recursion to calculate the GCD of two integers with the Euclidean Algorithm.

def euclideanAlgorithm(a,b): if b == 0: return a return euclideanAlgorithm(b, a % b) print(euclideanAlgorithm(10,25)) #Output: 5

We can also use Python to implement the Extended Euclidean Algorithm which finds integers x and y such that ax + by = gcd(a,b) with a recursive function.

def extendedEuclideanAlgorithm(a,b): if a == 0: return b, 0, 1 gcd, u, v = extendedEuclideanAlgorithm(b % a, a) x = v - (b // a ) * u y = u return gcd, x, y print(extendedEuclideanAlgorithm(10,25)) #Output: (5, -2, 1)

Python allows us to implement complex algorithms to do various calculations. One such calculation is finding the greatest common divisor of two integers.

We can use the math gcd() function in Python to find the GCD of two integers, but implementing the Euclidean Algorithm which is used to find the GCD of two integers isn’t too bad.

We can use a recursive function to find the GCD of two numbers with the Euclidean Algorithm.

The Euclidean algorithm is a continual repetition which repeatedly divides the divisor of two integers by the remainder of that division until the resulting remainder is 0. The GCD is the last non-zero remainder in this algorithm.

With Python, we can implement this easily with a recursive function. For a recursive function, we need to define a base case, and a recursive step.

The base case is when the remainder after division between the two integers is 0. The recursive step is calling our algorithm with the divisor and remainder after division.

Below is a recursive function which takes two integers and returns the GCD using the Euclidean Algorithm.

def euclideanAlgorithm(a,b): if b == 0: return a return euclideanAlgorithm(b, a % b) print(euclideanAlgorithm(10,25)) print(euclideanAlgorithm(90,33)) print(euclideanAlgorithm(1003,85)) print(euclideanAlgorithm(74,46)) #Output: 5 3 17 2

Implementing the Extended Euclidean Algorithm in Python

We can also implement the Extended Euclidean Algorithm in Python.

The Extended Euclidean Algorithm is an algorithm that finds integers x and y such that ax + by = gcd(a,b).

The Extended Euclidean Algorithm works in two steps. First, we need to find the GCD. So we use the Euclidean Algorithm to calculate the GCD of two integers. Then, to get x and y, we work backwards recursively.

For a recursive function, we need a base case and a recursive step.

In the extended Euclidean Algorithm, we have the same base case as above, as we are first finding the GCD of the two integers.

Then, we work backwards to get x and y.

To get x and y, at each step we can update the coefficients based on the following equations, where u and v are the coefficients which satisfy the equation (a % b) * u + b * v = GCD(a,b).

Below is a full implementation of the Extended Euclidean Algorithm in Python.

def extendedEuclideanAlgorithm(a,b): if b == 0: return a, 0, 1 gcd, u, v = extendedEuclideanAlgorithm(b, a % b) x = v - (a // b ) * u y = u return gcd, x, y print(extendedEuclideanAlgorithm(10,25)) print(extendedEuclideanAlgorithm(90,33)) print(extendedEuclideanAlgorithm(1003,85)) print(extendedEuclideanAlgorithm(74,46)) #Output: (5, 1, -2) (3, 11, -4) (17, 12, -1) (2, -8, 5)

Hopefully this article has been helpful for you to learn how to implement the Euclidean Algorithm and Extended Euclidean Algorithm to calculate greatest common divisors in Python.

Other Articles You’ll Also Like:

• 1. Get Name of Function in Python
• 2. e in Python – Using Math Module to Get Euler’s Constant e
• 3. How to Iterate over Everything in Word Document using python-docx
• 4. Create List of Numbers from 1 to 100 Using Python
• 5. pandas DataFrame size – Get Number of Elements in DataFrame or Series
• 6. Python sinh – Find Hyperbolic Sine of Number Using math.sinh()
• 7. pandas Standard Deviation – Using std() to Find Standard Deviation
• 8. Using pandas sample() to Generate a Random Sample of a DataFrame
• 9. Create List of Odd Numbers in Range with Python
• 10. Writing a Table Faster to Word Document Using python-docx

About The Programming Expert

The Programming Expert is a compilation of a programmer’s findings in the world of software development, website creation, and automation of processes.

Programming allows us to create amazing applications which make our work more efficient, repeatable and accurate.

At the end of the day, we want to be able to just push a button and let the code do it’s magic.

You can read more about us on our about page.

Источник