Thread: What's wrong in this code ?

1. What's wrong in this code ?

Hey all,
I've been trying to figure out for a whole evening what was wrong in the code I wrote to apply the extended euclidean algorithm on two coprime numbers in order to obtain the multiplicative inverse of $\displaystyle a$ modulo $\displaystyle b$. This is what I get (this is delphi, longword is the basic unsigned 32-bit integer) :

Code:
function ModularInverse(a, b: Longword): Longword;
Var
X, Y, lastX, lastY, temp, quotient: Longword;
begin
X := 0;
Y := 1;
Lastx := 1;
Lasty := 0;

while b <> 0 do
begin
Quotient := A div B;
Temp := B;
B := A mod B;
A := Temp;

Temp := X;
X := Lastx - quotient * X;
Lastx := temp;

temp := y;
y := lasty - quotient * y;
lasty := temp;
end;

Result := X;
end;
But this code keeps failing on even basic inputs like the inverse of 15 modulo 19 ! The answer should be 14 but it just keeps answering either 4, either 10 or sometimes 19 or 0. What the hell is wrong with this ? This is really melting my brain down. I really feel like my computer can't add two numbers right ...

Thanks all

2. Originally Posted by Bacterius
Hey all,
I've been trying to figure out for a whole evening what was wrong in the code I wrote to apply the extended euclidean algorithm on two coprime numbers in order to obtain the multiplicative inverse of $\displaystyle a$ modulo $\displaystyle b$. This is what I get (this is delphi, longword is the basic unsigned 32-bit integer) :

Code:
function ModularInverse(a, b: Longword): Longword;
Var
X, Y, lastX, lastY, temp, quotient: Longword;
begin
X := 0;
Y := 1;
Lastx := 1;
Lasty := 0;

while b <> 0 do
begin
Quotient := A div B;
Temp := B;
B := A mod B;
A := Temp;

Temp := X;
X := Lastx - quotient * X;
Lastx := temp;

temp := y;
y := lasty - quotient * y;
lasty := temp;
end;

Result := X;
end;
But this code keeps failing on even basic inputs like the inverse of 15 modulo 19 ! The answer should be 14 but it just keeps answering either 4, either 10 or sometimes 19 or 0. What the hell is wrong with this ? This is really melting my brain down. I really feel like my computer can't add two numbers right ...

Thanks all
Case sensitive?

CB

3. Originally Posted by CaptainBlack
Case sensitive?

CB
Hi Captain Black,
Delphi is not case-sensitive :/