W dniu 21.09.2010 11:45, Wojciech "Spook" Sura pisze:
> Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>
> Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
> równe.

Korzystamy z:
a/b == c/d <=> a*d == b*c

Pozostaje kwestia przekraczania zakresów przy mnożeniu. I tu 2 rozwiązania:

- skorzystać z biblioteki, np. GMP

- samemu zaimplementować mnożenie:

Jeśli a, b, c i d masz w N bitowych zmiennych to możesz potraktować je
jako 2-cyfrowe liczby N/2 bitowe (tj w systemie o podstawie: 2^(N/2)).
Takie liczby możesz przemnożyć stosując "algorytm szkolny" ("mnożenie
pisemne", oczywiście w systemie o podstawie 2^(N/2), a nie 10), przy
czym wynik mnożenia dwóch N/2 bitowych cyfr mieści się na N bitach (więc
stosujesz N-bitowy typ do obliczeń).
Całość wymaga 4 mnożeń, kilku dodawań, operacji bitowych...
Wynik będzie liczbą składającą się z co najwyżej 4ech N/2 bitowych cyfr.
Takie liczby łatwo porównasz cyfra po cyfrze.

Jest jeszcze kwestia znaków (liczb ujemnych), tych zgodność możesz
jednak sprawdzić przed powyższymi obliczeniami. W przypadku zgodności
możesz liczyć na wartościach bezwzględnych używając N-bitowego typu bez
znaku.

--
Piotr Beling - http://qwak.w8.pl http://warcaby.w8.pl http://bcalc.w8.pl