3

I am trying to code an algorithm in Python in order to solve linear Diophantine equations.

I think my algorithm is correct because I have tested it on a paper, however when I run it, it returns strange values.

My code:

def solve_Dioph(a,b,c):
    m1=1
    m2=0
    n1=0
    n2=1
    r1=a
    r2=b
    while r1%r2!=0:
        q=r1/r2
        aux=r1%r2
        r1=r2
        r2=aux
        aux3=n1-(n2*q)
        aux2=m1-(m2*q)
        m1=m2
        n1=n2
        m2=aux2
        n2=aux3
    return m2*c,n2*c;

It uses 7 variables and 3 auxiliar variables. After testing it with a pen and a paper, with this values:

a=65 b=14 c=4

I get

m2=-3*4 and n2=14*4

However, when I run it:

solve_Dioph(65,14,4)

It returns:

(-227/9, 16393/126)
duplode
  • 33,731
  • 7
  • 79
  • 150
Oscar Martinez
  • 621
  • 1
  • 8
  • 18
  • This is genius, i must admit i never expected there would be an extended euclidean algorithm that doesn't use recursion. – D. Sikilai Jul 04 '22 at 15:04

1 Answers1

4

I'm guessing you're using Python 3 (as opposed to Python 2). In Python 3, dividing two integers with / produces a float result. However, you can force the Python 2 behavior by using the // operator. Try changing the following line:

q=r1/r2

To:

q=r1//r2
Tom Karzes
  • 22,815
  • 2
  • 22
  • 41
  • You mean, "In Python 3, symbol `/` is floating-point division, and symbol `//` is integer division." The sentence "integer division returns a float result" is a self-contradiction. – Stef Dec 04 '21 at 15:03
  • 1
    @Stef It was poorly worded. I used "integer division" when I really meant "dividing two integers with `/`". I've updated the wording. – Tom Karzes Dec 04 '21 at 16:05