Extended Euclidean Algorithm Table Method

ext_eucli.py

#! /usr/bin/env python3
#  
# <THE BSD-3 LICENSE>  https://opensource.org/licenses/BSD-3-Clause
# Copyright (c) 2019, Jing Kai Tan
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without modification,
# are permitted provided that the following conditions are met:
# 
#  - Redistributions of source code must retain the above copyright notice,
#   this list of conditions and the following disclaimer.
# 
#  - Redistributions in binary form must reproduce the above copyright notice,
#    this list of conditions and the following disclaimer in the documentation
#    and/or other materials provided with the distribution.
# 
#  - Neither the name of Jing Kai Tan nor the names of its contributors may
#    be used to endorse or promote products derived from this software without
#    specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#
#
# Euclidean extended table
# As taught in UOW.
# To be used to check against answers.
# Given a and b, find inverse of each.
# 
# Requires python 3.6+
# @author jingkai.


# An arbitary global dictionary to be shared amongst the functions.
# Yes it is bad form but this is just a quick script.
CURRENT = {
    'r':0, # Initialize r and q to some default value.
    'q':0,
    'a1':1, # Initalize according to extended
    'b1':0,
    'a2':0,
    'b2':1,
    'originalN1':0,
    'originalN2':0
}

def calculate(n1: int, n2: int,count:int)->(int,int):
    """
    A recursive function to perform the eucid calculation.
    @param n1, the current n1,
    @param n2, the next n2.
    @param count, the number of times this recursion function has been called.
    @throws KeyError, if you somehow manage to screw up the dictionary
    @throws ZeroDivisionError, don't enter a fucking 0.
    """
    if count == 0:
        reset_current()
        CURRENT['originalN1'] = n1
        CURRENT['originalN2'] = n2
    remainder = n1 % n2
    quotient = n1 // n2 # Floor division.
    
    # Base case.
    if remainder == 0:
        # Updates the values first.
        swap_remainders(remainder,quotient)
        print_table(n1,n2)
        print_inverse()
    else: 
        # Updates the values first.
        swap_remainders(remainder,quotient)
        print_table(n1,n2)
        swap_current()
        calculate(n2,remainder,count+1)

def print_inverse()->None:
    print(f'gcd({CURRENT["originalN1"]},{CURRENT["originalN2"]}): '\
        f'{CURRENT["originalN1"]}({CURRENT["a2"]}) '\
        f'{CURRENT["originalN2"]}({CURRENT["b2"]})')

def swap_remainders(remainder: int, quotient:int)->None:
    """
    Swaps the values of remainder and quotient
    @param remainder, the new remainder
    @param quoteint, the new quotient
    @throws KeyError, if you somehow manage to screw up the dictionary
    """
    previous_remainder = CURRENT["r"]
    previous_quotient = CURRENT["q"]
    CURRENT["r"] = remainder
    CURRENT["q"] = quotient 

def swap_current()->None:
    """
    Swaps the values of a1 -> b2 in the current shared dictionary.
    @param None
    @return None
    """
    temp_a2 = CURRENT.get("a2")
    CURRENT["a2"] = CURRENT.get("a1") - CURRENT.get("q") * CURRENT.get("a2")
    CURRENT["a1"] = temp_a2
    temp_b2 = CURRENT.get("b2")
    CURRENT["b2"] = CURRENT.get("b1") - CURRENT.get("q") * CURRENT.get("b2")
    CURRENT["b1"] = temp_b2

def print_table(n1:int, n2:int)->None:
    """
    Prints a nice row.
    @param n1, integer 1
    @param n2, integer 2
    @return None
    """
    print(f'{n1:>{4}} | {n2:>{4}} | {CURRENT["r"]:>{4}} | {CURRENT["q"]:>{4}} |'\
        f' {CURRENT["a1"]:>{4}} | {CURRENT["b1"]:>{4}} | {CURRENT["a2"]:>{4}} |'\
        f' {CURRENT["b2"]:>{4}}')

def print_headers()->None:
    """
    Prints headers for the rows.
    """
    print("\n\n{:>4s} | {:>4s} | {:>4s} | {:>4s} | {:>4s} | {:>4s} | {:>4s} | {:>4s}".format
            (
                u'N\u2081',u'N\u2082','r','q',
                u'A\u2081',u'B\u2081',u'A\u2082',
                u'B\u2082'
            )
        )
def reset_current()->None:
    CURRENT['r'] = 0
    CURRENT['a'] = 0
    CURRENT['a1'] = 1
    CURRENT['b1'] = 0
    CURRENT['a2'] = 0
    CURRENT['b2'] = 1
    CURRENT['originalN1'] = 0
    CURRENT['originalN2'] = 0

if __name__ == "__main__":
    print_headers()
    calculate(39,11,0)
    print_headers()
    calculate(41,25,0)
    print_headers()
    calculate(4051,3037,0)

➜ python3 ecuid_extended.py
N₁ | N₂ | r | q | A₁ | B₁ | A₂ | B₂
3 | 26 | 3 | 0 | 1 | 0 | 0 | 1
26 | 3 | 2 | 8 | 0 | 1 | 1 | 0
3 | 2 | 1 | 1 | 1 | 0 | -8 | 1
2 | 1 | 0 | 2 | -8 | 1 | 9 | -1
gcd(3,26): 3(9) 26(-1)

N₁ | N₂ | r | q | A₁ | B₁ | A₂ | B₂
11 | 26 | 11 | 0 | 1 | 0 | 0 | 1
26 | 11 | 4 | 2 | 0 | 1 | 1 | 0
11 | 4 | 3 | 2 | 1 | 0 | -2 | 1
4 | 3 | 1 | 1 | -2 | 1 | 5 | -2
3 | 1 | 0 | 3 | 5 | -2 | -7 | 3
gcd(11,26): 11(-7) 26(3)

N₁ | N₂ | r | q | A₁ | B₁ | A₂ | B₂
13 | 26 | 13 | 0 | 1 | 0 | 0 | 1
26 | 13 | 0 | 2 | 0 | 1 | 1 | 0
gcd(13,26): 13(1) 26(0)

This generates the Extended Euclidean Algorithm in a table form, to make it easy to spot mistakes.
The script was written based on the examples given in CSCI368 lecture notes, and serve as a quick check when attempting questions or solutions.