Extended Euclidean algorithm and modular multiplicative inverse element

Question

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()

Answer 1

This looks like a bug in the input validation:

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_2

Other than these minor issues, I think this is good and clean code! The names seem quite fine to me.

Answer 2

Some general feedback:

• Take a look at PEP8 and check your code with http://pep8online.com/

• Don't write those ######### lines, because PEP8 says:

  Separate top-level function and class definitions with two blank lines.

• If you add #!/usr/bin/env python in the first line, people can directly execute your code (on Linux machines at least). This is called Shebang. See my article for a very short explanation.

• ArgumentParser(description=__doc__) is very nice.
• Do you know doctests? I think they are very neat if you have simple functions that have parameters of integers and output of integers.