Euclidean algorithm can't handle 2/3?

[Javulticat]

I'm currently using an implementation of the Euclidean algorithm in a program I am developing in order to take a decimal answer and display it as a fraction. For example, I entered 2/18, the program would use the Euclidean algorithm to display the answer as 1/9, instead of .1111111111 (indefinitely repeating). Every number combination I've tried works fine, with the exception of 2/3. Whenever I enter 2/3 (or 4/6, 6/9, etc.), the program always displays the answer as 2/2. So, the question is, is the Euclidean algorithm not capable of correctly calculating 2/3, or is it just that my implementation of the Euclidean algorithm is incorrect?

[NickThissen]

I'm pretty sure it's your code. Can you show it to us?

[Javulticat]

Sure, but it's programmed in a language most have never heard of, TI-Basic. It's the programming language for TI calculators. I guess it's similar to BASIC, but I've never used BASIC, so I'm not positive on that. I'll try to comment where ever I can to explain what the code does, but I just got it off a tutorial, and I'm not exactly sure what all of it does.

Prompt A //Prompts user for value of A.
Prompt B //Prompts user for value of B.
A/B //Divides A by B.  Answer is stored in variable Ans automatically.
Ans→X:{1,abs(X)} //Not exactly sure, but I know that X is being made equal to Ans and that abs(X) means absolute value of X.
Repeat E-9>Ans(2) //Repeats the following line until Ans(2) is less than E-9 (in true Euclidean algorithm, it should be until Ans(2) is equal to 0, but due to loss of precision, you must make it less than E-9).
abs(Ans(2){1,fPart(Ans(1)/Ans(2))}) //No idea.
End //Ends the repeat loop.
iPart({X,1}/Ans(1)) //No idea.
Text(1,1,Ans(1),"/",Ans(2)) //At this point, Ans(1) is the numerator and Ans(2) is the denominator.  This line just outputs the result in numerator/denominator form.

[jemidiah]

I bet you'd be surprised how many people have used TI-BASIC. I wrote a Sudoku solver in it during Calc class. Why not use the gcd function? On my 84, it's under Math->Num->9.

The code is using a list of two elements simultaneously, I have no idea why. It may as well use a couple of the letter variables for clarity. For instance, "abs(Ans(2){1,fPart(Ans(1)/Ans(2))})" is taking the element-wise absolute value of the list {1,fPart(Ans(1)/Ans(2))} which is first element-wise multiplied by Ans(2), and storing that as the next Ans list. It's elegant in a horrible sort of way.

If your numbers are small you can easily implement the much slower original Euclidean algorithm,

function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a - b)

without all of the awful imitation modular arithmetic that's been done here. I'd have to go through each line too carefully for it to be worthwhile to figure out why 2/3 is going wrong, particularly since gcd() would work anyway. But, the Euclidean algorithm does work in that case if implemented correctly.

[Logophobic]

The problem isn't with the code. There is a rounding error in the calculation of (1/2)*(2/3) such that it isn't equal to 1/3.

To demonstrate, with less precision than the TI uses:

1/3 = 0.33
2/3 = 0.67
0.67 / 2 = 0.34 (rounding up from 0.335)
0.34 <> 0.33

To get around this problem, change the next-to-last line to this:

iPart round({X,1}/Ans(1),11)