(11C) Arithmetic with Fractions

[Albert Chan]

(09-17-2018 01:12 AM)Albert Chan Wrote:  Hi, Thomas Klemm,

Thanks for the link to Kahan paper. I tried it, it work perfectly.

However, Kahan's example does not shown the algorithm's power.
Doing the math as fixed fraction already avoid the overflow problem ...

I made up a better example, to show Kahan's algorithm, where mixed fraction trick won't work:

M/N = 1234567/12345648 - 635720/6357263

From Kahan's paper: (using HP-12C, with my Mod/Gcd program)
G = gcd(12345648, 6357263) = 181
b = 12345648 / 181 = 68208
d = 6357263 / 181 = 35123
a = 1234567 % 181 = 147
c = 635720 % 181 = 48
ad - bc = 147*35123 - 68208*48 = 1889097 = 181 * 10437
g =gcd(G, ad - bc) = 181

M = 10437 + Det({{6820, 68208}, {3512, 35123}}) = 10437 - 7636 = 2,801
N = G/g * b * d = 68208 * 35123 = 2,395,669,584