Originally Posted by
TKHunny Have you considered the value of first determining if there IS a solution? A little number theory would get you there.
This is easily solved by whether or not C Modulo GCD(A, B) = 0. There are also a few other pitfalls that determine whether or not there is a solution. If it gets beyond that and there are no positive solutions available in a finite number set, then I will pseudo no-solution the equation. I will read up on number theory though, thanks for the suggestion.
Originally Posted by
ymar Try reading Euclidean algorithm - Wikipedia, the free encyclopedia
I think I have the Elucidian algorithm down. My problem is when I get beyond the Extended Elucidian algorithm, putting the quotients into a table and getting the Bezout's identity, that I start to have troubles. I think creating the identity is of somewhat trouble to me, although I may have solved the identity issue, I am not getting beyond that. However, I have been messing with my identity code and broke it and have to start it from scratch since I can't figure out what I broke. It's only a couple lines anyway.
I don't know if you know Python coding but this is what I have for the Elucidian and Extended Elucidian algorithms.
Code:
######################
###Elucid Algorithm###
######################
def ElucidAlgorithm(a, b):
global aTable#if abs(a) > abs(b) 0 else 1
global bTable#if abs(b) > abs(a) 0 else 1
print '###Elucid Algorithm###'
print '######################'
print 'Elucid Algorithm: ' + str(a) + ', ' + str(b)
#dividend = divisor * quotient + modulo
quotients = []
divisors = []
if aTable:
dividend = a
divisor = b
else:
dividend = b
divisor = a
divisors.append(divisor)
quotient = int(dividend / divisor)
quotients.append(quotient)
modulo = dividend % divisor
print 'Elucid Algorithm: ' + str(dividend) + ' = ' + str(divisor) + ' * ' + str(quotient) + ' + ' + str(modulo)
while modulo != 0:
dividend = divisor
divisor = modulo
divisors.append(divisor)
quotient = int(dividend / divisor)
quotients.append(quotient)
modulo = dividend % divisor
print 'Elucid Algorithm: ' + str(dividend) + ' = ' + str(divisor) + ' * ' + str(quotient) + ' + ' + str(modulo)
if divisor * quotient == dividend:
print 'Elucid Algorithm: Return (' + str(a) + ', ' + str(b) + ') ' + str(divisor)
return [divisor, quotients, divisors]
else:
print 'Elucid Algorithm: Return no solutions'
return 0
###############################
###Extended Elucid Algorithm###
###############################
def ExtendedElucidAlgorithm(a, b):
global aTable
global bTable
print '###Extended Elucid Algorithm###'
print '###############################'
gcdQuosDivs = ElucidAlgorithm(a, b)
if gcdQuosDivs != 0:
##################
###TABLE METHOD###
##################
print '###Extended Elucid Algorithm: TABLE METHOD###'
print '##############################################'
#populate table
print 'Extended Elucid Algorithm: Populate table'
table = [[0,1], [1,0]]
for quotient in gcdQuosDivs[1]:
table[aTable].append(quotient * table[aTable][len(table[aTable]) - 1] + table[aTable][len(table[aTable]) - 2])
table[bTable].append(quotient * table[bTable][len(table[bTable]) - 1] + table[bTable][len(table[bTable]) - 2])
row0 = 'a('+str(a)+'): '
row1 = 'b('+str(b)+'): '
for x in range(0, len(table[aTable])):
row0 = row0 + str(table[aTable][x]) + ' '
row1 = row1 + str(table[bTable][x]) + ' '
print 'Extended Elucid Algorithm: ' + row0
print 'Extended Elucid Algorithm: ' + row1
print 'Extended Elucid Algorithm: Return table'
return [gcdQuosDivs, table]
else:
print 'Extended Elucid Algorithm: Return no solutions'
return 0