Hướng dẫn calculate euclidean in python

Question

HowTo
Python NumPy Howtos
Calculate Euclidean Distance in Python

Created: April-09, 2021 | Updated: November-26, 2021

Nội dung chính Show

Use the NumPy Module to Find the Euclidean Distance Between Two Points
Use the distance.euclidean() Function to Find the Euclidean Distance Between Two Points
Use the math.dist() Function to Find the Euclidean Distance Between Two Points
Related Article - NumPy Math
Not the answer you're looking for? Browse other questions tagged python or ask your own question.

Use the NumPy Module to Find the Euclidean Distance Between Two Points
Use the distance.euclidean() Function to Find the Euclidean Distance Between Two Points
Use the math.dist() Function to Find the Euclidean Distance Between Two Points

In the world of mathematics, the shortest distance between two points in any dimension is termed the Euclidean distance. It is the square root of the sum of squares of the difference between two points.

I'm trying to write the Euclidean Algorithm in Python. It's to find the GCD of two really large numbers. The formula is a = bq + r where a and b are your two numbers, q is the number of times b divides a evenly, and r is the remainder.

I can write the code to find that, however if it the original numbers don't produce a remainder (r) of zero then the algorithm goes to step 2 => b = rx + y. (same as the first step but simply subbing b for a, and r for b) the two steps repeat until r divides both a and b evenly.

This is my code, I haven't yet figured out how to do the subbing of values and create a loop until the GCD is found.

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
r = int(a - (b)*int(a/b))

if r == 0:
  print("The GCD of the two choosen numbers is " + str(b))

elif r != 0:
  return b and r
  (b == a) and (r == b)

print("The GCD of the two numbers is " + str(r))

Chris Martin

29.6k8 gold badges74 silver badges131 bronze badges

asked Feb 6, 2014 at 16:32

2

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
r=a%b
while r:
    a=b
    b=r
    r=a%b
print('GCD is:', b)

or use break in loop:

a = int(input("What's the first number? "))
b = int(input("What's the second number? ")) 
while 1:
    r=a%b
    if not r:
        break
    a=b
    b=r
print('GCD is:', b)

answered Feb 6, 2014 at 16:43

zhangxaochenzhangxaochen

31.2k15 gold badges71 silver badges105 bronze badges

Try This

a = int(input("Enter No.1"))

b = int(input("Enter No.2"))

r = a%b

q = int(a/b)

while(r!=0):

    a = b

    b = r

    q = int(a/b)

    r = a - (b * q)


print(b)

answered Oct 23, 2018 at 13:50

I know this is old post but here it is:

def GCD(x , y):
    """This is used to calculate the GCD of the given two numbers.
    You remember the farm land problem where we need to find the 
    largest , equal size , square plots of a given plot?"""
    if y == 0:
        return x
    r = int(x % y)
    return GCD(y , r)

Taken from Algorithms 4th edition.

Note: if your numbers are REALLY REALLY large then try to increase the recursion limit by:

import sys
sys.seterecursionlimit("your new limit")

but be very very careful with it. I was able to fill my 12GB RAM and cause a freeze quite easily.

answered May 15, 2021 at 22:27

I think that's the shortest solution:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

answered Sep 29, 2021 at 18:44

I think there's one missing important condition for Euclidean Algorithm to work, which is a >= b > 0. So may I suggest this code I just made (quite long cuz I haven't viewed prev answers before building it haha.

def gcd(int1: int, int2: int):
# I used a recursive algorithm
# Condition: a>=b>0
if int1 < int2:
    a = int2
    b = int1
else:
    a = int1
    b = int2

if a % b == 0:
    return b
else:
    r = a % b
    gcd(b, r)
    return r

answered Jan 13 at 13:10

I recently came across a question like this in my math class. The code I wrote was:

def EuclideanAlg(a,b):
    # switches the value of a and b if a is less than b
    if a <= b - 1:
        temp = a
        a = b
        b = temp
    # takes the remainder after a is divided by b
    r = a % b
    # iterates infinitely
    while True:
        # if a is divisible by b, b is the gcd of a,b
        if r == 0:
            return b
            break
        # a becomes the current value of b and b becomes the current value of r
        else:
            temp = r
            r = b % r
            b = temp

answered Aug 20 at 2:59