patternpythonMinor
Extended Euclidean algorithm and modular multiplicative inverse element
Viewed 0 times
inverseeuclideanextendedmodularalgorithmelementandmultiplicative
Problem
After my first exercise here is another. Again, this is exactly that: Exercise, which means that the output doesn't necessarily need to be beautifully formatted, etc. I probably have some variable naming issues around and also more general issues.
# coding=utf-8
"""Basic usage:
$ python xggt.py 3343 77
(1, -12, 521)
65
"""
import argparse
###############################################################################
def main():
"""Prints out the results of xggt().
xggt() takes two non-optional integers as arguments.
"""
parser = argparse.ArgumentParser()
parser.add_argument('num_1', type=int)
parser.add_argument('num_2', type=int)
args = parser.parse_args()
if (args.num_1 == 0) and (args.num_2 == 0):
print("Please enter two positive integers.")
else:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))
###############################################################################
def xggt(num_1, num_2):
"""Implements the Extended Euclidean algorithm.
Returns the greatest common divisor of two integers > 0.
Also returns the coefficients of Bézout’s identity.
"""
if num_1 % num_2 == 0:
return(num_2, 0, 1)
else:
gcd, lin_fact_1, lin_fact_2 = xggt(num_2, num_1 % num_2)
lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
return(gcd, lin_fact_2, lin_fact_1)
###############################################################################
def modinv(num_1, num_2):
"""Returns the modular multiplicative inverse of two integers > 0
"""
gcd, lin_fact_1, _ = xggt(num_1, num_2)
if gcd != 1:
return None
else:
return lin_fact_1 % num_2
###############################################################################
if __name__ == '__main__':
main()Solution
This looks like a bug in the input validation:
The message "Please enter two positive integers." contradicts with the condition:
if both numbers are 0. I think you meant more like this:
I also removed redundant parentheses.
You had redundant parentheses in other places too:
These are all unnecessary, so I recommend to remove them.
You can simplify
Other than these minor issues, I think this is good and clean code! The names seem quite fine to me.
if (args.num_1 == 0) and (args.num_2 == 0):
print("Please enter two positive integers.")
else:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))The message "Please enter two positive integers." contradicts with the condition:
if both numbers are 0. I think you meant more like this:
if args.num_1 > 0 and args.num_2 > 0:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))
else:
print("Please enter two positive integers.")I also removed redundant parentheses.
You had redundant parentheses in other places too:
return(num_2, 0, 1)
# ...
return(gcd, lin_fact_2, lin_fact_1)These are all unnecessary, so I recommend to remove them.
You can simplify
x = x - ... with x -= ..., for example here:# instead of this:
# lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
lin_fact_1 -= num_1 // num_2 * lin_fact_2Other than these minor issues, I think this is good and clean code! The names seem quite fine to me.
Code Snippets
if (args.num_1 == 0) and (args.num_2 == 0):
print("Please enter two positive integers.")
else:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))if args.num_1 > 0 and args.num_2 > 0:
print(xggt(args.num_1, args.num_2))
print(modinv(args.num_1, args.num_2))
else:
print("Please enter two positive integers.")return(num_2, 0, 1)
# ...
return(gcd, lin_fact_2, lin_fact_1)# instead of this:
# lin_fact_1 = lin_fact_1 - num_1 // num_2 * lin_fact_2
lin_fact_1 -= num_1 // num_2 * lin_fact_2Context
StackExchange Code Review Q#69991, answer score: 3
Revisions (0)
No revisions yet.