ChatGPT and [Python] programs for the GCD()

Patrick Reany

23 June 2023

ChatGPT and GCD

Note: GCD() is a number-theoretic function that takes in n integers (just 2 for our
purposes here) and outputs their greatest common divisor.

On 22 June 2023, I asked ChatGPT to give me a Python program to find the GCD of two
integers using the Euclidean algorithm. What follows is the reply I got, plus a few
additional programs I found on the Internet, plus some comments I added here and there.
The various programs attack the coding in a variety of ways. I expect to learn a lot of
Python techniques by comparing and contrasting the various versions. BTW, I'm just a
beginner Python programmer.

Programming Aside: Just today, I happened upon a YouTube video in which the speaker claimed
that one of his regrets he has about his early days of learning how to program is that he didn't
take the time to break away from instructional materials (including YouTube videos) and
start coding early on. Really?! When I tackle a new programming language, the first thing
I want to do is to write a bunch of small but useful programs -- useful to me anyway.
Therein lies a great deal of motivation and immediate satisfaction. You simply have to
learn how to THINK SMALL! Successful small programs can quickly teach you a lot about
a programming language. Later on, I can construct larger programs.

Anyway, I tried out each program and they all worked. So, let's get started!

Patrick: Write a Python program that will calculate the GCD of two integers using the
Euclidean algorithm.

ChatGPT:

Certainly! Here's a Python program that calculates the greatest common divisor
(GCD) of two integers using the Euclidean algorithm:

python code:

...........................

def gcd(a, b):
     while b != 0:
          print("a = ", a, "b = ", b, "a % b = ", a % b)
          a, b = b, a % b
     return a
# Input two integers
num1 = int(input("Enter the first integer: "))
num2 = int(input("Enter the second integer: "))

# Calculate the GCD using the Euclidean algorithm result = gcd(num1, num2)

# Print the GCD
print("The GCD of", num1, "and", num2, "is:", result)

.................................

In this program, the gcd() function takes two integers a and b as input and uses the
Euclidean algorithm to calculate their GCD. It repeatedly replaces a with b and b with
the remainder of a divided by b until b becomes 0. At that point, the value of a is
the GCD of the original two integers.

You can run this program and enter any two integers to find their GCD.

FYI: In standard language, we write Dividend = Quotient x Divisor + Remainder

I tested each program on the numbers 27 and 392 because I have recently uploaded a paper
on the GCD that uses those numbers, so I knew what to expect. The programs as given do
not contain a print command to show the steps as they proceed. So, to each of the programs
I added an appropriate print statement. If you prefer not to have that print command active,
you don't have to delete it, just comment it out.

'''''''''''''''''''''''''''''''''''''

This is from

https://developerpublish.com/
python-program-to-find-gcd-of-two-numbers/?expand_article=1

# Python Program to find GCD of Two Numbers a temp variable

num1 = int(input("Enter the first integer: "))
num2 = int(input("\nEnter the second integer: "))
a = num1
b = num2
while(num2 != 0):
# swap using temp variable
   temp = num2
   num2 = num1 % num2
   num1 = temp
   print("\n num1 = ", num1, " num2 = ", num2)
gdc = num1
print("\nThe GDC of {0} and {1} is {2}".format(a,b,gdc))

My comment: I suppose one could call this the 'old fashioned' method of
coding because it uses a temporary variable.

''''''''''''''''''''''''''''''''''''''''''''''''

The following is from

https://www.geeksforgeeks.org/
python-program-to-find-the-gcd-of-two-numbers/

# Python code to demonstrate naive
# method to compute gcd ( recursion )

def hcf(a, b):
     if(b == 0):
         return a
     else:
         print("\na = ", a, "b = ", b, "a%b = ", a%b)
         return hcf(b, a % b)

a = 60
b = 48

# prints 12
print("The gcd of 60 and 48 is : ", end="")
print(hcf(60, 48))

''''''''''''''''''''''''''''''''''''''''''''''''

My comments: The GCD is also referred to as the HCF, or highest common factor.
I asked ChatGPT to assist me on this alternative notation.

Patrick: Since the notation HCF() [highest common factor] is not common in math (as
judged by university-level math texts), who uses it? Is it more common in grade
schools, high schools, or in countries outside the US?

