problem3.py


ffrom math import sqrt, ceil

class comp:
    # Constructor (used to create our complex number)
    def __init__( self, x: int, y: int ):
        self.a = x
        self.b = y

    # Defines the "-" operation between two complex numbers
    def __eq__( self, other: 'comp' ):
        return (self.a == other.a) and (self.b == other.b)

    # Defines the "-" operation between two complex numbers
    def __add__( self, other: 'comp' ):
        return comp( self.a + other.a, self.b + other.b )

    # Defines the "-" operation between two complex numbers
    def __sub__( self, other: 'comp' ):
        return comp( self.a - other.a, self.b - other.b )

    # Defines the "*" operation between two complex numbers
    def __mul__( self, other: 'comp' ):
        return comp( self.a * other.a - self.b * other.b, self.a * other.b + self.b * other.a )

    # Defines how a complex number should be turned into a string (i.e. text)
    def __str__( self ):
        return f'{self.a} {"-" if self.b < 0 else "+"} {abs(self.b)}i'

    # Defines the norm of a complex number
    def norm( self ) -> int:
        return self.a**2 + self.b**2

    # Creates a shorthand for determining if a complex number is zero
    def isZero( self ) -> bool:
        return self.a == 0 and self.b == 0


# Determines if the norm of the remainder is larger than the norm of y
def canBeQuotient( q , x, y ) -> bool:
    tmp = x - (y*q)
    return tmp.norm() < y.norm()


# Outputs all valid quotients for a pair x, y
# Creates a box around the valid locations for the remainder and scan that box.
# All valid quotients for the x, y are put into a list and returned
def searchForQuotient( x, y ):
    # Determines the radius of the circle that encloses all possible quotients
    radius = ceil(sqrt(x.norm())) if x.norm() > y.norm() else ceil(sqrt(y.norm()))

    digest = [ ]

    # Scan the real and imag. axises
    for r in range(0, radius):
        if canBeQuotient( comp(  r,  0 ), x, y ): digest.append( comp(  r,  0) )
        if canBeQuotient( comp( -r,  0 ), x, y ): digest.append( comp( -r,  0) )
        if canBeQuotient( comp(  0,  r ), x, y ): digest.append( comp(  0,  r) )
        if canBeQuotient( comp(  0, -r ), x, y ): digest.append( comp(  0, -r ) )

    # Scan the box between (1,1) and (radius, radius)
    # We'll trim out the circle later
    for r_a in range(1, radius):
        for r_b in range(1, radius):
            # If we are outside the circle, go to the next r_a value
            if r_a**2 + r_b**2 > radius**2:
                break
            if canBeQuotient( comp(  r_a,  r_b ), x, y ): digest.append( comp(  r_a,  r_b) )
            if canBeQuotient( comp( -r_a,  r_b ), x, y ): digest.append( comp( -r_a,  r_b) )
            if canBeQuotient( comp(  r_a, -r_b ), x, y ): digest.append( comp(  r_a, -r_b) )
            if canBeQuotient( comp( -r_a, -r_b ), x, y ): digest.append( comp( -r_a, -r_b) )

    return digest

# Finds all common divisors of x, y and returns them
# This uses recurrsion to implement the Chinese Remainder Theorem
def getCommonDivisors( x, y ):
    digest = [ ]

    # Finds all valid quotients for x, y
    Qs = searchForQuotient( x, y )
    for q in Qs:
        if (x - y*q).isZero():
            # If the remainder using a quotient, then y is a common divisor of x, y
            digest.append( y )
        else:
            # Otherwise, per the CRT, y becomes x and x-yq (the remainder) becomes y and you try again.
            digest += [ CD for CD in getCommonDivisors( y, x - y*q ) if CD not in digest ]

    return digest


# Our numbers that we are asked to compute the GCD of
first = comp( 850, 0 )
second = comp( 10, 50 )

Qs = searchForQuotient( first, second )
Ds = getCommonDivisors( first, second )

# Prints some numbers to make sure everything is working
print( [ str(c) for c in Qs ] )
print( [ str(c) for c in Ds ] ) # This is our answer


for i in range(len(Qs)):
    print( f'{second*Qs[i] + Ds[i]} = ({second})*({Qs[i]}) + ({Ds[i]})' )
  
          1