ChatGPT:

The notation "HCF()" (standing for Highest Common Factor) is not commonly
used in formal mathematics textbooks or advanced mathematical literature.
Instead, the term "GCD" (Greatest Common Divisor) is more prevalent and
widely recognized.

However, the use of "HCF()" or similar notations may vary depending on the
educational level and country. In some grade school or high school curricula,
particularly in certain countries outside the United States, the term "HCF"
may be more commonly used. It is often used in the British educational system,
for example.

In general, the choice of notation can vary between educational systems and
textbooks. While "GCD" is more commonly used in advanced mathematics, "HCF"
may be introduced at lower levels to familiarize students with the concept of
finding the largest common factor between two or more numbers.

The following is from

https://stackoverflow.com/questions/21608593/
euclidean-algorithm-gcd-in-python

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("\na = ", a,"b = ", b, "q = ", q, "r = ", r,)

print(b)

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This is what Bingchat claimed would work to find the GCD of two numbers using
functional programming in Python:

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Here is an example of how to find the GCD of two numbers using functional programming
in Python:

from functools import reduce

def gcd(a, b): return reduce(lambda x, y: x if y == 0 else gcd(y, x % y), [a, b])

print(gcd(60, 48)) # Output: 12

The reduce() function applies a rolling computation to sequential pairs of values
in a list. In this case, it applies the lambda function to the list [a,b]. The lambda
function takes two arguments x and y, and returns x if y is zero. Otherwise,
it calls itself recursively with arguments y and x % y.

I hope this helps!

My comment:

Actually, dear Bingchat, I have no idea how this program works. Maybe
I'll get back to it someday when I have time to learn functional programming.

My final comments: When I ran the ChatGPT version of the program with the additional
print command turned on, I got for GCD(27,392) the following output:

But when I switched the order of input of the integers, I got:

And our results are consistent with the fact that GCD(x,y) = GCD(y,x).

Just for curiosity's sake, I went back to ChatGPT for a list of ten uses of the
GCD function:

Patrick: Name up to ten important uses of the greatest common divisor function in engineering
or mathematics.

ChatGPT:

The greatest common divisor (GCD) function, also known as the greatest common factor (GCF)
function, has various applications in engineering and mathematics. Here are ten important
uses of the GCD function:

1) Simplifying fractions: The GCD is used to simplify fractions by dividing both the numerator
and denominator by their common factor. This reduces the fraction to its simplest form.

2) Modular arithmetic: The GCD is used to find modular inverses. In cryptography and computer
science, modular inverses play a crucial role in encryption and decryption algorithms.

3) Diophantine equations: The GCD is employed in solving Diophantine equations, which are
polynomial equations with integer solutions. The GCD helps determine if a solution exists and
finds the general solution.

4) Euclidean algorithm: The GCD function is a fundamental tool in the Euclidean algorithm
for finding the GCD of two numbers. This algorithm has wide applications in many areas of
mathematics and computer science.

5) LCM and GCD relationship: The GCD function is used to find the least common multiple
(LCM) of two numbers. The relationship between GCD and LCM is crucial for various mathematical
manipulations and problem-solving techniques.

6) Matrix operations: The GCD is used in matrix computations, such as matrix reduction and row
operations. It helps in finding the greatest common divisor of the elements in a matrix, which is
useful for simplification and analysis.

7) Polynomial factorization: The GCD function is used in polynomial factorization. It helps
in finding common factors of polynomials, which is essential in simplifying expressions and
solving polynomial equations.

8) Signal processing: The GCD is employed in signal processing applications, such as finding
the fundamental frequency of a signal. It helps identify the common periods or cycles present
in a signal.

9) Time complexity analysis: The GCD function is used in analyzing the time complexity of algorithms.
It helps determine the number of iterations or recursive calls required by an algorithm, particularly
in cases where GCD operations are involved.

10) Error detection and correction: The GCD is used in error detection and correction codes,
such as the checksum method. It helps identify errors or discrepancies in data transmission and
assists in correcting them.

These are just a few important uses of the GCD function in engineering and mathematics,
highlighting its versatility and significance in various domains.